7.Recursive

再帰とは

再帰（Recursion）とは，再帰的な構造を持つアルゴリズムのことです。再帰的な構造とは，自分自身の定義の中に，自分自身を含む構造です。再帰の代表的な例として階乗やユークリッドの互除法の再帰的定義がよく用いられます。それぞれについて学習していきます。

階乗

整数nの階乗は記号!を用いてn!と書きます。実際の計算は次のように行われます。

n! = n × (n-1) × (n-2) × ... × 2 × 1 

この式を再帰的定義に書き換えると，次のようになります。

n! = n × (n-1)!  (ただし，0!=1)

次の階乗のsketch、Factorial.pdeは10の階乗を行う例

1. 繰り返し構文を使ったメソッド　factorial_for
2. 再帰するメソッド　factorial_recursive

// 繰り返し構文を用いたメソッド
long factorial_for(long i){
  if(i < 0){
    println("Error! Invarid input.<using for>");
    return -1;
  } else {
    long result = 1;
    for (int j = 1; j <= i; ++j){
      result *= j;
    }
    return result;
  }
}
// 再帰を用いたメソッド
long factorial_recursive(long i){
  if(i < 0){
    println("Error! Invarid input.<using recursive>");
    return -1;
  } else if(i == 0){
    return 1;
  } else {
    return i * factorial_recursive(i - 1);
  }
}

void setup(){
  long num    = 0;
  // using for
  println("using for       : factorial(" + num + ") = "
           + factorial_for(num) );
  // using recursive
  println("using recursive : factorial(" + num + ") = "
           + factorial_recursive(num) );
  num    = 10;
  // using for
  println("using for       : factorial(" + num + ") = "
           + factorial_for(num) );
  // using recursive
  println("using recursive : factorial(" + num + ") = "
           + factorial_recursive(num) );
  num    = -10;
  // using for
  println("using for       : factorial(" + num + ") = "
           + factorial_for(num) );
  // using recursive
  println("using recursive : factorial(" + num + ") = "
           + factorial_recursive(num) );

}

ユークリッドの互除法

８王妃問題を解く

再帰を活用するメリットとデメリット

再帰を活用するメリットは，「（場合によっては）問題をシンプルに記述できること」です。しかし，再帰は電子計算機で実行するアルゴリズムとしてはやっかいな問題，デメリットを抱えています。

そのデメリットを話す前に，計算量の2つの種類について言及しておきます。計算量は「時間計算量」と「空間計算量」という2つに区別できます。時間計算量は，これまで何度か取り扱って来た計算量の考え方で，そのアルゴリズムの実行にどれだけ手数がかかるかを表す量です。これに対して空間計算量は，そのアルゴリズムの実行にどれだけの記憶容量が必要かを表す量です。

再帰のアルゴリズムは，自分自身を1回呼ぶ度に，自分自身を実行するために必要なメモリを用意します。再帰の回数が多くなれば，必要なメモリ容量も多くなります。つまり，再帰のアルゴリズムのデメリットとは空間計算量が大きくなることです。再帰のアルゴリズムは潤沢にメモリがあることを前提とした手段なのです。

かつて，コンピュータがごくわずかなメモリしか持っていなかった時代のプログラミング言語が，再帰を言語の仕組みとして用意しなかった理由の一つは，再帰が簡単にメモリを食いつぶす方法だったからでしょう。現在，パーソナルコンピュータのメモリは数ギガバイトを持つようになったため，この問題が大きく扱われることはあまりありません。ただ，再帰を使ったプログラムによってはメモリを圧迫しますので，利用にあたっては慎重になりましょう。

そのため，再帰アルゴリズムを使用するべき場合とは，コードを劇的にシンプルにできる場合に限ると考えておくべきです。