gaucheノート  末尾再帰(tail recursion)

階乗を計算する関数

gosh> (define (fact n)
(if (= n 1) 1
    (* n (fact (- n 1)))))
fact
gosh> (fact 10)
3628800

末尾(tail)に呼び出す(call)手続きが、乗算(→(* n (fact (- n 1))))のため、末尾再帰ではない


末尾再起で階乗を計算する関数

gosh> (define (fact-tailrec n acc)
(if (= n 1) acc
    (fact-tailrec (- n 1) (* n acc))))
fact-tailrec
gosh> (fact-tailrec 10 1)
3628800

末尾に呼び出す手続きが再帰になっているので、末尾再帰


変数名について
関数fact-tailrecの2つめの引数accはaccumulatorの略です。
以下のページなどを参考にし、accとしました。



末尾再帰に関して参照したURL:



フィボナッチ数

wikipedia:フィボナッチ数
http://upload.wikimedia.org/wikipedia/commons/8/83/FibonacciBlocks.png


通常の再帰で書く

gosh> (define (fibo n)
(cond ((= n 0) 0)
      ((= n 1) 1)
      (else
        (+ (fibo (- n 1)) (fibo (- n 2)))))
)
fibo
gosh> (map fibo '(0 1 2 3 4 5 6 7 8 9 10 11 12))
(0 1 1 2 3 5 8 13 21 34 55 89 144)



実行時間を測る

gosh> (time (fibo 5))
;(time (fibo 5))
; real   0.000
; user   0.000
; sys    0.000
5
gosh> (time (fibo 30))
;(time (fibo 30))
; real   0.233
; user   0.060
; sys    0.010
832040
gosh> (time (fibo 40))
;(time (fibo 40))
; real  25.001
; user   1.740
; sys    0.030
102334155



末尾再帰を調べるに至った経緯

この関数でフィボナッチ数を計算したときに、n=40前後からやけに遅くなったので、schemeだとこんなもんなのかなと思い、Cで同様のプログラムを書いてみました。しかし、同じくn=40前後から遅くなったので、フィボナッチ数の計算は結構時間のかかる処理なんだなあと思っていました。
ある日、再帰で書けないFORTRANは(→実装によりけりみたいです)どのようにしているのかと疑問に思ってネットで検索すると、以下のURLにあるようなプログラムがでてきて呆然としてしまいました。
http://d.hatena.ne.jp/fortran66/20090217/1234892881
まぁ、ふつうこう書きますよね。しかも高速!



末尾再帰で書く

gosh> (define (fibo-tailrecursion n acc prev-acc)
(cond ((= n 0) 0)   ;例外処理
      ((= n 1) acc) ;終了条件
      (else
        (fibo-tailrecursion (- n 1) (+ acc prev-acc) acc)))
)
fibo-tailrecursion
gosh> (define (fibo-tailrec n) (fibo-tailrecursion n 1 0))
fibo-tailrec
gosh> (map fibo-tailrec '(0 1 2 3 4 5 6 7 8 9 10 11 12))
(0 1 1 2 3 5 8 13 21 34 55 89 144)



末尾再帰で書いてみて

これは先ほどのFORTRANのプログラムと同じやり方をしていて、繰り返しのために無理に再帰を使っているという感じがします。
このように書く理由はなんでしょうか?僕が思いつく理由を挙げると以下の通りです。
 ・代入がないから
 ・schemer/lisperになりたいから
 ・schemer/lisperだから



変数名について
計算結果を入れる変数をaccとし、次の計算のため現在のaccの値を記憶する変数をprev-accとしました。初期値は、acc=1, prev-acc=0としたので終了条件はn=1のときです。n=0は、例外処理として定義しています。



実行時間を測る

gosh> (time (fibo-tailrec 5))
;(time (fibo-tailrec 5))
; real   0.000
; user   0.000
; sys    0.000
5
gosh> (time (fibo-tailrec 30))
;(time (fibo-tailrec 30))
; real   0.000
; user   0.000
; sys    0.000
832040
gosh> (time (fibo-tailrec 40))
;(time (fibo-tailrec 40))
; real   0.000
; user   0.000
; sys    0.000
102334155
gosh> (time (fibo-tailrec 1000))
;(time (fibo-tailrec 1000))
; real   0.001
; user   0.000
; sys    0.000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

参照したURL: