導入

第9回より「データ構造とアルゴリズム」という大きなテーマの中から、4つのトピックをとりあげています。

• 配列とコレクション
• ソート
• サーチ
• 再帰

今回はその最終回として「再帰」を学習します。高校で数学を学習した人ならば、数学的帰納法の名前は聞いたことがあるでしょう。数学的帰納法は再帰の一例です。マトリョーシカのように式が構成されます。私は、数学的帰納法や再帰の概念が自分のものになるまでは、それらがまるで魔法のようで手をつけるのが恐ろしいような気がしたものでした。読者の皆さんがそんなふうに恐れて身を引いておられるならば、もったいないことです。是非、今回の学習で便利さに気付き、適切に活用しましょう。

展開

再帰とは

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

階乗と数学的帰納法

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

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

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

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

右辺に!が出てきましたね。「⁠...」なんていう省略記号を用いずに、はっきり式を定義している再帰的定義のほうが美しいと思いませんか？

さて、数学的帰納法を用いた証明問題で、同じような構造の式を見たことがあるはずです。数学的帰納法とは次のような方法でした。

1. 式f(1)が成り立つことを示す。f(1)を初期条件という。
2. 任意の自然数kに対して、f(k)ならばf(k + 1)が成り立つことを示す。
3. 2.が成り立つならば、任意の自然数nについてf(n)が成り立つといえる。これで数学的帰納法による証明おわり。

『教養としてのコンピュータ・サイエンス』（⁠渡辺治 著）に「再帰の極意」として紹介されていること（P.59）が、この数学的帰納法についても同様に言えます。つまり、ひとつ後の式f(k+1)が正しく実行されるために、今の式f(k)は正しく実行されると信じ込む、疑わないことが大切です。こう言及すると、何か詐欺でも働いているようですが、再帰ならば最終的な条件、数学的帰納法ならば初期条件をしっかり定義したのだから大丈夫なのです。どんどん進んで条件に打ち当たれば、その条件に定めた処理を実行するだけです。

ここで、次の作業に取り組んで組んでください。

[作業] 10の階乗を行うsketchを作成しましょう。(1)繰り返し構文を使ったメソッド、 (2)再帰するメソッド、この2通りのコードをひとつのsketchの中に書いてみましょう。

作業で作成したsketchの例は次のとおりです。最低でも30分は例を見ずに、自分の力で取り組んでみてください。

// 繰り返し構文を用いたメソッド
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つの正の整数mとnについての最大公約数を求めるアルゴリズムです。『⁠改訂C言語によるはじめてのアルゴリズム入門』（⁠河西朝雄 著、P.37）には次のように書かれています。

1. 正の整数m, nについて。
2. mとnが等しくない間、次の操作3.を繰り返す。
3. m > nならばm = m-n、そうでないならばn = n-m
4. m（またはn）が最大公約数である。

WikiPediaには次のように書かれています。このアルゴリズムは、上記のアルゴリズムよりも効率良く求める手順として掲載されています。

1. 入力をm, n(m >= n)とする。
2. n = 0なら、mを出力してアルゴリズムを終了する。
3. mをnで割った余りを新たにnとし、更に元のnを新たにmとし2.に戻る。

再帰を用いずにユークリッドの互除法をsketchにすると次のように書けます。ディスプレイウインドウ上のマウスポインタの座標(x,y)の最大公約数を求めています。

void setup(){
  size(600,400);
}

void draw(){
  int m = mouseX;
  int n = mouseY;
  while( !(m == n) ){
    if ( m < n) {
      int temp = m;
      m = n;
      n = temp;
    }
    m = m - n;
  }
  println("mouse on (" + mouseX + "," + mouseY + ") G.C.D. is " + m);
}

このアルゴリズムを再帰的に記述すると次のように書けます。

1. 2つの正の整数m, nの最大公約数を求める。ただし、m < nの場合はmとnの値を交換してから関数を適用する。こののち関数をgcd(m,n)を呼ぶ。
2. mとnが等しければ、mが最大公約数である。手順はこれで終了。
3. mとnが等しくなければ、新しいmの値をm-nとし、手順1.に戻る。

演習では、ユークリッドの互除法の再帰的なアルゴリズムをsketchに書くことをとりあげます。

[作業] GCD_General.pdeには、ある欠陥があります。アルゴリズムに条件として述べられている「m,nが正の整数であること」をチェックしていないのです。マウスポインタがディスプレイウインドウの「ふち」にちょうど重なると、ぴたっとsketchが動作を止めます。これは入力に0があったために無限ループに陥るからです。この欠陥を修正しましょう。

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

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

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

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

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

そのため、再帰アルゴリズムを使用するべき場合とは、コードを劇的にシンプルにできる場合に限ると考えておくべきです。「⁠劇的にシンプルにできる場合」に気付き、再帰を適用できるためには、あらかじめ再帰を使えるようになっている必要があります。ですから学習が必要なのです。

さらに学ぶために

実は、前回までで学習したソートやサーチにおいて、再帰が上手く活用されているアルゴリズムがあります。これらによってより実用的な再帰処理を学習できるのですが、今回のテキスト分量としては大きくなりすぎると判断したので割愛します。再帰についてより深く学習したい方は、キーワード「クイックソート」「⁠バイナリサーチツリー」について調べてみましょう。

演習

演習1（難易度：easy）

フィボナッチ数について調査し、n番目のフィボナッチ数を求めるsketchを書きましょう。再帰を用いないgetFibonacciGeneralと再帰を用いるgetFibonacciRecursiveの2つのメソッドを書きましょう。sketchファイル名をGetFibonacci.pdeとしてください。

演習2（難易度：middle）

マウスカーソルの座標値x, yの最大公約数を求めるために、ユークリッドの互除法を再帰的に使ったsketchを書きましょう。GCD_General.pdeを適宜変更してください。sketchの名前はGCD_Recursive.pdeとしてください。

まとめ

• 再帰とその代表的なアルゴリズムを学習しました。
• 再帰のメリットとデメリットを紹介しました。

学習の確認

それぞれの項目で、Aを選択できなければ、本文や演習にもう一度取り組みましょう。

1. 再帰の仕組みが理解できましたか？
   1. 理解できた。気持ちよく納得した。
   2. 理解できた。しかし、今ひとつスッキリしない。
   3. 理解できない。

2. 再帰を使うかどうかの判断基準が理解できましたか？

   1. 理解できた。気持ちよく納得した。
   2. 理解できた。しかし、今ひとつスッキリしない。
   3. 理解できない。

参考文献

• 『改訂C言語によるはじめてのアルゴリズム入門』（⁠河西朝雄 著、技術評論社⁠）⁠
  • アルゴリズムの入門書。入門者に取っては十分に辞書的な内容です。丁寧に解説された良書。
• 『教養としてのコンピュータ・サイエンス』]（渡辺治 著、サイエンス社⁠）⁠
  • 大学1年生の教養科目としてのコンピュータ・サイエンスの教科書。薄くて内容が精選されています。平易な文章と最低限の数式で構成されており、コンピュータ・サイエンスがどんな学問分野なのか知りたい方にはおすすめします。P.57から数頁ですが再帰についてマージソートを例に分かりやすく解説しています。

演習解答

1. GetFibonacci.pde
2. GCD_Recursive.pde

[作業] 解答例のsketchには負の数が入力された場合のチェックはありません。このメソッドをより一般的に使えるものにするためにはチェックの必要があります。時間があれば取り組んでみてください。