[이코테 with Java] 재귀함수

■ 재귀 함수

---

재귀함수(Recursive Function)란 자기자신을 다시 호출하는 함수를 의미한다.

import java.util.*;

public class Main {
    public static void recursiveFunction(){
        System.out.println("재귀 함수를 호출합니다.");
        recursiveFunction();
    }

    public static void main(String[] args){
        recursiveFunction();
    }
}

 

이 코드를 실행하면 "재귀 함수를 호출합니다."라는 문자열을 무한히 출력한다. 여기서 정의한 recursive_function()이 자기 자신을 계속해서 추가로 불러오기 때문이다.

물론 어느 정도 출력하다가 다음과 같은 오류 메시지를 출력하고 멈출 것이다. 

RecursionError: maximum recursion depth exceeded while pickling an object

 

이 오류 메시지는 재귀(Recursion)의 최대 깊이를 초과했다는 내용이다. 

 

■ 재귀 함수의 종료 조건

---

재귀 함수는 재귀 함수가 언제 끝날지, 종료조건을 꼭 명시해야 한다.

자칫 종료 조건을 명시하지 않으면 함수가 무한 호출될 수 있다.

 

import java.util.*;

public class Main {
    public static void recursiveFunction(int i){
        // 100번째 호출을 했을 때 종료되도록 종료 조건 명시
        if(i == 100) return;
        System.out.println(i + "번째 재귀 함수에서 " + (i + 1) + "번째 재귀함수를 호출합니다.");
        recursiveFunction(i + 1);
        System.out.println(i + "번째 재귀 함수를 종료합니다.");
    }

    public static void main(String[] args){
        recursiveFunction(1);
    }
}

 

 

여기에서 재귀함수 호출이 끝나면 ( i가 100이 되어 return을 만났을 경우)  System.out.println(i + "번째 재귀 함수를 종료합니다.")가 출력된다. 

 

1번째 재귀 함수에서 2번째 재귀 함수를 호출합니다.
2번째 재귀 함수에서 3번째 재귀 함수를 호출합니다.
3번째 재귀 함수에서 4번째 재귀 함수를 호출합니다.
...
98번째 재귀 함수에서 99번째 재귀 함수를 호출합니다.
99번째 재귀 함수에서 100번째 재귀 함수를 호출합니다.
100번째 재귀 함수를 종료합니다.
99번째 재귀 함수를 종료합니다.
98번째 재귀 함수를 종료합니다.
...
3번째 재귀 함수를 종료합니다.
2번째 재귀 함수를 종료합니다.
1번째 재귀 함수를 종료합니다.

 

컴퓨터 내부에서 재귀 함수의 수행은 "스택 자료구조"를 이용한다.

함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 

위의 재귀 함수 100번 호출에서, "종료합니다"라는 문구가 나와야 하지만, 앞의 재귀 함수 호출이 끝나지 않아 "종료합니다"가 호출되지 않는다. 그래서 1~100까지의 "종료합니다"가 내부적으로 쌓여있다. 

앞서 "재귀 함수" = "스택"이라고 했듯이 1번부터 "종료합니다" 문구가 나오지 않는 이유도 동일하다.

1~100까지의 "종료합니다"가 쌓여있는데, 가장 마지막에 호출한 100번째 "종료합니다" 먼저 출력돼야 하기 때문에 

100->1 순으로 "종료합니다"가 출력되는 것이다. 

 

■ 팩토리얼과 점화식

---

재귀 함수를 이용하는 대표적 예제로는 "팩토리얼(Factorial)" 문제가 있다.

팩토리얼은 수학적으로 0!과 1!의 값은 1로 같다는 성질을 이용하여, 1이 1 이하가 되었을 때 함수를 종료하는 재귀 함수의 형태로 구현할 수 있다.

 

 팩토리얼은 반복적으로 구현하는 방식과 재귀적으로 구현하는 방식이 있다. 

 

1. 반복적으로 구현하는 방식

import java.util.*;

public class Main {

    // 반복적으로 구현한 n!
    public static int factorialIterative(int n){
        int result = 1;
        // 1부터 n까지의 수를 차례대로 곱하기
        for(int i = 1; i <= n; i++){
            result *= i;
        }
        return result;
    }

    public static void main(String[] args){
        System.out.println("반복적으로 구현:" + factorialIterative(5));
    }
}

 

2. 재귀적으로 구현하는 방식

import java.util.*;

public class Main {
    public static int factorialRecursive(int n){
        // n이 1 이하인 경우 1을 반환
        if(n <= 1) return 1;
        // n! = n * (n - 1)!를 그대로 코드로 작성하기
        return n * factorialRecursive(n - 1);
    }

    public static void main(String[] args){
        System.out.println("재귀적으로 구현:" + factorialRecursive(5));
    }
}

 

실행 결과는 동일하다. 그렇다면 반복문보다 재귀 함수를 사용하는 이유가 뭘까?

위의 코드를 비교했을 때 재귀 함수의 코드가 더 간결하다. 

왜냐하면 재귀 함수가 "점화식(재귀식)"을 그대로 소스코드로 옮겼기 때문이다.

 

점화식 : 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 
               n이 0 혹은 1일 때: factorial(n) = 1
              n이 1보다 클 때: factorial(n) = n x factorial(n - 1)