再帰を含むプログラムの速度分析の手法として、再帰方程式を説明。

• 先週説明をした fact() の再帰方程式を示し、一般解を示す。
• ハノイの塔のルールと、処理ステップ数がH(N)=2^N-1で示されることを、 数学的帰納法で証明。
• 再帰による2分探索のプログラムを示し、その再帰方程式を示し、 代入法で一般解の予測式を導き出す。
• 並び替えの処理速度を示すために、クイックソートは再帰が分かりにくいので、 マージソートにより O(N log N) を示す予定。 そのためにマージソートのアルゴリズムから、再帰方程式を示すまでを説明。

来週は、簡単な再帰プログラムより再帰方程式を示したり、速度の見積りなどを、 例題を通して理解確認を中心にしよう。