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

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 授業/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] を加えたものと考えることができます。 \[ \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の条件演算子をif文で書くと、次のようになります（プログラム2）。

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

演習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) が 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のように変更し、実行結果を確認せよ。

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

階乗 †

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

階段の昇り方 †

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

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

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

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

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

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

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

練習問題 †

フィボナッチ数 †

基数変換 †

ハノイの塔 †