第 7 回 再帰処理

本日の内容

• 7-1. 再帰処理

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

7-1. 再帰処理

自分の先祖を考えると、これは、おとうさん、おかあさん、おとうさんのおと うさん、おとうさんのおかあさん……と永遠に記述しなければならなくなりま すが、これを「おとうさん、おかあさんと、おとうさんの先祖とお母さんの先 祖」と言う風に先祖を規定するのに先祖という言葉を使って規定すると形の上 では短い表現で記述できます。 これを帰納的定義

ある関数から自分自身の関数を呼び出すことを再帰と言います。 C 言語は再帰が可能なため、関数定義で帰納的定義を使用することができます。 これを使うと、短い記述で複雑な問題を解くことができます。

ある問題を解く際に、その問題を同じ性質を持つ小さい部分に分解できるとし ます。 すると、その問題を解く関数 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>
void 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') の解法を求めなさい。