末尾再帰について書きたい！
はい。
末尾再帰ですね。
末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。再帰にかかわらず一般に、そのような最後の呼び出しを末尾呼び出し （en:Tail call）という。呼び出しではなく、戻り先を保存しないジャンプに最適化できるという特徴がある（#末尾呼出し最適化）。
wikipediaにはこうありますけど、これで納得してる人ならここに来ていないと思うので噛み砕きます。
スタックフレームやコールスタックがどうのこうのなど、実際の小難しい概念は一切出さずに説明したいと思います。
伝言ゲーム(末尾再帰ではない再帰)
A,B,C,Dの4人が伝言ゲームをしています。
それぞれ左から[1][2][3][4]という数字が書かれた紙持っています。
Aさんに指令を出します。
指令
「全員の持ってる数字の総和を求めろ」
Aさんは考えた結果、Bさんに
「BさんCさんDさん全員の総和を教えて」と伝えました。
Bさんは、自分の数字はわかるが、CさんDさんの数字はわからないので
Cさんに
「CさんとDさんの総和を教えて」
と伝えました。
それを聞いたCさんは、Dさんに
「Dさんの数字を教えて」と伝えました。
とこのようにしてAさんは指令の答えである10を導き出すことができました。
これは末尾再帰ではありません。
何がいけないのか
この方法だと、Aさんは伝言ゲームがスタートしてからDさんにまで指令が届くのを待って、さらにもう一度自分の元に総和が届くのを待たないといけません。
つまりAさんはBさんに「総和を教えて」と言った後に、さらにその返答がくるまでその場にいないとダメなんです。
Bさんも、Cさんも同様です。
Dさん以外の全員が「質問をしてから、その答えを元にさらに計算する」と言う二つの仕事を与えられてしまっています。
これはよくありません。
伝言ゲーム(末尾再帰)
Aさんは考えました。
いかにすれば自分の仕事を減らせるか。
一番効率がいいのは、自分の数字を横の人に伝えるだけで終わることです。
Aさんの数字は1です。
それをBさんに伝えて、さらに指令も伝えれば、もうAさんの仕事はありません。
だって全ての情報をBさんに伝えてるからです。
Bさんが代わりに指令に答えればAさんの仕事は無くなります。帰っていいんです。
と言うわけでAさんはBさんにこういいました。
A「今から言う数字と自分の数字を足して、その数をDさんにまで伝えて言ってください。そしてDさんまで行ったらDさんはその数を答えてください」
Bさんは全て理解しました。
同様に自分も処理をしたら帰宅できる方法でCさんにタスクを投げました。
B「数字と自分の数字を足してね。Dさんまでよろしく」
Cさんも同じことをDさんに伝えて、
最終的に
Dさん「10です！」
となって、伝言ゲームが完了しました。
一度仕事を終えた人が、さらに何かを処理するためにその場に待機している必要が無くなりました。
これが末尾再帰です。
書きたくなかったけど、実際のコード
1から10までの総和を求めるコードを通常再帰と末尾再帰で書いてみます。
通常再帰
def sum(start: Int, end: Int): Int = {
def loop(i: Int):Int = {
if(i <= end) i + loop(i + 1)
else i
}
loop(start)
}
sum(1,10)
# 55
末尾再帰
def sum2(start: Int, end: Int): Int = {
@tailrec #末尾再帰なのかどうかをコンパイルにチェックしてもらえるアノテーション。末尾再帰でないとコンパイルエラーになる
def loop(i: Int, acc: Int):Int = {
if(i <= end) loop(i + 1, acc + i)
else acc
}
loop(start,0)
}
sum2(1,10)
# 55
上の例だと
i + loop(i + 1)が処理を待っている例ですね。
loop(i + 1)の結果を待ち続けて、その後iを足してあげる仕事が待ってますね。
下の例だと
loop(i + 1, acc + i)で全てを次のloop君に投げてます。
もう待っている必要はありません。
どうして末尾再帰じゃないとダメなの？
技術的な話をすると、関数を呼び出すと関数自身の情報やどこに戻るかなどを格納したスタックフレームが生成されます。
末尾再帰でないと、このスタックフレームがどんどん生成されていき、処理が完了するまで存在し続けます。
今回は4人の例だったからそこまで影響はなかったのですが、これが数万とかのレベルになってくるとそんな人数を収容できる施設はありません。
末尾再帰ですと、伝えた人はもう帰っていいので、人数は一人分で済みます。
なぜ二人(例でいうとAさん、Bさん)でなく、一人分でいいのかと言うと、同時に二人がその場に存在する必要すらないからです。
(一人が書き置きして、その人が帰った後に次の人がその書き置きを見れば済むから)
というわけで末尾再帰は、大変エコロな仕組みでした。