advanced
再帰処理の動的計画法への最適化
非効率な再帰的アルゴリズムを分析し、メモ化または動的計画法を用いて効率化するコードを生成します。
📝 プロンプトの内容
以下に示す非効率なフィボナッチ数列を計算する再帰関数 `fib(n)` を、メモ化（Memoization）を用いて計算量をO(n)に削減するようにリファクタリングしてください。
元のコード:
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
要件:
1. Pythonを使用すること。
2. コードには日本語のコメントを含めること。
3. 変更前と変更後の計算量についての説明を記述すること。
4. 副作用のない純粋な関数に保つこと。