導入
第9回より
- 配列とコレクション
- ソート
- サーチ
- 再帰
今回はその最終回として
展開
再帰とは
再帰
階乗と数学的帰納法
整数n
の階乗は記号!
を用いてn!
と書きます。実際の計算は次のように行われます。
Factorial.pde
n! = n × (n-1) × (n-2) × ... × 2 × 1
この式を再帰的定義に書き換えると、
n! = n × (n-1)! (ただし、0!=1)
右辺に!
が出てきましたね。
さて、
- 式
f(1)
が成り立つことを示す。f(1)
を初期条件という。 - 任意の自然数
k
に対して、f(k)
ならばf(k + 1)
が成り立つことを示す。 - 2.が成り立つならば、
任意の自然数 n
についてf(n)
が成り立つといえる。これで数学的帰納法による証明おわり。
『教養としてのコンピュータ・f(k+1)
が正しく実行されるために、f(k)
は正しく実行されると信じ込む、
ここで、
[作業] 10の階乗を行うsketchを作成しましょう。(1)繰り返し構文を使ったメソッド、 (2)再帰するメソッド、
作業で作成した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) );
}
ユークリッドの互除法
ユークリッドの互除法も、m
とn
についての最大公約数を求めるアルゴリズムです。
- 正の整数
m
,n
について。m
とn
が等しくない間、次の操作3.を繰り返す。m > n
ならばm = m-n
、そうでないならばn = n-m
m
(または n
)が最大公約数である。
WikiPediaには次のように書かれています。このアルゴリズムは、
- 入力を
m, n(m >= n)
とする。n = 0
なら、m
を出力してアルゴリズムを終了する。m
をn
で割った余りを新たにn
とし、更に元のn
を新たにm
とし2.に戻る。
再帰を用いずにユークリッドの互除法をsketchにすると次のように書けます。ディスプレイウインドウ上のマウスポインタの座標(x,y)の最大公約数を求めています。
GCD_General.pde
。再帰を用いずにユークリッドの互除法で最大公約数を求める。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);
}
このアルゴリズムを再帰的に記述すると次のように書けます。
- 2つの正の整数
m, n
の最大公約数を求める。ただし、m < n
の場合はm
とn
の値を交換してから関数を適用する。こののち関数をgcd(m,n)
を呼ぶ。 m
とn
が等しければ、m
が最大公約数である。手順はこれで終了。m
とn
が等しくなければ、新しい m
の値をm-n
とし、手順1.に戻る。
演習では、
[作業] GCD_
には、
再帰を活用するメリットとデメリット
再帰を活用するメリットは、
そのデメリットを話す前に、
再帰のアルゴリズムは、
かつて、
そのため、
さらに学ぶために
実は、
演習
演習1(難易度:easy)
フィボナッチ数について調査し、n
番目のフィボナッチ数を求めるsketchを書きましょう。再帰を用いないgetFibonacciGeneral
と再帰を用いるgetFibonacciRecursive
の2つのメソッドを書きましょう。sketchファイル名をGetFibonacci.
としてください。
演習2(難易度:middle)
マウスカーソルの座標値x
, y
の最大公約数を求めるために、GCD_
を適宜変更してください。sketchの名前はGCD_
としてください。
まとめ
- 再帰とその代表的なアルゴリズムを学習しました。
- 再帰のメリットとデメリットを紹介しました。
学習の確認
それぞれの項目で、
- 再帰の仕組みが理解できましたか?
- 理解できた。気持ちよく納得した。
- 理解できた。しかし、
今ひとつスッキリしない。 - 理解できない。
再帰を使うかどうかの判断基準が理解できましたか?
- 理解できた。気持ちよく納得した。
- 理解できた。しかし、
今ひとつスッキリしない。 - 理解できない。
参考文献
- 『改訂C言語によるはじめてのアルゴリズム入門』
(河西朝雄 著、 技術評論社) - アルゴリズムの入門書。入門者に取っては十分に辞書的な内容です。丁寧に解説された良書。
- 『教養としてのコンピュータ・
サイエンス』 ] (渡辺治 著、 サイエンス社) - 大学1年生の教養科目としてのコンピュータ・
サイエンスの教科書。薄くて内容が精選されています。平易な文章と最低限の数式で構成されており、 コンピュータ・ サイエンスがどんな学問分野なのか知りたい方にはおすすめします。P. 57から数頁ですが再帰についてマージソートを例に分かりやすく解説しています。
- 大学1年生の教養科目としてのコンピュータ・
演習解答
[作業] 解答例のsketchには負の数が入力された場合のチェックはありません。このメソッドをより一般的に使えるものにするためにはチェックの必要があります。時間があれば取り組んでみてください。