Tail Recursion

------------------------------------------------------------------------------------------------

출처: http://blog.kaisyu.com/2007/08/erlang-tail-recursion.html

------------------------------------------------------------------------------------------------

 

이번에는 Tail Recursion(우리 말로는 '끝 재귀' 또는 '꼬리 재귀'라고 부르더군요.)에 대해

더욱 깊이 공부를 하면서 피보나치 수열(Fibonacci Sequence)을 tail recursion으로

구현해보았습니다.

우선, 피보나치 수열 구현으로 들어가기에 앞서 tail recursion이 무엇인지 간단하게 이해하고 넘어갈

필요가 있겠습니다. Tail recursion은 재귀 호출의 특수한 형태로서, 다음 재귀 호출이 끝난 이 후

현재 함수 블럭 내에서 추가 연산을 할 필요가 없도록 구현하는 형태를 말합니다. 말이 좀 복잡한데,

예를 들어서 설명을 해보죠. (이해가 쉽도록 C 코드로 작성을 해봤습니다.)

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

이 코드에서 sum 함수는 1 부터 n까지의 합을 구하는 재귀 함수입니다. 'sum(3)'을 호출했다고 가정하고 그 수행 과정을 살펴보면 다음과 같습니다.

sum(3) → 

3 + sum(2)           ← (1)
  3 + (2 + sum(1))
    3 + (2 + (1))
  3 + (3)            ← (2)
6

함수 호출의 깊이를 들여쓰기로 나타내었는데, (1) 에서 보이는 것처럼 'sum(2)'를 호출하기 전에

'3 + '라는 추가 연산의 여지를 남겨두고 있습니다. 그렇기 때문에 'sum(2)' 호출 전에 현재 함수 블럭의

상태를 stack에 저장해야 할 필요가 있고, 이렇게 저장된 상태는 다시 거슬러 올라오면서 (2)에서 복원되어 최종 연산으로 이어지게 됩니다.

똑같은 일을 하는 함수를 tail recursion으로 구현해봅시다.

int sum(int n, int acc)
{
  if(n == 1)
    return (acc+1);
  return sum(n-1, acc+n);
}

이번 구현에서는 위에서는 없었던 acc라는 변수가 하나 더 추가되었습니다.

Tail recursion에서는 이것을 Accumulator라고 부르는데, 현재 함수 블럭에 추가 연산의 여지를

남겨두지 않기 위해서 저장해야 할 데이터를 보관하는 용도로 사용됩니다.

 

이 sum 함수에서는 각 호출 단계별 합을 저장하게 되죠. 실행되는 결과를 보면 좀더 쉽게 이해가 됩니다.

sum(3, 0) →

sum(2, 3)            ← (3)
  sum(1, 5)
    6                ← (4)
  6
6

위 결과에서 (3)을 보면 다음 'sum(2, 3)'을 호출하기 전에 저장해야할 상태가 없습니다.

그래서 (4) 이후에는 계속 동일한 값을 반환하는 것으로 호출이 마무리 됩니다.

 

이게 무슨 의미가 있냐구요?

Tail Recursion Optimization, 즉 tail recursion 형태에 대한 최적화가 적용될 경우

실제 실행 결과는 다음과 같아집니다.

sum(3, 0)
sum(2, 3)
sum(1, 5)
6

이 결과에서 보시는 바와 같이 다음 재귀 호출을 수행한 뒤 그 반환값으로 추가 연산을 하지 않기 때문에 stack에 현재 함수 블럭의 상태를 저장하지 않고 그 상태를 바로 바꾼 뒤에 함수 블럭 처음부터 다시 실행을 하는 것입니다. 즉, 함수 호출(call)이 아닌 분기(jump)가 사용된 것과 같다는 말이죠. 이것은 결국 for 또는 while과 같은 loop가 실행되는 구조와 유사하게 변한다는 말이 됩니다.

주변에서 흔히 사용하고 있는 주요 C/C++ compiler를 비롯해서 다른 많은 프로그래밍 언어에서

tail recursion optimization을 지원하고 있습니다. Erlang 역시 지원해주고 있지요.

최적화가 적용된 tail recursion 구현의 특징은 stack-overflow가 발생하지 않는다는 것과 실행 속도가

non-tail recursion(끝 재귀가 아닌 일반 재귀)에 비해 빠르다는 것입니다.

 

재귀 함수의 알고리즘 구조에 따라서 그 차이가 극명하게 나타날 수도 있습니다.

아래에서 보게 될 피보나치 수열이 바로 그런 예입니다.

자, 그럼 본론으로 들어갑시다.
피보나치 수열의 정의는 다음과 같습니다.

f(x) = f(x - 1) + f(x - 2)
단, f(0) = 0, f(1) = 1

수열을 구하는 함수의 정의 자체가 재귀로 되어 있습니다. 그 모양 그대로 Erlang에서 재귀 함수 형태로

구현할 수 있습니다. Tail recursion 방식을 사용하지 않고 구현해보면 다음과 같겠지요.

-module(fibo).
-export([fibo/1]).

%% Fibonacci sequence - Recursion version
fibo(0) ->
  0;
fibo(1) ->
  1;
fibo(N) when N > 1 ->
  fibo(N - 2) + fibo(N - 1).

그런데, 이 구현은 원칙적인 측면에서는 매우 직관적이고 바람직한 형태라고 할 수 있겠지만,

효율 측면에서는 매우 그렇지 못합니다.(제가 사용하는 HP nc8000 노트북에서 'fibo:fibo(100)'을

실행했더니 stack-overflow는 발생하지 않는데, 아무리 기다려도 답이 나오지 않더군요.)

자, 그러면 tail recursion을 적용해서 다시 한번 구현해봅시다.

-module(fibo2).
-export([fibo/1]).

%% Fibonacci sequence - Tail-recursion version
fibo(0) ->
  0;
fibo(1) ->
  1;
fibo(N) when N > 1 ->
  fibo(N, 1, 1, 1).

fibo(N, I, Acc1, Acc2) when (N > 1) and (I < N) ->
  fibo(N, I + 1, Acc2, Acc1 + Acc2);
fibo(N, N, Acc1, Acc2) ->
  Acc1.

처음 구현 형태에 비하면 모양이 꽤 복잡해보입니다. 피보나치 수열 특성 상 세 개의 accumulator가 사용되었습니다. 'I'는 index를, 'Acc1'과 'Acc2'는 각각 f(n-2)와 f(n-1)의 계산값 저장을 위해 사용합니다. 구현에 대한 더욱 구체적인 이해는 여러분들께 맡기겠습니다. 이 구현보다 더 깔끔한 구현이 있을 수도 있으니 직접 한번 도전해보시는 것도 좋지 않을까요? ;)

실행 결과는 다음과 같습니다.

[그림 1] fibo 실행 결과

정확한 시간을 측정해보지는 않았지만, 제 노트북(HP nc8000)에서 'fibo:fibo(40)'의 결과를 구하는 데

대략 3 ~ 4 초 가량이 소요됐으나, tail recursion으로 구현된 'fibo2:fibo(10000)'의 결과를 구하는 데에는

채 1 초도 걸리지 않더군요. Non-tail recursion 구현의 'fibo:fibo(100)'은 10 분 이상을 기다려도 답이

떨어지지 않아서 결국 중단하고 말았습니다. :-$