エンジニアとしての基礎力強化の一環で、アルゴリズムの学習をしています。その中で出てきた「再帰」の理解に苦戦したので、忘れないようにまとめます。

再帰とは？

再帰とは、「関数の中で自身を再度呼び出すことで、繰り返し処理を実現する」アルゴリズムです。

これだけじゃ分かりにくいので、具体例ベースで考えます。

3の倍数を再帰的計算で求める

たとえば、3 × 5 を例に考えます。3 × 5 は以下のように表せます。

3 × 5 = (3 × 4) + 3

さらに、3 × 4 の部分は以下のように表せます。

3 × 5 = {(3 × 3) + 3} + 3

ここまでは誰でも理解できるはず。

では、3 × n の場合はどうなるか？

↑と同じことを n を使って表現します。

3 × n の結果を multiply_of_three(n) とした場合、次のように記述できます。

multiply_of_three(n) = multiply_of_three(n - 1) + 3

同様に 3 × (n – 1) の結果を multiply_of_three(n - 1) とした場合、次のように記述できます。

multiply_of_three(n - 1) = multiply_of_three(n - 2) + 3

この式に先ほどの3 × 5 の例より n = 5 と仮定すると以下のように計算されます。

3 × 5 の結果　＝　3 × 4 の結果　＋　3
↓

3 × 4 の結果　＝　3 × 3 の結果　＋　3
↓

3 × 3 の結果　＝　3 × 2 の結果　＋　3
↓

3 × 2 の結果　＝　3 × 1 の結果　＋　3
↓

3 × 1 の結果　＝　3 × 0 の結果　＋　3

これが再帰的計算です。

Rubyのコードで multiply_of_three メソッドを定義した結果がこちらです↓

def multiply_of_three(n)
  multiply_of_three(n - 1) + 3
end

メソッドの中で自分自身を呼び出すことで、ループを表現するんですね。

再帰的計算の注意点

じつは、先ほどの実装だけでは不十分です。なぜなら、繰り返しのループが永遠に続いてしまうからです。

今回のように3の倍数を求める場合、ぼくたちは 5 → 4 → 3 → 2 → 1 → 0 と n = 0 に到達した時点で終了だと認識できますが、コンピュータにはその判断ができません。

そのため、ループを終わらせる処理（＝ ベースケース）を書く必要があります。

def multiply_of_three(n)
  return 0 if　n == 0  # ベースケースを記述

  multiply_of_three(n - 1) + 3
end

このように記述することで、処理の流れは次のようになります。

3 × 5 の結果　＝　3 × 4 の結果　＋　3
↓

3 × 4 の結果　＝　3 × 3 の結果　＋　3
↓

3 × 3 の結果　＝　3 × 2 の結果　＋　3
↓

3 × 2 の結果　＝　3 × 1 の結果　＋　3
↓

3 × 1 の結果　＝　3 × 0 の結果　＋　3
↓

3 × 0 の結果　＝　0　 → ここがベースケース！

このように、ベースケースを用意しないとコンピュータは無限ループに陥ってしまうため、かならずベースケースを用意しましょう。

まとめ

再帰とは、関数の中で自分自身を呼び出すことで繰り返し処理を表現するアルゴリズムであること、再帰的計算にはかならずベースケースを用意して無限ループに陥るのを防ぐ必要があることを学びました。