[Algorithm] 재귀 함수 (Recursive Function)

재귀 함수(Recursive Function)

Computer Science에서 재귀는 자신을 정의할 때 자기 자신을 재참조 하는 방법이라고 정의되어 있고 프로그래밍에서 재귀 호출로 많이 사용된다.

public class RecursionTest {
    static void recursion() {
        System.out.println("Hello");
        recursion();
    }
    public static void main(String[] args) {
        recursion();
    }
}

위와 같이 자기 자신을 계속 호출하는 메서드를 재귀 함수(Recursive Function)라고 한다.

하지만 위 코드는 main에서 recursion 메서드를 호출하면 recursion 메서드가 자기 자신을 계속 호출하고 종료 조건이 없기 때문에 계속해서 Hello를 출력하다가 StackOverflowError가 발생하며 프로그램이 종료된다.

 

위 코드의 결과로 알 수 있는 것처럼 재귀함수는 재귀의 깊이가 길어질수록 메모리가 많이 사용되어 함수의 종료 조건을 적절하게 작성하지 않으면 문제가 될 수 있다.  하지만 종료 조건을 주의 깊게 작성해서 재귀 함수를 사용하면 반복문을 대신해서 코드의 가독성을 높이고 변수의 사용을 줄일 수 있다.

 

재귀 함수는 함수의 종료 조건이 되는 base case와 계속해서 호출하는 recursive case가 있다. 재귀 함수는 base case가 반드시 하나는 있어야 하고 recursive case는 조건이 base case로 수렴하도록 작성해야 한다.

재귀 함수의 장점

1. 불필요하게 여러 개의 반복문을 사용하지 않아서 코드가 간결해진다.

2. 수정이 용이하다.

3. 변수를 여러개 사용할 필요가 없어진다.

재귀 함수의 단점

1. 코드의 흐름이 직관적으로 보이지 않는다.

2. 반복문에 비해 메모리를 더 많이 사용하게 된다.

---

1부터 n까지의 합 구하기

public class RecursionTest {
    static int sum(int n) {
        if (n == 1) {
            return 1;
        }
        return n + sum(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(sum(5)); //15
    }
}

재귀적으로 1부터 n까지 합을 구하는 함수인데, 그림으로 보면 다음처럼 표현할 수 있다.

static int sum(int n) {
    if (n == 1) { //base case
        return 1;
    }
    return n + sum(n - 1); //recursive case
}

위 함수에서 base case는 n이 1인 경우이고 recursive case에서는 n을 1씩 줄이면서 base case로 수렴하도록 작성하고 있다. 

그래서 매개변수로 받은 n이 1씩 줄어들면서 호출하고 n이 1인 경우 base case에 걸려서 호출 순서의 역방향으로 return 하여 결과를 얻게 된다.

 

피보나치 수열

피보나치 수열은 (편의상 0번째 항 0으로) 0,1,1,2,3,5,8,13,21,34,55,.....처럼 2부터 자기 바로 앞 두 항의 합으로 나열된 수열이다. 피보나치 수열도 재귀 함수의 대표적인 예제로 재귀적으로 구현할 수 있다.

public class RecursionTest {
    static int fibo(int n) {
        if (n <= 1) {
            return n;
        }
        return fibo(n - 1) + fibo(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fibo(5)); //5
    }
}

base case는 n이 1 이하일 때 n을 반환해서 재귀를 종료하고 recursive case는 n-1, n-2로 줄여가면서 호출한다.

사실 피보나치 수열은 재귀로 구현하면 비효율적이다.

 

fibo(5)의 재귀 호출 과정을 보면 총 15번의 함수 호출이 일어난다. 이미 알고 있는 결과를 비효율 적으로 재귀 호출을 하기 때문이다. 

public class RecursionTest {
    static int fibo(int n) {
        count++;
        if (n <= 1) {
            return n;
        }
        return fibo(n - 1) + fibo(n - 2);
    }

    static int count = 0;
    public static void main(String[] args) {
        for(int i = 1; i <= 40; i++){
            count = 0;
            fibo(i);
            System.out.printf("fibo(%d) count = %d",i,count);
            System.out.println();
        }
    }
}

count 변수를 만들어서 40까지 fibo호출을 하고 호출 횟수를 확인해보면

n이 커질수록 호출 수는 매우 크게 증가하는 것을 볼 수 있다. 결국 메모리의 낭비가 크다는 것이고 최악의 경우엔 프로그램이 종료될 수 있기 때문에 재귀 함수를 사용할 때엔 어느 정도 결과가 예측이 가능할 때 사용하는 것이 좋다.