このディレクトリの索引
http://toro.2ch.net/test/read.cgi/tech/1276873238/676
#  問題 
#  n番目のフィボナッチ数を求める関数f(n)を再帰的に定義した場合に 
#  この関数を呼び出す回数を求めよ。 
#  例 
#  n=10のときの関数fの呼び出し回数=109 
#  n=30のときの関数fの呼び出し回数=1664079 
# 

'n番目のフィボナッチ数を求める述語を再帰的に定義した場合にこの述語を呼び出す回数を求める'(_n番目,_フィボナッチ数,_呼び出す回数) :-
        '帰納を使い、フィボナッチ数を得る'(_n番目,_フィボナッチ数,1,_呼び出す回数).

'帰納を使い、フィボナッチ数を得る'(0,0,S,S).
'帰納を使い、フィボナッチ数を得る'(1,0,S,S).
'帰納を使い、フィボナッチ数を得る'(2,1,S,S).
'帰納を使い、フィボナッチ数を得る'(N,X,S_1,S) :-
        N > 2,
        N_1 is N - 1,
        N_2 is N - 2,
        S_2 is S_1 + 2,
        '帰納を使い、フィボナッチ数を得る'(N_1,X_1,S_2,S_3),
        '帰納を使い、フィボナッチ数を得る'(N_2,X_2,S_3,S),
        X is X_1 + X_2,!.