授業/C言語基礎/再帰呼び出し のバックアップ(No.7)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 授業/C言語基礎/再帰呼び出し へ行く。
  • 1 (2015-12-21 (月) 12:22:25)
  • 2 (2015-12-22 (火) 09:15:07)
  • 3 (2015-12-23 (水) 18:04:18)
  • 4 (2015-12-23 (水) 18:16:19)
  • 5 (2015-12-24 (木) 11:46:26)
  • 6 (2016-01-07 (木) 09:21:03)
  • 7 (2016-01-08 (金) 10:28:40)

---

ある関数の中でその関数自身を呼び出すことを再帰呼び出しといいます。

再帰呼び出しを用いると簡潔なプログラムにできる場合がありますが、再帰呼び出しには注意しなければならないこともあります。

ここでは、再帰呼び出しについて説明します。

再帰的定義 †

[math]1[/math] から [math]n[/math] までの整数の和 [math]S_n[/math] について考えてみます。 \[ S_n = 1 + 2 + 3 + \dots + (n - 1) + n \]

[math]S_n[/math] は、[math]1[/math] から [math]n-1[/math] までの整数の和 [math]S_{n-1}[/math] に [math]n[/math] を加えたものと考えることができます。

したがって、[math]S_n[/math] は、[math]S_{n-1}[/math] を使って次のように定義できます。 \[ \begin{align} S_n &= \left( 1 + 2 + 3 + \dots + (n - 1) \right) + n \\ &= S_{n-1} + n \end{align} \] このような定義を再帰的定義といいます。 ただし、[math]n = 1[/math]のときは [math]S_1 = 1[/math] です。

再帰的に定義された関数を再帰関数といい、再帰関数が関数の中で自分自身を呼び出すことを再帰呼び出しといいます。

整数の和を求めるプログラムを再帰呼び出しを使って書くと、次のようになります（プログラム1）。

/*
 *  1からnまでの整数の合計を求める（再帰関数）
 */
int sum(int n) {
  if (n == 1) {
    return 1;
  } else {
    return sum(n - 1) + n;  // 再帰呼び出し
  }
}


int main(void) {
  int i = sum(5);
  printf("%d\n", i); 
  return 0;
}

関数sumは、条件演算子を使って次のようにも書けます（プログラム2）。

int sum(int n) {
  return n ? sum(n - 1) + n : 0;
}

n が 0 でないときは条件を満たすとして sum(n - 1) + n を計算して返します。 そうでないときは 0 を返します。 元の定義では [math]n = 1[/math] のとき [math]S_1 = 1[/math] ですが、条件をより簡潔にするため、[math]n = 0[/math] のときに [math]S_0 = 0[/math] を返すようにしています（このため、再帰呼び出しの回数が1回多くなります）。

条件演算子を用いたプログラム2のほうがコンパクトですが、理解しにくいならプログラム1だけわかれば問題ありません。

演習1 †

プログラム1またはプログラム2を作成し、実行結果を確認せよ。

再帰呼び出しの振る舞い †

再帰呼び出しの振る舞いを見るために、printf関数を呼び出してみましょう（プログラム3）。

int sum(int n) {
  printf(">> sum(%d) が呼び出されました\n", n);
  if (n == 1) {
    return 1;
  } else {
    return sum(n - 1) + n;
  }
}

このプログラムを実行すると、次のようになります。

luna% a.out
>> sum(5) が呼び出されました
>> sum(4) が呼び出されました
>> sum(3) が呼び出されました
>> sum(2) が呼び出されました
>> sum(1) が呼び出されました
15

まず、main関数が sum(5) を呼び出します。 次に、sum(5) は、n が 1 より大きいので、sum(4) を呼び出します（再帰呼び出し）。 sum(4) も、n が 1 より大きいので、 sum(3) を呼び出します。 同様にして、sum(3) が sum(2) を、sum(2) が sum(1) を呼び出します。

sum(1) は、n が 1 より大きくないので、（再帰呼び出しを行わずに）1 を sum(2) に返します。

sum(2) は、sum(1) から 1 を受け取り、1 + 2 を計算して sum(3) に返します。 sum(3) は、sum(2) から 3 を受け取り、3 + 3 を計算して sum(4) に返します。 sum(4) は、sum(3) から 6 を受け取り、6 + 4 を計算して sum(5) に返します。 sum(5) は、sum(4) から 10 を受け取り、10 + 5 を計算してmain関数に返します。

このようにして、main関数が sum(5) から 15 を受け取るまでの間に、sum関数が何度も再帰的に呼び出されています。

演習2 †

