再帰関数とメモ化

再帰関数とメモ化

再帰関数の基本概念

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

再帰関数の構造

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

フィボナッチ数列の例

フィボナッチ数列は再帰関数の典型的な例です。各数が前の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 グローバル変数）
• スレッドセーフティ
• キャッシュの有効期限と更新戦略

まとめ

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