Rubyで再帰とメモ化を使用する方法

Rubyの再帰とは何ですか？

再帰関数は、最終目標に到達するまで自分自身を呼び出し続ける関数です（ベースケースとも呼ばれます）。 ）。各関数呼び出しの後、この基本ケースに向かって前進し、残りの作業量を減らします。

基本ケースに達すると、再帰が終了し、関数が戻り始めます。

ルビー再帰

再帰について学び始める典型的な例は、階乗数の計算です。

反復と再帰の両方を使用して、Rubyでこれを行う方法を見てみましょう！

数値の階乗を計算するには、1から目標数値までのすべての数値を乗算する必要があります。たとえば、5の階乗は次のとおりです。1 * 2 * 3 * 4 * 5 = 120 。

Rubyと再帰を使用してこれを行う方法を見てみましょう。

例 ：

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

def recursive_factorial(n)
  # Base case
  return 1 if n <= 1

  # Recursive call
  n * recursive_factorial(n-1)
end

この例では、階乗数を計算する2つの方法を示します。反復的かつ再帰的なソリューション。

再帰的ソリューションでは、作業する数（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回計算されます。これにより、より長いフィボナッチ数列を計算しようとすると、関数が非常に遅くなります。

ソリューション？メモ化。

メモ化：すでに行った作業の再利用

前のステップですでに行った作業を再利用できたら素晴らしいと思いませんか？

メモ化を使用してそれを行うことができます 。

高価な計算結果を保存するために、キャッシュを使用します。この場合、配列で十分です。

例 ：

@cache = [0,1]

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

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

最初に、結果がすでにキャッシュにあるかどうかを確認し、返された場合はそれを返します。そうでない場合は、計算を行って結果を保存します。

これにより、実行速度が大幅に向上し、はるかに大きなフィボナッチ数を計算できるようになります。

再帰の限界

読者が親切に指摘したように、再帰的なソリューションはSystemStackError: stack level too deepで失敗する可能性があります 入力番号が大きい場合（約7500、正確な数はシステムによって異なります）。

さらに大きな数を計算する必要がある場合は、反復解を使用する必要があります。

例 ：

memo = []

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

結論

再帰は素晴らしいですが、把握するのが難しい場合があります。今度はあなたの番です、練習は習得します！

気に入ったらこの投稿を共有して、私のニュースレターを購読してください🙂