再帰呼び出しの思い出。
大学一年のとき、計算機でフィボナッチ数列 1,1,2,3,5,8,13,...
X(n)=X(n-1)+X(n-2)
の n 番目を計算せよ、という課題が出た。自分は素直に
というようなコードを書いた。隣にいた同級生は再帰呼び出しを使って
int i, fibo[MAX];
fibo[0]=fibo[1]=1;
for(i=2;i＜MAX;i++) fibo[i] = fibo[i-1] + fibo[i-2];
と一見エレガントなコードを書いた。しかし盲点があった。前者はn に比例した時間で計算が終るのに対し、後者は２の n 乗に比例した計算時間がかかる！大きな値をいれたところでＦＭ１６βが反応しなくなり、彼はリセットを押すハメに。セーブしてなかったエレガントなコードはモクズと消えたのだった。。。
int fibo(int n){
if (n <= 2) return(1);
else return( fibo(n-1) + fibo(n-2) );
}
