末尾再帰についてちょっと夜更かしして末尾再帰について勉強。下の解説がかなり分かりやすいです。普通に再帰を書くと、再帰して呼び出した結果を利用して、値を計算するという流れになる。末尾再帰では、一番最後に自身を再帰する。最初に計算をして、その値を呼び出し先に伝えるという手法を取る。末尾再帰を用いると、現在使用しているスタック構造をそのまま再帰呼び出し先で再利用することができ、スタックの節約ができる。3.は末尾再帰の最適化と呼ばれているそうです。実際は、再帰が繰り返しループに置換されるみたい。末尾再帰の恩恵を受けるには、この最適化機能が使用する言語で提供されているかどうかが肝になるみたい。言葉の説明はこの程度にしておいて、いつものようにサンプルコードを。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)))これに対して、末尾再帰。n*acc);}かるく衝撃を覚えるほどのソースコードです。returnするときには、現在の関数のスタックは必要じゃなくなってますね。動的計画を彷彿とさせるような感じですが。この場合の計算イメージはこんな感じです。factorial2(5,1)factorial2(4,5)factorial2(3,20)factorial2(2,60)factorial2(1,120)factorial2(0,120)末尾再帰の場合は、最後に呼び出された関数の戻り値が答えになります。それぞれの関数は自分の役割を終えたら、後は呼び出し先に任せるよ。逆に普通の再帰の場合は、最初に呼ばれた関数の戻り値が答えになります。それぞれの関数は、自分の仕事を部下に任せるんですが、部下が仕事を終えるのをずっと待っていなくてはなりません。上の関数は、部下の部下の部下の・・・・部下の仕事が終って、自分のところまで結果が戻ってくるのを待たないといけないわけですね。