階乗を計算する関数
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としました。
- http://e-words.jp/w/E382A2E382ADE383A5E383A0E383ACE383BCE382BF.html
- wikipedia:アキュムレータ
- wikipedia:アキュムレーター
- http://stackoverflow.com/questions/33923/what-is-tail-recursion
- wikipedia:末尾再帰
末尾再帰に関して参照したURL:
- wikipedia:末尾再帰
- http://www.geocities.jp/m_hiroi/func/abcscm04.html
- http://www-ui.is.s.u-tokyo.ac.jp/~hara2001/scheme/material/2/2.mtd.mobile.5.html
- http://karetta.jp/book-node/gauche-hacks/004664
- http://stackoverflow.com/questions/33923/what-is-tail-recursion
フィボナッチ数
wikipedia:フィボナッチ数
通常の再帰で書く
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: