実はHaskellの場合は遅延評価の影響で、末尾再帰にしても
fact' x y = fact' (x - 1) (x * y)
の(x - 1)とか(x * y)とかが評価されずに残り続けてしまうので、あまりうまみがなかったりっていう話もあります。
http://d.hatena.ne.jp/kazu-yamamoto/20091122/1258899591もしかしたら最近のGHCの状況では話は別かもしれないです。
そのへんはきっと誰かが教えてくれるはず。
というコメントがありました(arowMさん、ありがとうございました).
僕もこの記事を読んだ事がありましたが, 通常の再帰と末尾再帰で圧倒的に体感時間の差があったため, もうこの事を忘れて勢い余って投稿してしまいました.
もしかしたら末尾再帰を理解した事が嬉しすぎて時間が経つのが早く感じてしまったのじゃないかと思ったので, ちゃんと検証していきたいと思います.
検証開始
と言っても大それた事をするわけではありません. ただプログラムの実行時間を計るだけです.
測定に使うのはMacのtimeコマンドです.
引数にコマンドや実行ファイルを与えると, そのコマンドを実行して実行にかかった時間を教えてくれます.
ソースコード
では次に比較に使うプログラムです.
通常再帰
fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
main = print $ fib 35
末尾再帰
fib' :: Integer -> Integer
fib' n = fib'' n 1 1
where
fib'' n x y
| n == 0 = 1
| n == 1 = x
| otherwise = fib'' (n - 1) (x + y) (x)
main = print $ fib' 35
はい, 例によってまたフィボナッチ数列です.
好きなんですよ, フィボナッチ数列.
測定
ではこれから測定をしていきたいと思います.
測定に使ったマシンはMacBook Pro (Retina, 15-inch, Mid 2014)で, CPUは2.2 GHz Intel Core i7です.
まずは1回目
time ./fib1
14930352
./fib1 1.81s user 0.02s system 98% cpu 1.845 total
time ./fib2
14930352
./fib2 0.00s user 0.01s system 45% cpu 0.016 total
......圧倒的ですね
もう5回ずつやった結果の表が以下の通りです.
測定結果
| 回数 | 通常再帰(sec) | 末尾再帰(sec) |
|---|---|---|
| 1 | 1.845 | 0.016 |
| 2 | 1.910 | 0.015 |
| 3 | 1.893 | 0.008 |
| 4 | 1.842 | 0.009 |
| 5 | 1.870 | 0.008 |
| 6 | 1.892 | 0.008 |
| 平均 | 1.8753 | 0.0107 |
170倍以上の差が出ていますね.
正直ここまで差が出るとは思いませんでした.
ちなみにCPU使用率の平均は通常再帰が98.67%, 末尾再帰が57.33%でした.
結論
最新のGHCではどうやら末尾再帰最適化(?)が行われているっぽいですね.
もう少し詳しく調べてみようと思います.
追記
SaitoAtsushiさんから
これはそもそも同じ計算量ではないです。 式変形の段階でアルゴリズムが変わっています。 以前に似たような事例を見て解説記事を書いたことがあるので参考にしてください。
という指摘をいただきました.
実際に実行過程を追っていきたいと思います.
(申し訳ありません, 通常再帰は左側優先, 末尾再帰は右側優先で計算してしまいました. 計算結果と計算量に差はありませんので, ご了承下さい)
fib 5
↓
(fib 4) + (fib 3)
↓
(fib 4) + ((fib 2) + (fib 1))
↓
(fib 4) + ((fib 2) + 1)
↓
(fib 4) + (((fib 1) + (fib 0)) + 1)
↓
(fib 4) + (((fib 1) + 1) + 1)
↓
(fib 4) + ((1 + 1) + 1)
↓
(fib 4) + (2 + 1)
↓
(fib 4) + 3
↓
((fib 3) + (fib 2)) + 3
↓
((fib 3) + ((fib 1) + (fib 0))) + 3
↓
((fib 3) + ((fib 1) + 1)) + 3
↓
((fib 3) + (1 + 1)) + 3
↓
((fib 3) + 2) + 3
↓
(((fib 2) + (fib 1)) + 2) + 3
↓
(((fib 2) + 1) + 2) + 3
↓
(((fib 1) + (fib 0)) + 1) + 2) + 3
↓
(((fib 1) + 1) + 1) + 2) + 3
↓
(((1 + 1) + 1) + 2) + 3
↓
((2 + 1) + 2) + 3
↓
(3 + 2) + 3
↓
5 + 3
↓
8
引数5で22回の計算でした.
fib 5
↓
fib' 5 1 1
↓
fib' (5 - 1) (1 + 1) 1
↓
fib' (5 - 1) 2 1
↓
fib' 4 2 1
↓
fib' (4 - 1) (2 + 1) 2
↓
fib' (4 - 1) 3 2
↓
fib' 3 3 2
↓
fib' (3 - 1) (3 + 2) 3
↓
fib' (3 - 1) 5 3
↓
fib' 2 5 3
↓
fib' (2 - 1) (5 + 3) 3
↓
fib' (2 - 1) 8 3
↓
fib' 1 8 5
↓
8
同じく引数5で14回の計算でした.
これは差が出て当然ですね......
申し訳ありませんでした.
また近いうちに, 計算量が同じ関数を用いて試したいと思います.
SaitoAtsushiさん, ありがとうございました.