注意：github に移動しました。
再帰ドリル(1)を読んでいない人は、先に読むこと。
等差数列の和
差が1の等差数列の和を素朴な再帰で実現すると以下のようになった。
soap 0 = 0 soap n = soap (n-1) + n
プログラミング言語の内部をよく知っている人は、何度も関数を呼び出すのでスタックが溢れてしまわないか心配だろう。実際、この手の関数はスタックが溢れてしまう可能性がある。
そもそも、この程度の計算はループで実現できるはずで、スタックは溢れて欲しくはない。幸いにも、素朴な再帰を「末尾再帰」(tail recursion)という形に直すと、スタックが溢れなくなる。
末尾再帰の形をした関数とは、分岐の末端の最後で自分自身を呼び出す関数のことである。上記の関数は末尾再帰ではない。(注意：この説明は正格評価を仮定している。) 以下のように二項演算子を関数に直して前に出すと、よく分かる。
soap 0 = 0 soap n = (+) (soap (n-1)) n
soap が最後に呼び出すのは、(+) であるから末尾再帰ではない。幸い、ループできることを実装している再帰関数は、「引数を増やすことで末尾再帰に直せる」。
soap n = soap' n 0 soap' 0 acc = acc soap' n acc = soap' (n-1) (acc + n)
増やされた引数は「蓄積変数」(accumulator)と呼ばれる。蓄積変数に結果を蓄えていき、最後にそれを返す訳だ。
関数型言語を名乗るプログラミング言語であれば、再帰の末尾呼び出しは、単なるジャンプ(goto)に置き換えられるので、スタックは溢れない。(まぁ、この辺りが微妙な関数型言語もあるけれど。) これを「末尾呼び出しの最適化」(TCO: tail call optimization)と言う。
階乗
階乗を素朴な再帰で実現した
fact 1 = 1 fact n = fact (n - 1) * n
は、以下のように変形できる。
fact n = fact' n 1 fact' 1 acc = acc fact' n acc = fact' (n - 1) (acc * n)
掛け算
階乗を素朴な再帰で実現した
mul m 1 = m mul m n = mul m (n - 1) + m
は、以下のように変形できる。
mul m n = mul' m n m mul' m 1 acc = acc mul' m n acc = mul' m (n - 1) (acc + m)
蓄積変数の初期値に注意。
