Tweet関数の再帰と末尾再帰について学習したのですが、ちょうど某所で話題にあがってたので良いタイミングだなと思って書き留めておきます。再帰とは自分自身を参照するようなアクションのことです。再帰関数が一番に思い浮かびますが、定義や言葉遊びなどでも使われます。Preprocessor」を意味するものとなっています。PHPを展開したのにまたPHPが出てきます。階乗を計算する!さて自分自身を呼び出す関数のことを再帰関数と呼びますが、一例としてnの階乗を計算する関数を見てみましょう。nの階乗とはn!と書き、1からnまでを乗算した数です。1の階乗は1、2の階乗は1×2で2、3の階乗は1×2×3で6となります。同様に、nの階乗は1×2×...×(n-1)×nとなります。詳しく計算を注目してみます。(n-1)!×nnの階乗は(n-1)の階乗にnを掛けたもの、ということがわかるので(n-1)の階乗を計算しようとします。そのためには(n-1)-1の階乗、つまり(n-2)!が必要です。やって一つ手前の階乗を順番に計算していって、最終的に1の階乗に来た時にやっと1!が1であることにたどり着きます。階乗を計算するのに階乗が必要になる、立派な再帰ですね。(n-1)!階乗の定義はこれだけです。nの階乗を求めたいときには、nが1だったら1を、それ以外だったら(n-1)の階乗を計算してそれにnを掛けたものを返します。これをJavaで書くと次のようになります。factorial(n-1);}このように再帰関数は定義をそのまま表したものによく似ていることが多く、見た目にも何をしているのかわかりやすいのが特徴です。一つの例を見てみましょう。フィボナッチ数フィボナッチ数列は以下のように定義されます(一例)。1番目の数は12番目の数も1n番目の数は(n-1)番目と(n-2)番目の数を足したもの実際に計算してみると、1、1、2、3、5、8、13、...と続きます。そこでn番目の数を計算するプログラムはこうなります。fib(n-2);}イメージ通りだったでしょうか。効率を考える見た目もシンプルでわかりやすい再帰関数ですが、プログラム中で利用するにはいくつか問題があります。その内の一つが再帰から戻ってくるためにコールスタックを一つ消費する必要があるということです。コールスタックとは新たな作業を始めるためのスペースだと思ってください。人が並んで座れる長机だと考えるとわかりやすいかもしれません。このスペースがなくなるまで(つまり、隣に人が座れなくなるまで)再帰を続けるとスタックオーバーフローというエラーが起こります。このため無限に再帰関数を呼び続けることはコールスタックに制限がある以上簡単にはできません。さっきのfactorial関数ですが、nを計算するときに(n-1)の階乗の結果を待たなければなりません。このため、この関数はコールスタックを一つ消費して(n-1)!を計算しようとします。座ってる机の隣のスペースにに人を呼んで仕事を頼む感じです。(n-1)!を頼まれた人は、また別の人を呼んで(n-2)!の計算を頼みます。このように次々に仕事を次の人に頼んでいき、最終的に1!の計算を頼まれた人が1を計算結果として2!を計算しようとしている人に返します。すると2!の人は、返ってきた1と2を掛けた2を計算結果として3!の人に返します。このようにして次々と結果が返ってきて、最終的にはn!の人が(n-1)!の人から返ってきた結果にnを掛けて計算終了となります。このやり方ですと100!を計算しようとすると100人が必要になることになります。最初に仕事を頼んだ人は99!の人が計算を返すまでずっと待っていなければなりません。このような再帰は少し効率が悪そうに見えます。隣の人に計算を投げっぱなしにするここで発想の転換を行います。頼んだ仕事が返ってくるのを待つのではなくて、自分の仕事を終わらせた後、隣に人を呼んで、後の作業を任せてしまうのです。任せてしまった後は自分は席を立って構いません。このようにすれば、計算中に同時に長机に座っている人は一人だけです。再帰を呼んでもコールスタックを消費しないので無限に再帰することができます。これが末尾再帰の概念です。実際どのようにfactorial関数を末尾再帰にするかを考えます。最初の人が頼んだ計算結果を待たなければいけない理由は再帰を呼ぶ式に理由があります。関数の2行目を見てみましょう。factorial(n-1);作業を完了するには、返ってきた計算結果にnを掛ける必要があるので待っているわけです。ここを投げっぱなしにするにはどうすればいいでしょうか。勘の良い人は、関数を呼ぶだけにすればいいと気がつくかもしれません。factorial(...);だけにするのです。席をたつことができます。戻ってきたところで自分は何もすることがないですし。問題は...の部分をどうするかです。すれば隣の人に自分が計算した分を渡すことができるでしょうか。末尾再帰では補助変数としてaccumulatorというものがよく使われます。長机の例で言うなら、隣の人に渡す作業メモにそれまでの結果を書き記すようなものです。このaccを使ってfactorial関数を末尾再帰にしてみます。acc*n);}違いが分かりますか?この関数は2つの変数を受け取るようになっています。ひとつは今までどおり計算対象のn、もうひとつはaccです。関数の2行目に注目してください、return文が再帰呼び出しだけになっています。これなら隣の人に任せて自分は席をたつことができます。ロジックなるほど見た目は確かに末尾再帰になっているみたいですが、果たして計算結果は正しいのでしょうか。ロジックを見てみます。この関数はfactorial(n,1)のようにして呼び出します。nが1の時を考えると、この関数はaccを直接返します。factorial(1,1)=1となり、これは正しいです。それではfactorial(2,1)はどうでしょうか。今度はnが1なのでaccである2を返します。