授業/C言語基礎/再帰呼び出し

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

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

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

再帰的定義 †

[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);
  }
}

↑

まとめ †

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

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

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

↑

練習問題 †

練習問題はこちら。

再帰呼び出し