末尾再帰について

ちょっと夜更かしして末尾再帰について勉強。。

下の解説がかなり分かりやすいです。

In traditional recursion, the typical model is that you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. In this manner, you don't get the result of your calculation until you have returned from every recursive call.

In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of "(return (recursive-function params))" (I think that's the syntax for Lisp). Basically, the return value of any given recursive step is the same as the return value of the next recursive call.

The consequence of this is that once you are ready to perform your next recursive step, you don't need the current stack frame any more. This allows for some optimization. In fact, with an appropriately written compiler, you should never have a stack overflow snicker with a tail recursive call. Simply reuse the current stack frame for the next recursive step. I'm pretty sure Lisp does this.

ざっくり日本語で言うと、

1. 普通に再帰を書くと、再帰して呼び出した結果を利用して、値を計算するという流れになる。
2. 末尾再帰では、一番最後に自身を再帰する。最初に計算をして、その値を呼び出し先に伝えるという手法を取る。
3. 末尾再帰を用いると、現在使用しているスタック構造をそのまま再帰呼び出し先で再利用することができ、スタックの節約ができる。

3.は末尾再帰の最適化と呼ばれているそうです。実際は、再帰が繰り返しループに置換されるみたい。末尾再帰の恩恵を受けるには、この最適化機能が使用する言語で提供されているかどうかが肝になるみたい。

とりあえず、言葉の説明はこの程度にしておいて、いつものようにサンプルコードを。

int factorial(int n) {
  if (!n)
      return 1;
  return n * factorial(n-1);
}

上のコードは階乗を求めるソースです。普通は、上のように書くでしょう。。

これは、factorial(n-1)の値を求めて、それにnをかけてreturnするという形になっています。つまり再帰呼び出しの結果を用いて計算を実施したのち、returnという形です。

計算されるイメージはこんな感じ。

factorial(5)

5*factorial(4)

5*(4*factorial(3))

5*(4*(3*factorial(2)))

5*(4*(3*(2*factorial(1))))

5*(4*(3*(2*1)))

これに対して、末尾再帰。

int factorial2(int n, int acc=1) {
   if (!n)
       return acc;
   return factorial2(n-1, n*acc);
}

かるく衝撃を覚えるほどのソースコードです。returnするときには、現在の関数のスタックは必要じゃなくなってますね。。ちょっと動的計画を彷彿とさせるような感じですが。。

この場合の計算イメージはこんな感じです。

factorial2(5,1)

factorial2(4,5)

factorial2(3,20)

factorial2(2,60)

factorial2(1,120)

factorial2(0,120)

末尾再帰の場合は、最後に呼び出された関数の戻り値が答えになります。それぞれの関数は自分の役割を終えたら、後は呼び出し先に任せるよ。ってイメージです。

逆に普通の再帰の場合は、最初に呼ばれた関数の戻り値が答えになります。

それぞれの関数は、自分の仕事を部下に任せるんですが、部下が仕事を終えるのをずっと待っていなくてはなりません。一番上の関数は、部下の部下の部下の・・・・部下の仕事が終って、自分のところまで結果が戻ってくるのを待たないといけないわけですね。。これは大変。（面倒くさそう。。日本のソフト開発の主流であるウォータフォールモデルみたい。。）

残念ながら、私が使用しているC++環境では末尾再帰の最適化はサポートされていないようです。末尾再帰を使って書いた関数（総和を求める関数）でもスタックオーバーを起こしました。。

引用サイト：　http://stackoverflow.com/questions/33923/what-is-tail-recursion