[Java]재귀 함수(Recursive Functions)

재귀 함수는 위 그림처럼 정의 단계에서 자기 자신을 다시 호출하는 함수를 말한다.

 

수학으로 봤을 땐 점화식이라고 생각하면 편하다.

f(n) = f(n - 1) + n // 점화식

재귀 함수를 활용하면 반복적인 작업을 해야 하는 문제를 간결하게 풀 수 있는 경우가 있다.

 

반면 코드에 대한 직관적인 이해가 어렵고, 메모리를 많이 사용하게 된다는 단점도 존재한다.

 

재귀 함수에 익숙해지기 위해선 문제를 작게 쪼개는 연습을 하는 게 중요한데,

 

가장 간단한 예 중 하나인 팩토리얼로 예를 들어보자.

 

먼저 팩토리얼은 다음과 같이 계산한다.

n! = n * (n - 1) * (n - 2) * ... * 2 * 1

0! = 1

1부터 n까지의 모든 자연수를 곱하는 계산이라고 생각하면 된다.

 

먼저 이 계산을 반복문을 통해 구현해 보자.

// 반복문으로 구현한 팩토리얼

public static int factorial(int n) {

        int fac = 1; // 초기값 설정

        for (int i = n; i > 1; i--) { // 반복문 생성
            fac = fac * i;
        }
        return fac;
    }

for문을 통해 자연수를 n부터 2까지(미리 설정된 초기값 1 제외) 호출해 곱한 것을 볼 수 있다.

 

계속해서 같은 문제를 재귀 함수를 이용해 풀어보자.

 

문제를 작게 쪼개는 연습부터 시작이다. 팩토리얼의 정의를 가만히 보면 아래와 같은 관계식을 얻을 수 있다.

n! = n * (n - 1)!

n!이라는 계산을 n 곱하기 (n - 1)!로 잘게 쪼갠 것이다.

 

이를 더 이상 반복할 수 없을 때까지 반복하면 아래와 같다.

n! = n * (n - 1)!
   = n * (n - 1) * (n - 2)!
   = n * (n - 1) * (n - 2) * (n - 3)!
   ...
   = n * (n - 1) * (n - 2) * (n - 3) * ... 3 * 2 * 1

이런 식으로 문제를 가장 작은 단위까지 쪼개고 나니 초기값이 1이라는 것도 명확하게 보인다.

 

그럼 위 논리를 바탕으로 코드를 작성해 보자.

// 재귀함수로 구현한 팩토리얼

public static int factorial(int n){

    if(n == 0) return 1; // base case, 초기값, 0! = 1
    
    return n * factorial(n - 1);
    
    }

 

좋은 코드지만 계산을 쪼갰다는 것을 더 명시적으로 표현하고 싶다.

 

이럴 때 관행적으로 사용되는 키워드가 head와 tail인데, 예제를 계속해서 보자.

// 재귀함수와 head, tail을 이용해 구현한 팩토리얼

public static int factorial(int n){

    if(n == 0) return 1; // base case, 초기값, 0! = 1

    int head = n; // 첫 번째 요소
    
    int tail = n - 1; // 나머지 요소

    return head * factorial(tail);

    }

로직에서 코드를 바로 가져온 예제에 비해 덜 직관적으로 보일 수도 있다.

 

하지만 규칙을 가진 배열이 있을 때 지금처럼 첫 요소 head와 나머지 tail을 구분하는 연습을 하면

 

복잡한 문제를 푸는 데에 도움이 크게 된다.

 

참고로 반복문과 변수를 이용해 구현된 알고리즘은 언제나 재귀 함수로 변환될 수 있고, 그 역도 성립한다.

 

마지막으로 factorial() 함수를 구현하는 순서를 되짚으며 재귀함수 구현 시 절차를 간략하게 정리하자.

 

 

1. 입력값과 출력 값 정의하기

 

말 그대로 함수에 어떤 타입의 요소가 입력되고 출력되는지 파악하는 일이다.

 

factorial 함수는 int 타입 요소를 입력받아 int 타입을 리턴한다. 대략 다음과 같다.

factorial: int -> int

 

2. 문제를 쪼개고 경우의 수 나누기

factorial(n) = n * factorial(n - 1)

위의 예에서 처음 이렇게 문제를 쪼갠 것처럼, 큰 문제를 더 작은 문제로 쪼개는 로직을 생각해 본다.

 

더 이상 쪼갤 수 없는 문제가 무엇인지 파악하는 게 좋다.

 

위 예에서는 n에 0이 대입되었을 때가 더 이상 쪼갤 수 없는 경우이며, 나머지 경우와 다르게 처리해야 한다.

factorial: int => factorial(0) / factorial(int n)

 

3. 단순한 문제 해결하기 - 초기값 설정

 

더 이상 쪼갤 수 없는, 그러니까 가장 간단한 문제를 먼저 해결한다.

 

이를 base case라고 하며, 종료 조건 혹은 재귀의 기초라고도 부른다.

 

위의 예에선 n이 가장 작은 값일 때, 그러니까 0이 대입되었을 때의 문제를 풀고 종료 조건으로 삼아야 한다.

factorial: int => factorial(0) = 1 / factorial(int n)

 

4. 복잡한 문제 해결하기 - head와 tail 구분

 

위의 종료 조건(이 경우엔 0)을 제외한 n이 주어질 때의 문제를 푼다.

 

앞서 봤던 것처럼 입력값의 첫 요소(head)와 나머지(tail)를 입력받는 문제를 구분해

 

함수를 재귀적으로 표현한다.

factorial: int => factorial(0) = 1 / factorial(int n) = n * factorial(int n - 1)

 

5. 코드로 작성

 

위 단계까지 마쳤다면 남은 일은 논리를 코드로 옮기는 것뿐이다.

 

수도 코드를 작성하며 진행하는 것을 연습하는 편이 좋다.