再帰法とメモ化アルゴリズム

再帰を用いたフィボナッチ数列の計算と，メモ化による処理の最適化についての説明です．デモンストレーション付き．

フィボナッチ数列とは，f(n) = f(n-1) + f(n-2),  f(0) = 1,  f(1) = 1 で定義される数列です．その値を再帰的関数として定義します．ただし，単純な再帰的定義だと，同じ計算を何度も行うことになり，非効率です．そこで，メモ化という処理を加えます．デモンストレーションで，その効果を体験することができるでしょう．