再帰関数とメモ化

再帰関数の基本概念

再帰関数とは、関数が自分自身を呼び出すプログラミング手法です。多くのアルゴリズムにおいて、問題を小さな同じ部分問題に分割して解くことができます。

再帰関数の構造

基底条件（再帰の終了条件）
再帰呼び出し（自分自身の呼び出し）

フィボナッチ数列の例

フィボナッチ数列は再帰関数の典型的な例です。各数が前の2つの数の和になっている数列です。

単純な再帰実装

def fibonacci(n)
  return n if n <= 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

この実装には重大な問題があります：

同じ計算を何度も繰り返す
時間計算量は O(2^n) と非常に非効率
n が大きくなると実用的でない

メモ化とは

メモ化は、計算結果をキャッシュして再利用することで、重複計算を防ぐ最適化手法です。

メモ化を使用したフィボナッチ実装

def fibonacci_with_memo(n, memo = {})
  return memo[n] if memo.key?(n)
  return n if n <= 1
  
  memo[n] = fibonacci_with_memo(n - 1, memo) + fibonacci_with_memo(n - 2, memo)
  return memo[n]
end

この実装の特徴：

時間計算量が O(n) に改善
空間計算量は O(n)
大きな n に対しても実用的

メモ化の効果的なケース

メモ化が特に効果を発揮するケース：

重複する部分問題が多い場合
各計算のコストが高い場合
入力の範囲が限定的な場合

具体例：

動的計画法の問題
パス探索アルゴリズム
組み合わせ最適化問題

メモ化が非効果的なケース

以下の場合、メモ化のオーバーヘッドが利点を上回る可能性があります：

重複計算が少ない、または存在しない場合
各計算が非常に軽い場合
メモリ使用量が重要な制約となる場合

非効果的な例

def factorial(n, memo = {})
  return memo[n] if memo.key?(n)
  return 1 if n <= 1
  
  memo[n] = n * factorial(n - 1, memo)
  return memo[n]
end

この階乗計算では、重複する部分問題が存在しないため、メモ化のメリットがありません。

空間コストの考慮

メモ化を実装する際は、以下の空間コストを考慮する必要があります：

メモリ使用量

メモ化テーブルのサイズは入力に比例
大きな入力に対してはメモリ不足のリスク
必要に応じてLRUキャッシュなどの制限付きキャッシュを検討

トレードオフ

時間効率 vs メモリ使用量
キャッシュサイズの制限 vs パフォーマンス向上
実装の複雑さ vs 保守性

実践的な考慮事項

実際の実装では以下を検討：

メモ化テーブルのスコープ（インスタンス変数 vs クラス変数 vs グローバル変数）
スレッドセーフティ
キャッシュの有効期限と更新戦略

まとめ

再帰関数は複雑な問題を分割して解くための強力なツール
メモ化は重複計算を防ぎ、大幅な性能向上が可能
ただし、問題の性質や制約に応じて適切に使用する必要がある
メモリ使用量とのトレードオフを常に意識する