第 7 回 再帰処理

本日の内容

• 7-1. 再帰処理

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

7-1. 再帰処理

ある関数から自分自身の関数を呼び出すことを再帰と言います。 これを使うと、短い記述で複雑な問題を解くことができます。

ある問題を解く際に、その問題を同じ性質を持つ小さい部分に分解できるとし ます。 すると、その問題を解く関数 solve は再帰処理を使うと次のように書くこと ができます。

int solve(解くべき問題 t){
  if(t がもう分解できない){ 
    t を処理;
    return t の答え;
  }else{
    t1 = t を分解;
    ans1 = solve(t1);
    分解した残りと ans1 によりtの答を計算;
    return t の答え;
  }
}

例7-1

階乗 n!=n*(n-1)*...*2*1 は n!=n*(n-1)! と左辺にも階乗を含む構造に分解 できます。 一方 0!=1 となります。 従って、プログラムは次のようになります。

int kaijo(int n){
   if(n==0){
     return 1;
   }else{
     return n*kaijo(n-1);
   }
}     

演習7-1

このプログラムを使って、 5! と 6! を求めなさい。

例7-2

フィボナッチ数列とは、手前の数と、その手前の数の和を次々と求めてできる 数列です。

a₀=1, a₁=1 とすると、n 番目(n≧ 2)は a_n= a_n-1+ a_n-2 と書けます。 この時の n 番目の値を求めてみましょう。

演習7-2

1. a_nを求めるプログラムを作り、 a₂₀を求めなさい。
2. 素朴なプログラムだと a_nを計算する際、 a₁ は 2^n-1回も参照される これは非常に効率が悪く、このままでは現実的な時間内に a₄₀を求めることはできない。 そこで、値を入れる配列を用意して一度計算をしたら配列に格納し、計算結果 を再利用することを考える。 なお、この数列は全て値が正であるという特徴をもつので、最初配列を 0 で 初期化しておくと未計算かどうかは 0 かどうかを調べるだけでわかる。 このような計算法に修正したプログラムで a₄₀を求めなさい。

例7-3

組合せの数 _nC_m の求め方を考えます。 これは n 個の中から m 個を取り出す取り出し方は何通りあるかということで す。 ここで、n 個のものの中から一つのものに注目します。

注目したものを取り出さなかった時

残りの n-1 個の中から m 個を取り出すことになるので、組合せは _n-1C_m 通り

注目したものを取り出した時

残りの n-1 個の中から m-1 個を取り出すことになるので、組合せは _n-1C_m-1 通り

従って、 _nC_m = _n-1C_m + _n-1C_m-1 が得られます。 なお、n 個のものから0 個を取る取り方や、 n 個全部を取り出す取り方はと もに 1 通りしかありません。つまり _nC₀ = _nC_n = 1 です。

演習7-3

この式を使って再帰的なプログラムを組み、 ₅C₂、 ₂₀C₂ を求めなさい。

例7-4

ハノイの塔とは次のようなパズルです。 大きさが一回りずつ違う円盤を大きい順に下から並べます。 そして、次のルールでその円盤の山を移動させます。

1. 一度には一枚しか動かせない。
2. 移動可能な場所は、現在位置を含み三箇所
3. 小さい円盤の上に大きい円盤を置くことはできない

以下に 3 枚での例を示します。

この解法を再帰的に考えます。 もし、hanoi(n-1,'a','b','c') が n-1 枚の円盤を a から b へ移動する解法 を出力するとします(c はもう一つの領域)。 すると、 n 枚の円盤を a から b へ移動する解法は次のように考えられます。

1. まず、 n の上に乗っている n-1 枚の円盤を a から c へ移動します。つ まり hanoi(n-1,'a','c','b')
2. そして、n を a から b へ移動します。 move n from a to b
3. 最後に c にある n-1 枚の円盤を b に移します。 hanoi(n-1,'c','b','a')

このようにすると hanoi(n,'a','b','c') の解法を出力します。

#include <stdio.h>
hanoi(int n, char x, char y, char z){
  if(n==1){
    printf("move 1 from %c to %c\n",x,y);
    return;
  }else{
    hanoi(n-1,x,z,y);
    printf("move %d from %c to %c\n",n,x,y);
    hanoi(n-1,z,y,x);
    return ;
  }
}
main(){
  hanoi(3,'a','b','c');
}

演習7-4

上のプログラムを動かして hanoi(3,'a','b','c') と hanoi(4,'a','b','c') の解法を求めなさい。