例年通りの進み方なんだけど、再帰処理の速度分析をするための説明を行う。 最初に、fact(N) , 配列の2分割積算 , fib(N) のプログラムを示し、 処理の流れのトレースを解説。 この後に、ハノイの塔の再帰方程式と数学的帰納法による証明を説明する。

ハノイの塔のディスクの移動回数を、 で表す。 ハノイの塔のルールより、N枚のディスクの移動には、(1)最下層の1枚の上にある、(N-1)枚を 隣に移動、(2)最下層の1枚を移動、(3)一旦隣に動かしておいた(N-1)枚を、目的の塔に 移動というステップを経由する。このため、 ただし また、最終的には、 が成り立つ。

ハノイの塔は、少ない枚数での移動を解いてみると、 が予想される。 この式が常に成り立つことを証明するため、枚についてこの予想が成り立つものと仮定する。 この時、枚については、

が成り立つので、

となり、 でも仮定が成り立つことが示される。よって、数学的帰納法により仮定は全ての 自然数について成り立つ。

この証明のような、式の中に自分自身が含まれるような方程式を、再帰方程式と呼ぶ。 再帰処理の速度予測では、これと同じように再帰方程式をたてる事ができる。

プログラムと再帰方程式

int fact( int N ) {
if ( N == 1 )
return 1 ;
else
return N * fact( N - 1 ) ;
}

このプログラムの処理時間は、N=1においては、if,==,return の一定の処理が行われるので、

Nが2以上では、if,==,*,-1,returnの処理と、fact()の再帰が行われる。よって、

この再帰方程式を、代入を繰り返しながらとけば、

が導き出せる。よって、階乗の再帰プログラムの処理時間のオーダは、 となる。