先週までのハノイの塔やらの再帰方程式は、実際のプログラムとは 離れていると感じている学生が多いと思われるのも問題なので、実際的な例にて 再帰方程式の説明。

最初に、先週の授業で説明のできなかったフィボナッチ数列の場合。 再帰によるフィボナッチ数の関数の処理速度のオーダーを求める。 代入法による予想で求めた一般式が、数学的帰納法により正しいことを証明する。 つもりであったが、証明の前準備をしてなかったので、授業中に説明を私自身の 宿題とする。 フィボナッチ数の説明

このあと、マージソートプログラムが、O(N log N)であることの説明として、 マージソートプログラムの概念を示し、再帰方程式を示し、代入法により証明を行 う。

余った時間には、来週からのヒープメモリの解説の前準備として、 名前列の2次元配列への記憶で、可変長配列が使えないC言語では、 最大データに合わせて配列宣言を行うと、 メモリの使用効率に無駄が発生することを説明。