재귀

재귀(recursion)란 어떤 함수가 그 내부에서 자기 자신을 다시 호출하는 것을 말합니다. 간단한 예로 1부터 10까지의 합을 구하는 문제를 생각해보죠. 이 문제는 가장 단순하게는 반복을 통해서 해결할 수 있다는 생각이 들겁니다. 1부터 10까지 루프를 돌면서 각 값을 최종 결과에 계속 누적해주면 됩니다.

def sample(n):
    result = 0
    for i in range(n): 
        # i = 0, 1, 2, ... , n - 1 이므로 'i + 1'을 누적한다.
        result += i + 1
    return result

재귀를 이용해서 구현할 때에는 문제를 조금 다르게 바라볼 필요가 있습니다.

1. 1에서 n까지의 합을 구하는 것을 S(n)이라 표현한다면, S(1) = 1 이다.

2. S(9) = 1 + 2 + 3 + ... + 9 이므로, S(10) = S(9) + 10 이다.

   def sample(n):
    if n == 1:
       return 1
   return n + sample(n - 1)

3. 이 원리는 결국 어떤 수열의 점화식을 표현하는 것과 같습니다. 이 점화식을 코드로 옮기면 재귀로 구현한 코드가 됩니다.

sample(3)을 호출했을 때의 계산을 따라가 봅시다. sample(3) = 3 + (sample(2)) = 3 + (2 + (sample(1)) = 3 + 2 + 1 이 되는 것도 쉽게 알 수 있습니다.

재귀는 이처럼 어떤 문제를 수열의 점화식 형태로 만들 수 있거나, 큰 계산을 부분으로 나눌 수 있는 경우라면 쉽게 적용할 수 있습니다. 또 이런 경우에는 재귀로 작성된 코드가 문제의 풀이를 보다 명료하게 표현하게 된다는 장점이 있죠. 다만, 우리의 뇌는 반복으로 된 코드를 따라가기는 쉽지만 재귀로 된 코드는 따라가기 어렵기 때문에 문제가 있을 때 디버깅을 하기가 어려워질 수 있다는 단점도 있습니다.

수학적으로는 모든 재귀 연산은 반복 연산으로 변환할 수 있고, 그 역도 항상 성립한다는 것이 이미 알려져 있습니다. 하지만 컴퓨터는 함수를 호출할 때 내부적으로 '호출 스택'이라는 것을 만드는 데, 이 영역은 함수 내부에서 사용되는 지역 변수들이 위치하는 곳입니다. 재귀 호출의 경우에는 자기 자신을 호출하긴 하지만 호출 스택은 똑같이 계속해서 새로 생성해야 합니다. 즉 반복과 달리 메모리 자원을 더 많이 사용해야 하고, 많은 프로그래밍 언어에서 호출 스택은 최대 크기가 정해져 있는 경우가 많습니다. 즉 재귀 코드를 사용해서는 1~1,000,000 까지의 합은 구할 수가 없는 것입니다. (호출 스택 크기에 구애를 받지 않는 stackless python 같은 구현체에서는 가능합니다.)

재귀 코드를 작성하는 일반적인 원리는 다음과 같습니다.

1. 끝나는 지점을 먼저 정해야 합니다. 합계를 구하는 위 예제에서는 n = 1 인 경우가 여기에 해당합니다. 이렇게 재귀가 끝나는 지점을 기저 케이스(base case)라고 합니다. 기저 케이스를 정의하지 않으면 재귀가 무한히 반복되다가, 최대 깊이에 도달해서 프로그램이 크래시됩니다.
2. 문제를 점화식 형태로 표현하고, 재귀 호출 형태의 코드를 작성합니다.

꼬리 재귀

꼬리 재귀는 재귀 코드의 특별한 형태로 return func(...) 와 같이 재귀 호출의 결과를 그대로 리턴하는 것을 말합니다. 꼬리 재귀가 특별한 점이 있다면, 꼬리 재귀는 재귀 호출을 하는 순간부터 해당 깊이의 호출 스텍 프레임이 더 이상 필요하지 않다는 점입니다. 이 말은 컴퓨터 내부적으로 새로운 호출 프레임을 사용하지 않고, 함수의 지역변수를 모두 초기화하여 그대로 재사용할 수 있다는 것입니다. 이렇게 하면 호출 스택을 생성하는 비용이 들지 않기 때문에, 재귀 호출의 성능이 더 좋아지게 됩니다. 이것을 "꼬리재귀 최적화"라고 합니다. 꼬리 재귀 최적화는 사람이 하는 것이 아니라 컴파일러가 수행합니다. 기계적인 방식으로 재귀 형태의 코드를 반복문 형태로 바꾸는 작업이라고 생각하면 됩니다. 다만, 아직 파이썬은 꼬리 재귀 최적화를 지원하지 않습니다. 대신 사람이 할 수는 있죠. 재귀형태의 코드를 반복문으로 바꿔서 다시 작성하면 됩니다...

트램폴린

트램폴린은 재귀를 반복문 형태로 바꾸는 다른 기법입니다. 함수 내에서 재귀 호출을 하는 대신, 재귀 호출을 익명 함수나 클로저 형식으로 리턴하는 방식입니다. 단 이 형식을 사용하기 위해서는 함수 모양은 꼬리 재귀 모양이어야 합니다. n까지의 합을 구하는 함수를 트램폴린 방식으로 구현하면 다음과 같습니다.

def helper(n, s=):
    if n == 0:
        return s
    return lambda: helper(n - 1, s + n)


def sample(n):
    r = helper(n)
    while callable(r):
        r = r()
    return r

sample(10)
# >> 55

트램폴린은 실질적으로는 반복문을 실행하는 것이기 때문에, 재귀 형태의 코드를 반복문으로 변경하기 위해서 큰 변경을 할 필요가 없으면서 재귀의 최대 깊이 제한을 우회할 수 있는 방법입니다.