반복보다 재귀를 좋아하는 사람으로서, 재귀의 문제점 중 하나인 콜 스텍 오버플로우는 반드시 짚고 넘어갈 문제이다.

재귀에서 콜 스텍 오버플로우는 왜 발생하는가? 아래 함수를 보자.

// 실제로 컴파일 해본건 아니라 오류가 있을수도
int sum(int n) {
  if (n == 1) then return 1
  else return n + sum(n - 1);
}

int fibo(int n) {
  if (n == 1) then return 1
  else if (n == 2) then return 1
  else return fibo(n - 1) + fibo(n - 2);
}

return n + sum(n - 1)나 return fibo(n - 1) + fibo(n - 2)에서 보듯이 부르는 함수(caller)가 끝나기 전에 불리는 함수(callee)가 호출됨을 알 수있다. 먼저의 함수가 끝나지 않았는데도 불구하고 다음 함수가 호출됨으로서, 부르는 함수의 메모리 영역이 풀리기 이전에 불리는 함수의 메모리 영역이 잡힌다. 따라서 메모리에 함수의 메모리 공간들이 쌓이고 쌓여 나가다가, 공간이 부족하면 stackoverflow를 뱉는 것이다.(내 경우 c에서는 세그멘테이션 폴트가 떴다.)

즉, 불린 함수의 입장에서 부른 함수의 메모리(로컬 변수 및 그 부른 함수를 또 부른 함수의 위치(레퍼런스)를 저장한다)를 해방할 수 없기 때문에 메모리가 부족해진다.

이를 해결하는 방법은, 단순히 생각하면 다음 함수가 불릴때 이전 부르는 함수를 해방해주면 된다. 어떻게? 부르는 함수가 다음 함수를 부르는 시점 이후로 더이상 아무런 작업을 하지 않게하고, 이를 컴파일러가 알도록 해주면 된다.

// 꼬리재귀
#include <stdio.h>
#include <assert.h>

int gcd(int n, int m) {
  assert(n>0 && m>0);
  if (n == m) { return n; }
  else if (n > m) { return gcd(n-m, m); }
  else { return gcd(m-n, n); }
}

int main(void) {
  int a = 540000001;
  int b = 2;
  printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b));
  return 0;
}

함수 gcd를 보면 return gcd(n-m, m), return gcd(m-n, n)에서 드러나듯이 다음 함수가 호출된 이후 아무런 작업 없이 그 값을 가지고 리턴한다는 것을 알 수 있다. 이전의 부른 함수가 하는 일이라곤 불린 함수가 반환한 값을 그대로 다시 넘겨주는 것 뿐이다. 이 경우에는 부르는 함수가 가진 메모리 값들이 아무런 필요가 없다. 따라서 논리적으로 메모리 오버플로우를 방지할 수 있는 조건이 된다.

다만 코드를 라인바이라인으로 있는 그대로 읽어 보면, 바로 리턴하도록 짜던가 아니던가 결국 부르는 함수가 끝난 건 아니므로 메모리 공간에 쌓여있어야 할 것 같다. 코드를 줄대로 그대로 읽으면 그게 맞다. 아직 중괄호가 끝나지 않았으니까 메모리 공간이 잡혀있어야만 한다.

하지만 컴파일러가 이를 잘 해석해서 최적화를 해주기에 메모리 오버플로우를 방지할 수 있는 것이다. gcc는 C컴파일 시 -O2 옵션을 주어야 이를 해준다. OCaml 같은 경우는 기본적으로 컴파일러가 이 작업을 한다. 즉 꼬리재귀 최적화는 코드를 작성하는 방법의 문제이자 컴파일러 기능의 문제이기도 하다. 그렇기에 꼬리재귀는 단지 코드 작성자가 주의깊게 작성한다고만 해결되는게 아니고, 컴파일러가 이를 지원하는지, 지원하면 어떻게 해야 적용되는지를 알아야 해결되는 문제이다.

