재귀함수 (Recursive Function)

재귀함수란?

재귀함수란, 함수 내부에서 자기자신을 다시 호출해 작업을 수행하도록 하는 함수를 말한다.

재귀함수를 통한 문제 해결은 귀납적인 사고로 문제를 해결하는 방법이다. 다시 말해 어떠한 문제를 재귀적으로 푼다는 것은, 해당 문제를 수학적 귀납법의 형태로 표현 가능하다는 이야기로도 볼 수 있다.

수학적 귀납법이란?

주어진 명제가 모든 자연수에 대해서 참임을 증명하기 위해, 주어진 명제에 대해서

1. 해당 명제가 n=1일때 성립함을 보인다.
2. 해당 명제가 n=k일때 성립한다고 가정한 후, n=k+1일때도 성립하는지 증명한다.

 

재귀함수를 구현할 때는 아래와 같은 역할을 하도록 하여야 한다.

1. 특정한 입력에 대해서는 자기자신을 다시 호출하지 않고 함수가 종료되어야 한다. (= Base Condition)
2. 모든 입력은 Base Condition으로 수렴해야 한다.
3. 위 1, 2를 만족하지 않는 경우에는 함수가 무한하게 돌도록 한다.

 

간단하게, 숫자 10부터 차례대로 10→9→8→…→1을 출력하게 하는 코드를 재귀적으로 작성한다면 다음과 같다.

def foo(N: int):
    if N < 1:
        return

    print(N)
    foo(N-1)

foo(10)

위 코드를 보면, 함수의 입력 값이 10일 때 입력 값을 출력하고 해당 값에서 -1을 한 값을 함수 자기자신의 입력 값으로 하여 다시 호출하고 있다. 결과적으로 N은 1보다 작게 되어, 해당 조건에서 함수는 종료되게 된다.

 

이번에는 유명한 문제 중의 하나인 피보나치 수열에서 특정 위치의 숫자를 구하는 문제를 재귀로 풀어보자. 피보나치 수열은 다음과 같은 점화식으로 정의되는 수열이다.

$$
F(0)=0, \; F(1)=1, \; F(N) = F(N-1)+F(N-2)
$$

def fibo(N: int):
    if N <= 1:
        return N
    return fibo(N-1) + fibo(N-2)

위와 같이 구현한다면, 이론적으로 모든 피보나치 수열의 값을 계산할 수 있다. 그러나, 실제 코드를 실행해보면 N이 커짐에 따라 실행시간이 기하급수적으로 커지는 것을 확인할 수 있다. 계산해보면 해당 코드의 시간복잡도는 $O(2^N)$ 정도가 된다.

 

fibo(5)를 계산하기 위해 fibo(4), fibo(3) 의 값을 구해야 하고, fibo(4) 의 값을 구하기 위해서는 fibo(3), fibo(2) 의 값을 구해야 하는 등 같은 값을 계산하는 함수를 반복적으로 실행해야 하기 때문이다.

 

해당 문제를 해결하기 위해서는, 계산한 값을 따로 저장해서 확인하는 Memoization과 같은 방식을 사용할 수 있는데, 이는 Dynamic Programming에서 더 자세하게 설명하고자 한다.

 

재귀(Recursion) vs 반복(Iteration)

재귀함수와 다르게, 반복문을 통한 접근은 명령을 반복적으로 수행하도록 하는 절차지향적인 알고리즘이다.

 

모든 재귀함수는 반복문으로 구현 가능하고 반대로 반복문을 재귀함수로도 구현하는 것이 가능하지만, 반복문에 비해서 재귀는 간결한 코드 구성을 가져 가독성이 좋다.

 

그러나, 재귀함수는 반복문에 비해 메모리 및 시간 복잡도적인 측면에서 손해를 보게 되며, 자기자신을 계속 호출하는 과정에서 메모리의 Stack 영역을 채우게 되므로 Stack Overflow를 발생할 수 있는 문제점이 존재한다.

 

즉, 재귀는 코드 구조가 간결한 대신, 시간/공간적인 측면에서 손해를 보게 된다. 따라서 문제 상황에 따라 적절하게 어떤 알고리즘을 통해서 해결할지 선택하는 것이 좋다.