フィボナッチ数を、再帰バージョンと末尾再帰バージョンにしたときの比較です。
SICPの1.2.2 Tree Recursionと全く同じ問題ですね。
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2
再帰バージョン
iint fib(int n){ if (n == 0) return 0; else if (n == 1) return 1; else return fib(n-1) + fib(n-2); }
コンパイルした結果です。
普通の再帰関数の呼出になっています。
fib: addiu $sp,$sp,-40 sw $31,32($sp) sw $fp,28($sp) sw $16,24($sp) move $fp,$sp sw $4,40($fp) lw $2,40($fp) bne $2,$0,.L2 nop sw $0,16($fp) b .L1 nop .L2: lw $3,40($fp) li $2,1 # 0x1 bne $3,$2,.L4 nop li $2,1 # 0x1 sw $2,16($fp) b .L1 nop .L4: lw $2,40($fp) addiu $2,$2,-1 move $4,$2 jal fib # 再帰呼び出し nop move $16,$2 lw $2,40($fp) addiu $2,$2,-2 move $4,$2 jal fib # 再帰呼び出し nop addu $16,$16,$2 sw $16,16($fp) .L1: lw $2,16($fp) move $sp,$fp lw $31,32($sp) lw $fp,28($sp) lw $16,24($sp) addiu $sp,$sp,40 j $31 nop
末尾再帰バージョン
int fib_iter (int a, int b, int count) { if (count == 0) return b; else return fib_iter(a + b, a, count - 1); }
コンパイル後のアセンブラです。
末尾再帰の最適化がされており、関数呼び出しが無くなっています。
fib_iter: b .L4 move $2,$5 .L7: move $2,$3 addiu $6,$6,-1 .L4: move $3,$4 bne $6,$0,.L7 addu $4,$4,$2 j $31 nop
Exercise 2.18
ざっくり計算量を見積もる。
再帰バージョンの場合、f(n+1) = f(n) + f(n-1)で、nが増える度に関数呼び出し回数が約倍になります。なので、計算量はO(2^n) で近似できます。
末尾再帰バージョンの場合、,L7からはじめる5命令のループが実際に計算をしているところになります。計算量はO(n)で表現でき、 メモリにはアクセスしていないのでn × 5 [命令] で実行時間も見積もれます。
※再帰バージョンの計算量を厳密に求めると、(1+√5)/2のn乗になります。SICPの練習問題にもなっています。
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_thm_1.13
フィボナッチ数について
フィボナッチ数といえば、上の再帰→iteratorの変換だけでなく、メモ化の題材としてもよく使われます。
Higher-order PerlからPerlで最適化をしている例を紹介します。
http://hop.perl.plover.com/Examples/Chap5/
fib-0からfib-12まで順番に見てみましょう。
他にも不動点を使ってフィボナッチ数を求める話もあります。
http://www.kmonos.net/wlog/52.php#_0212050903
