再帰呼び出しを含む処理の、速度分析の説明として、ハノイの塔とマージソートを 説明する。

ハノイの塔

ハノイの塔は、３本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。 ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 ということが予想される。

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。 これより、

ということが言える。 ディスクが 枚で、予想が正しいと仮定すると、 枚では、

となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

マージソートの処理速度分析

最も高速なソートアルゴリズムとして、クイックソートがあげられる。 しかし、説明が分かり難いので、同じ処理速度のオーダとなる、 マージソートの分析で説明する。

マージソートのアルゴリズムは、

• データが１件の時は、そのまま。
• それ以上の件数では、
  • データを中央で２分割して、それぞれをマージソートを行う。
  • 出来上がった２つのデータ列を、先頭から２つを比較し小さい方から移し替える。

この方式であれば、再帰方程式として、以下の式が示される。

N=1,2,4,8,…と、代入を繰り返すと、処理時間は、 であることがわかる。