[Java] 재귀 함수(Recursive Function)로 피보나치 수열 예제로 쉽게 이해하기

재귀는 함수가 자기 자신을 다시 호출하는 방식으로, 잘 사용하면 복잡한 문제를 매우 간결하게 표현할 수 있습니다. 재귀를 처음 배울 때 가장 많이 사용하는 예제인 피보나치 수열 코드를 통해 그 원리를 파헤쳐 보겠습니다.

 

재귀 함수의 핵심 구성 요소

재귀 함수는 반드시 두 가지 요소를 가져야 합니다.

1. 기본 단계 (Base Case): 재귀 호출을 멈추는 조건입니다. 이 부분이 없다면 함수가 무한히 자신을 호출하다가 StackOverflowError를 내뿜으며 프로그램이 종료됩니다. 가장 중요합니다!
2. 재귀 단계 (Recursive Step): 문제를 더 작은 단위로 쪼개기 위해 자기 자신을 호출하는 부분입니다.

 

피보나치 수열 재귀 함수 코드

피보나치 수열은 F(n) = F(n-1) + F(n-2) (단, F(1)=1, F(2)=1)로 정의됩니다. 이 정의 자체가 재귀적이죠. 이걸 코드로 그대로 옮기면 다음과 같습니다.

public class Main {

    /**
     * 피보나치 수열을 계산하는 재귀 함수
     * @param n 계산할 항의 위치 (양의 정수)
     * @return n번째 피보나치 수
     */
    public static int fibonacci(int n) {
        // 1. 기본 단계 (Base Case): n이 2 이하일 때 재귀를 멈춤
        if (n <= 2) {
            return 1;
        }

        // 2. 재귀 단계 (Recursive Step): 더 작은 문제로 나누어 자신을 호출
        return fibonacci(n - 2) + fibonacci(n - 1);
    }

    public static void main(String[] args) {
        int number = 10;
        int result = fibonacci(number);
        System.out.println("피보나치 수열의 " + number + "번째 항: " + result); // 결과: 55

        int number_5 = 5;
        int result_5 = fibonacci(number_5);
        System.out.println("피보나치 수열의 " + number_5 + "번째 항: " + result_5); // 결과: 5
    }
}

 

fibonacci(5) 호출 과정 분석

코드는 간단하지만, 내부 동작은 어떻게 이루어질까요? fibonacci(5)가 호출되는 과정을 단계별로 따라가 봅시다.

• fibonacci(5)
  • return fibonacci(3) + fibonacci(4)

이 값을 얻기 위해 컴퓨터는 fibonacci(3)과 fibonacci(4)를 계산해야 합니다.

• fibonacci(3)을 먼저 계산합니다.
  • return fibonacci(1) + fibonacci(2)
  • fibonacci(1)은 1을 반환합니다. (Base Case)
  • fibonacci(2)도 1을 반환합니다. (Base Case)
  • 따라서 fibonacci(3)의 결과는 1 + 1 = 2입니다.
• 이제 fibonacci(4)를 계산합니다.
  • return fibonacci(2) + fibonacci(3)
  • fibonacci(2)는 1을 반환합니다. (Base Case)
  • fibonacci(3)은 위에서 이미 2라고 계산했습니다.
  • 따라서 fibonacci(4)의 결과는 1 + 2 = 3입니다.

최종적으로 fibonacci(5)는 fibonacci(3)의 결과(2)와 fibonacci(4)의 결과(3)를 더하여 5를 반환하게 됩니다.