구현의 아이디어는 위에서 설명한 바와 같고, 실제적인 컴파일러 차원의 구현은 다음과 같은 방식으로 이루어진다. 어떤 불린 함수는 부른 함수의 위치에 대한 정보를 저장해야한다(어셈블리를 까보면 돌아갈 라인의 메모리 주소를 인자와 함께 메모리 공간에 달고 들어간다). 그래야 리턴된 후에 그 위치로 다시 돌아가서 다음 코드를 수행할 수 있기 때문이다. 이렇게 깊게깊게 불려들어가는데, 꼬리재귀 최적화를 시도하여 불린 함수가 반환된 이후 아무런 작업이 없을 때는, 불린 함수가 자신이 돌아가야 할 자리(부른 함수가 호출한 바로 그 위치) 대신, 부른 함수가 호출 당했던 자리, 즉 부른 함수를 부른 함수의 자리를 저장한다. 즉 callee가 caller의 caller로 돌아가도록 한다.

이게 연속적으로 계속해서 소급해 올라가면서 적용되기 때문에, 결국 제일 깊은곳에서 불리는 최종 함수 호출이 기억하는 돌아갈 자리는, 최초 함수의 호출 자리 가 된다. 따라서 이전 함수들이 차지했던 공간들은 다음 함수를 부르는 순간에 해방(free)될 수 있다. 즉, 제일 깊은 곳의 함수에서 리턴된 값이 최초 함수 호출 위치로 다이렉트로 넘어간다.

더 단순하게 이 현상을 보자면, 부른 함수가 불린 함수에 의해 대체되는 것과 마찬가지이다. gdc의 예시를 잘 보자. 이전 함수는 다음 함수에 의해 의미적으로 대체된다. 따라서 이전 함수의 메모리공간은 불필요한 것이 되고, 최적화가 가능해진다.

따라서, 다음 함수가 리턴된 후에 아무 작업도 하지 않도록 하는 것을 꼬리 호출(tail call)이라 하고, 이런 함수 구조를 꼬리 재귀(tail recursion)라고 하며, 이런 함수를 꼬리재귀함수(tail recursion function)라고 용어를 정리할 수 있다.

심화

첫번째 예시의 sum같은 경우는 어떻게 꼬리호출 형태로 변경할 수 있을까? 다음 코드를 보자.

int sum(int n) {
  if (n == 1) then return 1
  else return n + sum(n - 1);
}

이 경우 꼬리재귀구조를 방해하는 건 return n + sum(n - 1)의 n +이다. n이 무엇인지 기억하고 있어야 하기 때문에 기존 함수의 메모리 영역을 풀어 줄 수 없다. 이 부분이 없으면 최적화가 가능할 것이다.

1에서 시작하여 n까지 더한다는 의미의 sum 함수를, 조금 정의를 변경해보자. 1부터 시작하여 n까지 더하고, m이란 값을 여기에 더 더하는 함수를 sum2로 정의하자. sum(n)은 sum2(n, 0)과 같게 된다.

여기서 포인트는, sum2(n, 0)이 sum2(n - 1, 0 + n)으로 대체 될 수 있다는 점이다. sum2(n - 1, 0 + n)은 또 sum2(n - 2, 0 + n + (n - 1))과 동일하다. 이렇게 점점 내려가면, 결국 sum2는 sum2(1, …)으로 대체된다. 대체 가능성은 꼬리재귀의 가능성을 말해준다. 두번째 인자인 0 + n + (n - 1) 요 부분은 다음번 대체 이전에 순서상 먼저 계산된다(인자는 lazy하게 계산되지 않는다. 아마 lazy하게 된다 하더라도, 인자는 하나의 식이므로 메모리 오버플로우는 나오지 않을 것…같다(확실친 않음)). 그결과, 아래와 같은 코드가 성립한다.

// 꼬리재귀 변환
int sum2(int n, int m) {
  if (n == 1) then { return m + 1; }
  else { return sum2(n - 1, m + n); }
}

다음 함수 호출의 결과값이 그대로 부른 함수의 리턴값으로 넘어가는 구조가 됨을 알 수 있다. 꼬리재귀함수의 조건을 갖춘 것이다.

Q1. 모든 재귀 함수는 꼬리재귀함수로 변환이 가능한가? 이는 증명가능한가?

Q2. 모든 재귀함수는 반복문으로 대체될 수 있다고 한다. 이는 어떻게 증명하는가?