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.
ざっくり日本語で言うと、
- 普通に再帰を書くと、再帰して呼び出した結果を利用して、値を計算するという流れになる。
- 末尾再帰では、一番最後に自身を再帰する。最初に計算をして、その値を呼び出し先に伝えるという手法を取る。
- 末尾再帰を用いると、現在使用しているスタック構造をそのまま再帰呼び出し先で再利用することができ、スタックの節約ができる。
上のコードは階乗を求めるソースです。普通は、上のように書くでしょう。。
int factorial(int n) {
if (!n)
return 1;
return n * factorial(n-1);
}
かるく衝撃を覚えるほどのソースコードです。returnするときには、現在の関数のスタックは必要じゃなくなってますね。。ちょっと動的計画を彷彿とさせるような感じですが。。
int factorial2(int n, int acc=1) {
if (!n)
return acc;
return factorial2(n-1, n*acc);
}
引用サイト: http://stackoverflow.com/questions/33923/what-is-tail-recursion
0 件のコメント:
コメントを投稿