再帰を含む処理の処理速度の見積りの例として、 階乗の再帰の速度見積り、２分探索の再帰版の速度見積り、 ハノイの塔の処理速度の速度見積りを示す。

ハノイの塔の再帰方程式と数学的機能法

N枚の板の移動は、以下の手順で実行するため、移動回数を H(N) で表すと、 以下のような再帰方程式が示される。

• 底の1枚を残して、N-1枚を一旦別の柱に移し、
• 底の１枚を目的の柱に移動、
• 別の柱に移しておいた N-1枚を移動、

H(1) = 1               (N=1の時)
H(N) = 1 + 2 * H(N-1)  (N>1の時)

少ない枚数のハノイの塔を解くと、処理速度 H(N) では、以下の仮定が成り立つ。

H(N) = 2^N - 1

よって、数学的帰納法で証明すると、

・H(1) で、仮定が正しいのは明らか。
N = k の時、仮定が正しいならば、 N=k+1の時、
・H(k+1) = 1 + 2 * H(k)         # ルールより
= 1 + 2 * (2^k - 1)    # N=kの時の仮定を代入
= 1 + 2^(k+1) - 2
= 2^(k+1) - 1
であり、仮定は k+1 でも成り立つ。
よって数学的帰納法により、N≧1で成り立つ。

フィボナッチ数の再帰プログラムの処理速度の見積り

講義では、フィボナッチ数の処理速度の見積りは示さなかったが、 自主的な取り組みをしてみることと伝えておいた。 ここで、ヒントを示す。

• ビネの公式

フィボナッチ数の再帰処理より、成り立つ再帰方程式
T(1) = Ta
T(2) = Ta
T(N) = Tb + T(N-1) + T(N-2)
代入法による一般式の予測
T(1) = Ta , T(2) = Ta
T(3) = Tb + Ta + Ta
T(4) = Tb + (Tb + 2Ta) + Ta = 2Tb + 3Ta
T(5) = Tb + (2Tb+3Ta) + (Tb+2Ta) = 4Tb + 5Ta
以下の一般式を仮定する。
T(N) = (Ta + Tb) * fib(N) - Tb
上記一般式は、N=1,2 で仮定が成り立つのは明らか。
N≦k で仮定が成り立つとすれば、N=k+1 の時、
T(k+1) = Tb + T(k) + T(k-1)
= Tb + {(Ta + Tb) * fib(k) - Tb} + {(Ta + Tb) * fib(k-1) - Tb}
= (Ta + Tb){ fib(k) + fib(k-1) } - Tb
= (Ta + Tb) * fib(k+1) - Tb
よって、k+1 でも仮定が成り立つことが確認できた。

この一般式より、フィボナッチ数の再帰呼出し処理の速度のオーダーは、 ) となる。 ビネの公式より、 )

# くそ、授業中に記憶だけで書いた(1+sqrt(5))/2 の値が違ってた….