Rubyで再帰とメモ化をマスターする方法｜階乗・フィボナッチ数列の実例で学ぶ

Rubyにおける再帰（recursion）とは、関数が自分自身を呼び出し続け、最終的なゴール（ベースケース）に到達するまで処理を繰り返す手法です。各呼び出しごとにベースケースへ向けて少しずつ進み、残りの作業量が減っていきます。

ベースケースに到達した時点で再帰は終了し、今度は呼び出しとは逆順に関数が値を返していきます。

Rubyでの再帰の基本：階乗の計算

再帰を学ぶときの定番の例題が「階乗」の計算です。ここでは、反復処理（イテレーション）と再帰の2つの方法で階乗を求める方法を見ていきましょう。

ある数の階乗を求めるには、1からその数までのすべての整数を掛け合わせます。たとえば5の階乗は 1 * 2 * 3 * 4 * 5 = 120 となります。

def iterative_factorial(n)
  (1..n).inject(:*)
end

def recursive_factorial(n)
  # ベースケース
  return 1 if n <= 1

  # 再帰呼び出し
  n * recursive_factorial(n-1)
end

この例では、同じ階乗を反復版と再帰版の2通りで計算しています。

再帰版では、扱う数を1つずつ減らす（n-1）ことで処理を進めています。n が 1 以下になるとそれ以上の再帰呼び出しは行われず、次のような流れで結果が返ってきます。

return 1      # recursive_factorial(1)
return 2 * 1  # recursive_factorial(2)
return 3 * 2  # recursive_factorial(3)
return 4 * 6  # recursive_factorial(4)
return 5 * 24 # recursive_factorial(5)

Ruby開発者の多くは普段、反復処理を使った書き方を選ぶことがほとんどですが、再帰の仕組みを理解しておくことには依然として大きな価値があります。

フィボナッチ数列を再帰で求める

次に紹介するのも定番の例題、フィボナッチ数列です。この数列は、レオナルド・フィボナッチが理想的な条件下でのウサギの個体数の増え方をモデル化しようとした際に発見したとされています。

数列は「直前の2つの数を足し合わせる」というルールで計算されます。

例：

1, 1, 2, 3, 5, 8, 13, 21

Rubyでは次のような再帰関数で表現できます。

def fib(n)
  return n if n < 2

  fib(n-1) + fib(n-2)
end

この関数と範囲オブジェクトを組み合わせれば、最初の20個のフィボナッチ数も簡単に出力できます。

(1..20).each { |n| puts fib(n) }

しかし、ここに落とし穴があります。

この関数は必要以上の重複計算を行っています。たとえば fib(3) の計算は同じ処理の中で5回も繰り返されます。引数が大きくなるほど無駄な計算が急増するため、長いフィボナッチ数列を求めようとすると処理速度が極端に遅くなります。

その解決策こそが「メモ化」です。

メモ化：一度やった計算を再利用する

以前のステップで計算済みの結果をそのまま再利用できたら便利だと思いませんか？　それを実現するのがメモ化（memoization）です。

コストの高い計算結果を保存しておくためにキャッシュを使います。ここでは配列で十分です。

@cache = [0,1]

def fib(n)
  return @cache[n] if @cache[n]

  @cache[n] = fib(n-1) + fib(n-2)
end

まずキャッシュに結果が存在するかどうかを確認し、あればそれを返します。なければ計算を実行して、その結果をキャッシュに保存します。

これにより処理速度は大幅に向上し、より大きなフィボナッチ数も計算できるようになります。

再帰の限界：スタックオーバーフローに注意

再帰には限界もあります。入力する数が大きくなると（環境にもよりますが7500前後）、SystemStackError: stack level too deep というエラーが発生することがあります。これは呼び出しスタックの深さに上限があるためです。

さらに大きな数を計算したい場合は、反復処理による実装に切り替える必要があります。

memo = []

(0..n).each do |i|
  memo[i] = i < 2 ? i : memo[i-1] + memo[i-2]
end

この方法なら再帰呼び出しを行わないため、スタックの深さ制限を気にせず、大きな数でも安全に計算できます。

まとめ

再帰は強力な手法ですが、仕組みの理解に少し時間がかかることもあります。まずは階乗やフィボナッチ数列といったシンプルな例題から、実際にコードを書いて試してみてください。繰り返し練習することで必ず身につきます。