【アルゴリズム】再帰入門

この記事でわかること

• 再帰関数について
• 再帰関数の処理順序
• メモ化再帰

再帰とは

手続きの中で自分自身を呼び出すことを再帰呼び出しといい、再帰呼び出しを行う関数を再帰関数といいます。

具合例

int func(int n) {
  func(n - 1);
}

上記は無限にfunc関数を再帰呼び出する関数です。func関数の中で自分自身（func関数）を呼び出していることがわかります。これが再帰関数です。ただし、このままだと処理が終わらないので、処理を終了させる条件を処理内に定義する必要があります。

それでは上記を修正して、無限に再帰しないようにしていきます。

int func(int n) {
  if (n == 0) return 0;
  return func(n - 1);
}

// func関数の呼び出し
func(10);
// => 0

これで無限にfunc関数を再帰呼びだしされることは防げるようになりました。
これだけだと何も計算をしないので、さらに修正を加えて　１からNまでの総和を求める関数にしていきます。

int func(int n) {
　　if (n == 0) return 0;
　　return func(n - 1) + n; // + nを追加
}

// func関数の呼び出し
func(10);
// => 55

実行結果からわかるように, 1 - 10 の総和が求まることがわかります。

なぜそのような結果になるのか、処理順序を追って行きましょう。

0. func(10)を実行する

1. func(10 - 1)が呼び出される
  => func(9)が実行される

2. func(9 - 1)が呼び出される
  => func(8)が実行される

3. func(8 - 1)が呼び出される
  => func(7)が実行される

4. func(7 - 1)が呼び出される
  => func(6)が実行される

5. func(6 - 1)が呼び出される
  => func(5)が実行される

6. func(5 - 1)が呼び出される
  => func(4)が実行される

7. func(4 - 1)が呼び出される
  => func(3)が実行される

8. func(3 - 1)が呼び出される
  => func(2)が実行される

9. func(2 - 1)が呼び出される
  => func(1)が実行される

10. func(1 - 1)が呼び出される
  => func(0)が実行される
  => ここで初めて再帰呼び出しが終了する。　
  => ０が返却される

11. No.9で実行されたfunc(1)の計算が行われる
  => 1 + 0 // 0はfunc(0)の結果
  => 1が返却される

12. No.8で実行されたfunc(2)の計算が行われる
  => 2 + 1 // 1はfunc(1)の結果
  => 3が返却される

13. No.7で実行されたfunc(3)の計算が行われる
  => 3 + 3 // 3はfunc(2)の結果
  => 6が返却される
 
14. No.6で実行されたfunc(4)の計算が行われる
  => 4 + 6 // 6はfunc(3)の結果
  => 10が返却される

15. No.5で実行されたfunc(5)の計算が行われる
  => 5 + 10 // 10はfunc(4)の結果
  => 15が返却される

16. No.4で実行されたfunc(6)の計算が行われる
  => 6 + 15 // 15はfunc(5)の結果
  => 21が返却される

17. No.3で実行されたfunc(7)の計算が行われる
  => 7 + 21 // 21はfunc(6)の結果
  => 28が返却される
 
18. No.2で実行されたfunc(8)の計算が行われる
  => 8 + 28 // 28はfunc(7)の結果
  => 36が返却される

19. No.1で実行されたfunc(9)の計算が行われる
  => 9 + 36 // 36はfunc(8)の結果
  => 45が返却される

20. 最初に実行したfunc(10)の計算が行われる
  => 10 + 45 // 45はfunc(9)の結果
  => 55が返却される
  => func(10)の処理結果は55となる。

再帰関数でフィボナッチ数列

フィボナッチ数列
1 1 2 3 5 8 13 21 34 55 ・・・
これを再帰で実装すると以下のようになります。

class Fibonacci {
  static long calculate(int n) {
    if (n == 1 || n == 2) return 1;

    return calculate(n - 1) + calculate(n - 2);
  }

  public static void main(String[] args) {
    for(int n = 1; n < 10; n++) {
      System.out.println(n + ": " + calculate(n));
    }
  }
}

処理結果

1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55

メモ化再帰

メモ化再帰とは

関数の呼び出し結果を配列等に保持しておき、関数呼び出し毎に再計算するのを防ぐための手法です。

上記のフィボナッチ数列の処理をメモ化再帰を利用して処理効率を上げていきます。

class Fibonacci {
  // nの最大を999とする
  static long[] memo = new long[1000];

  static long calculate(int n) {
    if (n == 1 || n == 2) return 1;

    if (memo[n] != 0) {
      return memo[n];
    } else {
      long result = calculate(n - 1) + calculate(n - 2);
      memo[n] = result;
      return result;
    }
  }

  public static void main(String[] args) {
    for(int n = 1; n < 10; n++) {
      System.out.println(n + ": " + calculate(n));
    }
  }
}

一度行った引数nに対する計算処理を行わないように、配列に値を格納しておくことで重複した処理を省略しているのがわかります。

実際に手元で動作確認し、どのくらい処理速度が変わるのかを確認してみてください。
メモ化再帰の場合n = 50でもすぐに終わるはずです。逆に、メモ化再帰を利用しない場合、ものすごく時間がかかることがわかります。

以上、再帰入門でした。
自分自身の理解を深めるために記事にしましたが、誰かのためになったら幸いです。
間違っているところなどあればコメントください。