関数の再帰呼び出し


C言語では、関数は自分自身を呼び出すこができます。これを再帰呼ぶ出し(recursive call)といいます。再帰呼び出しはスタック領域のメモリを大量に消費しますので、多用は避けたほうがよいでしょう。

main 関数から main 関数を呼び出すことも可能です。

ソースコード

源文件 
  1|/* recursive01.c */
  2|
  3|#include <stdio.h>
  4|
  5|int main(void)
  6|{
  7|  static int i = 1;
  8|
  9|  if (i <= 10){
 10|    printf("i = %d\n", i);
 11|    i++;
 12|    main();                                                                 
 13|  }
 14|  return 0;
 15|}

実行結果

i = 1
i = 2
i = 3
i = 4
i = 5
i = 6
i = 7
i = 8
i = 9
i = 10

再帰呼び出しで例としてよく使われるのが、階乗を求める関数です。n階乗とは

n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

のことであり、n! と書きます。では、階乗を求めるプログラムを作ってみましょう。

ソースコード

源文件 
  1|/* recurisive02.c */                                                        
  2|
  3|#include <stdio.h>
  4|
  5|int kaijo(int);
  6|
  7|int main(void)
  8|{
  9|  int i;
 10|  for(i = 0; i < 11; i++){
 11|    printf("%d! = %d\n", i, kaijo(i));
 12|  }
 13|  return 0;
 14|}
 15|
 16|int kaijo(int n)
 17|{
 18|  if (n == 0){
 19|    return 1;
 20|  } else {                                                                  
 21|    return n * kaijo(n - 1);
 22|  }
 23|}

実行結果

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

kaijo(0);

と呼び出された場合「return 1;」が実行されkaijo関数は1を返します。次に

kaijo(4);

という具合に呼び出されるとどうなるでしょうか。

  1. まずは「4 * kaijo(3)」が return される。
  2. ここでまた、kaijo 関数が呼ばれる。
  3. そうすると「3 * kaijo(2)」が return される。
  4. ここまた、kaijo関数が呼ばれる。
  5. そうすると「2 * kaijo(1)」が return される。
  6. またまた kaijo 関数が呼ばれる。
  7. このとき、kaijo 関数は「1 * kaijo(0)」を return する。
  8. ここで呼ばれた kaijo 関数は1を返す

kaijo(4) の戻り値を見ていくと次のようになります。

4 * kaijo(3)
4 * (3 * kaijo(2))
4 * (3 * (2* kaijo(1)))
4 * (3 * (2 * (1 * kaijo(0))))
4 * (3 * (2 * (1 * 1)))
結局 kaijo(4) の戻り値は「4 * 3 * 2 * 1 * 1」となるわけです。
kaijo 関数は条件演算子を使って次のように書き直すことができます。 
int kaijo(int n)
{
  return (n == 0) ? 1 : n * kaijo(n - 1);                                       
}

Chapte5 @ C言語目録 @ HomeWork List @ 昭亮's Homepage