第 8 回 再帰処理

本日の内容

• 8-1. 再帰処理

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

8-1. 再帰処理

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

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

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

int solve(解くべき問題 t){
  if(t がもう分解できない){ 
    t を処理;
    return t の答え;
  }else{
    t1 = t と同じ性質を持つ小さい部分;
    ans1 = solve(t1);  /* 再帰 */
    分解した残りと ans1 によりtの答を計算;
    return t の答え;
  }
}

例8-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);
   }
}     

演習8-1

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

例8-2

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

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

演習8-2

1. a_nを求めるプログラムを作り、 a₂₀を求めなさい。 なお、このフィボナッチ数は指数関数的に増加しますので、 a₅₀ は 32 bit の int 型で表せる範囲を越えてしまいます。 したがって、関数のシグネチャは次のを使用してください。

   
   long a(int n)
   

   これで、10946 が出ればプログラムは正常です。
2. a₀からa₅₀まで表示するプロ グラムを作りなさい。 なお、素朴なプログラムだと a_nを計算する際、 a₁ は 2^n-1回も参照される ことになります。 これは非常に効率が悪くなり、 50 まで表示するのにかなり時間がかかります。 1 分以内に求められるのはどこまでか調べなさい。
3. 一度計算した値を配列にしまう事を考えます。 そして、毎回値を計算するのに再帰処理を行うのではなく、 配列を用意して一度計算をしたら配列に格納し、計算結果 を再利用することを考える。 なお、関数は何度も呼ぶ事になるので、この結果をしまう配列はグローバルに宣 言しなければならない。 さらに、この数列は全て値が正であるという特徴をもつので、最初配列を 0 で 初期化しておくと未計算かどうかは 0 かどうかを調べるだけでわかる。 このような計算法に修正したプログラムで a₄₀を求めなさい。

例8-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 です。

演習8-3

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

例8-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==0) return;
  hanoi(n-1,x,z,y);
  printf("move %d from %c to %c\n",n,x,y);
  hanoi(n-1,z,y,x);
}
int main(void){
  hanoi(3,'a','b','c');
  return 0;
}

演習8-4

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