プログラム1またはプログラム2をプログラム3のように変更し、実行結果を確認せよ。

注意すべきこと †

再帰呼び出しが停止するように書く †

まず、再帰呼び出しを行う関数は、再帰呼び出しが必ず停止するように書かなければなりません。

よくありがちな間違いとして、[math]n = 1[/math] のときの処理を忘れてしまうことがあります（プログラム4）。

int sum(int n) {{
  printf(">> sum(%d) が呼び出されました\n", n);
  return sum(n - 1) + n;
}

すると、sum(5) を呼び出すと、sum(1) が sum(0) を、sum(0) が sum(−1) を呼び出すので、sum関数が延々と呼び出されて停止せず、無限ループに陥ります。

実際には、関数が呼び出されるたびに、メモリーのスタック領域を消費しますので、スタック領域がオーバーフローしてセグメント・エラーが発生します。 スタック・オーバーフローについては、計算機アーキテクチャーの授業できちんと勉強してください。

したがって、再帰呼び出しを行う関数は、再帰呼び出しが停止するように書かなければなりません。 とくに、条件分岐がない再帰呼び出しはあり得ません。

再帰呼び出しが停止するように呼び出す †

sum関数が、プログラム1のように正しく定義されていたとしても、sum(−5) を呼び出すと、sum関数が延々と呼び出されて停止せず、無限ループに陥り、スタック・オーバーフローが発生します。

したがって、再帰呼び出しを行う関数を呼び出すときは、再帰呼び出しが停止するように呼び出さなければなりません。

なるべく再帰呼び出しを使わない †

再帰呼び出しはメモリーのスタック領域を消費します。 また、何度も関数呼び出しを行うので、実行に時間がかかります。

再帰呼び出しを行わなくても良い場合には、再帰呼び出しを使うべきではありません。 もちろん、1からnまでの整数の合計も、再帰呼び出しを使わなくても計算できます（プログラム5, 6）。

/*
 *  for文を使って1からnまでの整数の合計を求める
 */
int sum(int n) {
  int i, s = 0;
  for (i = 1; i <= n; i++) {
    s += i;
  }
  return s;
}

/*
 *  公式を使って1からnまでの整数の合計を求める
 */
int sum(int n) {
  return n * (n + 1) / 2;
}

演習3 †

プログラム3をプログラム4のように変更し、実行結果を確認せよ。

再帰呼び出しを使ったプログラムの例 †

階乗 †

再帰呼び出しを使うと簡単に定義できる関数の代表例が階乗です。 \[ \begin{align} n! &= n \times (n - 1) \times \dots \times 2 \times 1 \\ &= n \times (n - 1)! \end{align} \] ただし、[math]0! = 1[/math]です。

int fact(int n) {
  return n == 0 ? 1 : n * fact(n - 1);
}

if文で書くと次のようになります。

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

階乗を求める関数は、再帰呼び出しを使わなくても定義できます。

int fact(int n) {
  int i, f = 1;
  for (i = n; i > 1; i--) {
    f *= i;
  }
  return f;
}

階段の昇り方 †

次のような問題を考えてみましょう。

階段を1段ずつか1段飛ばしで昇るとき、全部で20段ある階段の昇り方は何通りか

この問題は、再帰的に考えると、簡単に解けます。

最後の昇り方だけを考えると、最後は、19段目から1段昇るか、18段目から1段飛ばしで昇るかのいずれかです。 つまり、20段目までの昇り方が何通りあるかは、19段目までの昇り方が何通りあるかと18段目までの昇り方が何通りあるかがわかれば、この二つの和によって求めることができます。

これを一般的に書くと、n段目に昇る方法は、n−1段目から1段昇るか、n−2段目から1段飛ばしで昇るかのいずれかであり、n段目までの昇り方の場合の数、n−1段目までとn−2段目までの昇り方の場合の数の和で求まります。 ただし、1段目までの昇り方は1通り、2段目までの昇り方は（1段ずつ2段昇る方法と1段飛ばしで昇る方法の）2通りです。

したがって、n段目までの昇り方の場合の数を [math]S_n[/math] とすると、[math]S_n = S_{n-1} + S_{n-2}[/math] となります。 ただし、[math]S_1 = 1[/math], [math]S_2 = 2[/math] です。

/*
 *  n段目までの階段を1段ずつか1段飛ばしで昇る方法の場合の数を求める
 */
int step(int n) {
  switch (n) {
  case 1:
    return 1;
  case 2:
    return 2;
  default:
    return step(n - 1) + step(n - 2);
  }
}

まとめ †

再帰呼び出しは、関数の中でその関数自身を呼び出すことです。

最も高速なソート（並べ替え）アルゴリズムであるクイック・ソートは、分割統治法による再帰的アルゴリズムであり、再帰呼び出しを使って実装されます。 （分割統治法とクイック・ソートについては、データ構造とアルゴリズムやプログラム演習の授業できちんと勉強してください。）

再帰呼び出しでは、必ず、再帰呼び出しが停止するように再帰関数を定義し、再帰呼び出しが停止するように再帰関数を呼び出す必要があります。 また、再帰呼び出しは呼び出すたびにメモリーのスタック領域を消費するので、再帰呼び出しを行う必要がないときに使わないように注意しましょう。

課題・練習問題 †

13A-1: フィボナッチ数（難易度♠） †

フィボナッチ数列は、一つ前の項と二つ前の項の和で定義され、1, 1, 2, 3, 5, 8, 13, 21,... と続く数列である。 \[ \begin{align} f_1 &= 1 \\ f_2 &= 1 \\ f_n &= f_{n-1} + f_{n-2} \quad \text{($n > 2$)} \end{align} \] [math]n[/math] を大きくすると、隣り合うフィボナッチ数の比 [math]\frac{f_n}{f_{n-1}}[/math] が黄金比に近づく。

20番目のフィボナッチ数 [math]f_{20}[/math] を求めるプログラムを作成せよ。

13A-2: ユークリッドの互除法（難易度♠） †

ユークリッドの互除法は、二つの正の整数 [math]m[/math], [math]n[/math] ([math]m > n[/math])の最大公約数を求めるアルゴリズムである。

• [math]m[/math] が [math]n[/math] で割り切れるとき、[math]n[/math] が最大公約数
• そうでないとき、[math]m[/math] を [math]n[/math] で割ったときの余りを [math]r[/math] とすると、[math]n[/math] と [math]r[/math] の最大公約数が、[math]m[/math] と [math]n[/math] の最大公約数

ユークリッドの互除法を用いて 84 と 49 の最大公約数を求めるプログラムを作成せよ。

13A-3: 基数変換（難易度♠♠） †

10進数を2進数に変換するには、まず 2 で割り、商と余りを求める。 求めた商をさらに 2 で割り、商と余りを求める。 これを商が 0 になるまで繰り返し、求めた余りを逆順に並べると2進数になる。

たとえば、10進数の 10 について考えると、10 を 2 で割ると 5 余り 0、5 を 2 で割ると 2 余り 1、2 を 2 で割ると 1 余り 0、1 を 2 で割ると 0 余り 1 である。 余りを逆順に並べると 1010 になり、これが10進数 10 を2進数で表したものである。

10進数 65 を2進数に変換して出力するプログラムを作成せよ。

13A-4: ハノイの塔（難易度♠♠♠） †

ハノイの塔とは、次のようなパズルである。

[math]n[/math]枚の大きさが異なる円盤がある。 大きな円盤を小さな円盤の上に置くことはできず、円盤を置くことができる場所は A, B, C の3つしかない。 今、A にすべての円盤が下から大きい順に積まれている。 すべての円盤を C に移動させるには、どうしたらいいか。

5段のハノイの塔を解く手順を出力するプログラムを作成せよ。

13A-5: 配列のコピー（難易度♠♠） †

次の部分プログラムは、配列aの要素を配列bに再帰的にコピーするものである。 プログラムを完成させよ。

/*
 *  配列aの要素を配列bに再帰的にコピーする
 */
void copy(int a[], int b[], int from, int to) {
  if (from <= to) {
    b[from] = a[from];
    copy(a, b,        ,        );
  }
}

int main(void) {
  int a[5] = {1, 2, 3, 4, 5}, b[5];

  copy(a, b, 0, 4);  // 配列aから配列bへ要素番号0から4までの要素をコピーする

  int i;
  for (i = 0; i < 5; i++) {
    printf("%d\n", b);
  }

  return 0;
}

13A-6: 人口シミュレーション（難易度♠） †

[math]n[/math]年の人口を[math]P_n[/math]とすると、人口の増減は漸化式を用いて次のようにモデル化できる。 \[ \begin{align} \Delta P_n &= P_n - P_{n-1} = \alpha P_{n=1} \\ P_n &= (1 + \alpha) P_{n-1} \end{align} \] ここで、[math]\alpha[/math]は、前年同月比の人口増加率を表す。

2015年（7月1日現在）の日本人人口は1億2523万4000人で、前年同月に比べ0.21%の減少であった。 このときの人口増加率が続くとして、50年後（2065年）の日本人人口を推計するプログラムを、再帰関数populを定義して作成せよ。