再帰呼び出しの含まれる処理の、分析について説明を行う。 再帰に慣れていない人のために、fact(N) , pyra(N) , fib(N) のプログラムを示し、 適当な引数での実行結果を答えて貰う。

fact(N):階乗のような再帰であれば、処理の時間も繰り返しになることから、代入法で 簡単に説明ができる。しかし、フィボナッチ数列fib(N)であれば、自身の呼び出し回数も 簡単には説明ができない事例。ということで、まずはハノイの塔の処理ステップの証明を、 (1) 代入法による一般解の予想、(2)数学的帰納法を交えてた証明について 説明を行う。

最後に、フィボナッチ数列の再帰の処理時間を、代入法により示し、ピネの公式より オーダを示す。