[자료구조/알고리즘] Chapter 02. 재귀(자기호출)함수 - (1) 팩토리얼, 피보나치 수열

해당 시리즈는 제가 책(쉽게 배우는 자료구조 with 자바)을 읽고 해당 내용을 정리하기 위하여 작성되었습니다.

어렵다고 느껴지는 자료구조를 최대한 쉽게 설명하고자 풀어쓰는 점 참조해주시고,

같이 자료구조/알고리즘에 대해 공부하는 시간이 되었으면 좋겠습니다. 감사합니다.

---

자료구조와 재귀

재귀?

 

재귀는 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러내는 것 입니다.

단어가 생소하여 무슨 의미인지 잘 와닿지 않을 수 있는데요. (제가 그랬습니다.)

가장 간단한 예인 팩토리얼(!)로 설명 드리겠습니다.

 

팩토리얼은 1부터 n까지 곱하는 것으로 n! = 1 * 2 * 3 * ... * (n - 1) * n 입니다.

여기서 맨 끝에 있는 n을 제외하면 1 * 2 * 3 * ... * (n - 1),  (n - 1)! 입니다.

다시 정리하면 n! = n * (n - 1)! 입니다. 혹시 뭔가 느껴지시는 게 있나요?

 

이처럼 크기가 n인 팩토리얼 크기가 n - 1인 팩토리얼을 포함하고 있습니다. 이처럼 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 '재귀적 구조'를 갖고 있다고 말합니다.

 

프로그래밍 언어에서는 재귀를 함수 내부에서 자신을 호출하는 자기 호출 기능이라고도 합니다.

'재귀'의 의미가 직관적으로 잘 와닿지 않기 때문에 '자기 호출'이라는 말과 혼용하여 쓰도록 하겠습니다.

---

재귀 구조의 예1) 팩토리얼

 

앞서 설명드렸던 팩토리얼을 자바 코드로 작성해보겠습니다.

public class Main {
    public static void main(String[] args) {
        System.out.println("3! = " + factorial(3));
    }
    public static int factorial(int n) {
        if(n == 1) {
            return 1;
        } else return n * factorial(n-1);
    }
}

 이렇게 재귀함수는 함수가 자기 자신을 호출하는 것을 말합니다.

즉, 함수가 수행되는 도중에 자기 자신을 다시 호출하여 문제를 해결하는 방식인데요.

이렇게 자기 자신을 호출하면서 함수가 반복적으로 호출되는 것을 '재귀호출(자기 호출)' 이라고합니다.

 

팩토리얼 같이 간단한 문제의 경우에는 입력값이 작기 때문에 for문과 재귀함수의 성능 차이가 크지 않지만, 이진 탐색과 같은 분할 정복 알고리즘은 재귀함수를 이용한 구현이 더 빠릅니다.

---

• 이진 탐색 : 정렬된 배열에서 특정 값을 찾는 알고리즘
  배열의 중간값과 찾고자 하는 값의 크기를 비교하여 탐색 범위를 반으로 줄여가며 값을 찾음.
• 분할 정복 : 큰 문제를 작은 부분으로 나누어 해결하는 알고리즘
  큰 문제를 작은 부분 문제로 분할한 후, 부분 문제를 각각 해결하고, 각 부분 문제의 해결 방법을 결합하여 전체 문제를 해결하는 방법(병합 정렬, 퀵 정렬, 이진 탐색 등)

재귀 구조의 예2) 피보나치 수열

 

피보나치 수열은 이전 두 항의 합이 다음 항이 되는 수열 입니다.

즉, 0과 1부터 시작하여 다음과 같이 나열됩니다.

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

 

이 수열을 재귀 함수로 구현해볼까요?

public static int fibonacci(int n) {
    if (n == 0) { // 종료 조건 1
        return 0;
    } else if (n == 1) { // 종료 조건 2
        return 1;
    } else { // 재귀 호출
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

위 코드에서 fibonacci()는 n번째 피보나치 수를 반환합니다.

n이 0이나 1일 때는 각각 0, 1을 반환하며, 그 외의 경우에는 이전 두 항의 합을 계산하기 위해 자기 자신을 두 번 호출하여 재귀적으로 문제를 해결합니다.

 

코드를 보면 아시다시피 재귀 알고리즘은 반복해서 호출하다가 언젠가 끝나야 하는데 이를 위한 경계 조건을 항상 갖고 있어야 합니다.

 

팩토리얼 함수는 if(n == 1)이 경계 조건이고, 피보나치 수열은 if(n == 0)과 if(n == 1) 입니다.

---

유의할 점

 

위의 fibonacci()를 예로 들어 설명하자면.. 재귀 알고리즘으로 구현하고 큰 값을 구하려고 하면 오버플로우가 발생됩니다.

아마fibonacci(100)을 계산하려면 평생 기다려도 결과를 볼 수 없을 것입니다.

 

그 이유는 뭘까요?

바로 재귀함수의 호출 횟수가 입력 크기에 따라 지수적으로 증가하기 때문 입니다.

n번째 피보나치 수를 계산하기 위해서는 재귀 호출이 2^(n-1)번이 이루어집니다. 따라서, 입력 크기가 커질 수록 재귀함수의 호출 횟수는 기하급수적으로 증가하게 됩니다.

 

이러한 지수함수적인 증가는 알고리즘이 비효율적이며, 입력 크기가 커질수록 실행시간이 급격히 증가하기 때문에 재귀함수를 이용한 알고리즘을 설계할 때는 가능한 지수 함수적인 호출 횟수를 최소화해야 합니다.

 

개선 방안(?)

 

해당 코드가 비효율적인 걸 알았으면 개선 코드도 알아봐야겠죠!

public static int fibonacci(int n) {
    if (n < 2) {
        return n;
    }
    int[] fib = new int[n+1];
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib[n];
}

이 코드에서는 fib[]를 이용하여 중복되는 계산을 최소화 하였습니다.

1. 입력 값 n에 따라 fib[]을 생성하고, 배열의 첫 번째 값과 두 번째 값에 각각 0과 1을 저장합니다.
2. 2 부터 n 까지 반복하면서, 이전 두 개의 값을 더한 값을 현재의 값으로 저장합니다.
3. fib[n] 값을 반환하여 피보나치 수열의 n번째 값을 계산 합니다.

이 코드는 입력값에 따라 선형적인 실행 시간을 가지므로 재귀 함수를 이용하는 것보다 훨씬 효율적 입니다.

아까 코드로는 fibonacci(100)을 실행하면 평생 걸려도 결과값을 못봤다면 이 코드로는 천만 분의 1초도 걸리지 않습니다.

---