自分自身を二回以上呼び出すような再帰構造を持つ再帰関数に関しての末尾再帰というのはあまり考えないが、実は部分的に末尾再帰であるような例を考える事ができる。このような再帰の事を、部分末尾再帰と呼ぶ事としよう。(勝手に名付けた。一般的な呼び方があったら教えてください。)
このような関数ついて、正の整数 n を受け取り、フィボナッチ数列の n 番目を返す関数(fib 関数)を例にとり考えてみる。
Haskell でツリー構造再帰を使った fib 関数の定義は、以下のようになる。
fib :: Int -> Int fib n | n <= 1 = n | otherwise = fib (n - 1) + fib (n - 2)
この fib 関数は n が1以下であれば n をそのまま返し、そうでなければ fib (n - 1) と fib (n - 2) の和を返す。
つまり、n が0以上であるような fib (n + 2) は fib n + fib (n + 1) に簡約されるはずである。これが末尾再帰でないのは明らかだ。
しかし、ツリー構造の再帰であっても fib ... が fib ... の形に簡約されていれば外側の再帰に関しては末尾再帰になっていると言えるはずである。fib をその形に書き換えると、以下のようになる。
fib' :: Int -> Int -> Int fib' sum n | n <= 1 = sum + n | otherwise = fib' (fib' sum (n - 2)) (n - 1)
この fib' 関数は、元の n 以外にもとある時点での計算結果(和)を持っている。n が0以上であるような fib' sum (n + 2) は fib' (fib' sum n) (n + 1) に簡約されるので、外側の再帰に関して末尾再帰であると言える。
また、スタックで関数呼び出しを管理する普通の言語であれば、fib' は fib に比べて再帰一回分のスタック消費を基準とした時のスタック消費量が約半分になるはずである。スタックの深さが見えるように fib 7 と fib' 7 をそれぞれ可視化すると以下のようになる。(上が fib 7、下が fib' 7)
Permalink | コメント(3) | トラックバック(0) | 13:09