フィボナッチ数列

次のような末尾再帰の関数によってフィボナッチ数列を計算する場合を考えます

• 0番目のフィボナッチ数は0
• 再帰によってNが1になったらX2を返す

Fib (0,X1,X2) :- 0. 

Fib (1,X1,X2) :- X2.

Fib (N,X1,X2) :-　Fib(N-1, X2,X1+X2).

たとえば、７番目のフィボナッチ数を調べたいときは、

Fib( 7 , 0,1).

のようにします。 (２番目、３番目の引数は常に　初期値として0,1を渡す)
関数Fib内で再帰的じ自分自身を呼び出していますが、Nが正の整数であれば、N-1を繰り返すことで、N-1回目には1となります

このプログラム全体としての、関数のつながり具合を隣接行列に書いて調べてみます
...といっても、この場合は、一個しか関数が無いですけど。

列は呼び出される関数。関数名のみ書いてあります。
呼び出す場合は

関数	条件	Fib
Fib	N=0	終
Fib	N=1	終
Fib	それ以外	末尾再帰

関数が一個しか無いので、上のウログラムとえらく違いませんが、　Fib 　 それ以外の場合、で、ループしているのがわかります。今回は、呼び出すたびにN-1しているので、Nが正の整数ならば、必ずいつかは1となります。

コンピュータさんに自動で調べてもらうのは　ちょっとどうやるのかわかりませんが。