サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：再帰＞関数の再帰呼び出し
[２次元ポインタ配列]←このソース→[１０進数を１６進表示]
今日は階乗を求める関数を例にして、再帰呼び出しについて学びます。再帰呼び出し（Recursive call）とは、関数の中で自分自身と少し異なる自分を呼び出すことです。全く同じ自分を呼び出すことではありません。無限ループになってしまいます。
再帰呼び出しの関数のコードを記述するのは、慣れないと難しいのですが、再帰に向いているルーチンならば、短くて強力なソースプログラムを書くことができます。
まず、ある整数の階乗を返す関数を再帰を使わないで作ります。
ｎの値が大きくなるにつれて、ｎの階乗の値は急速に増加します。そこで戻り値は long型の整数とします。階乗を英語では" Factorial "というので、ｎの階乗を求める関数の名前を下記のようにします。
long Factorial1(int n) ;
ｎが０か１の時
なので、上記の２行をそのままソースコードにすると、次のようになります。
if (n == 0)
return (1L);
else if (n == 1)
return (1L);
しかし、これは次に示すように、論理演算子（|| ：論理和）を使えばもっと簡潔に記述できます。
if (n == 0 || n == 1)
return (1L);
では、ｎが３より大きい場合について考えます。ループを使えば良さそうです。long型の変数ｐを宣言し、１Lに初期化しておく。ループの中で、もし、ｎが１より大きければ、ｐにｎを掛け、ｎの値を１減少させる。
上記の文をそのままコードにすると、関数は次のようになります。
long Factorial1(int n)
{
long p = 1L;
if (n == 0 || n == 1)
return (1L);
else if (n > 1) {
for ( ; n > 0; n--)
p = p * n; // * 注
return (p);
}
}
* 注：pはlong型で、nはint型なので、
この掛け算はnがlong型に変換されてから行われる。
キャストの必要はない。
次に再帰版を作ります。
long Factorial2(int n);
Ｃでは、関数を呼び出す時、スタックに値を積みます。呼ばれた関数の側は積まれた値を利用します。これを値による呼び出し（Call by value）といいます。再帰版のソースを下記に示します。
// 階乗を求める（再帰版）
long Factorial2(int n)
{
if (n == 0 || n == 1) // n が 0 か 1 なら
return (1L); // 1 を返す
else // n に自分より 1 小さい自分を掛ける（これが再帰呼び出し）
return (n * Factorial2(n -1));
}
この関数を呼び出すと何が起こるか、次の説明をじっくり眺めて下さい。
Factorial2(n)の中に、n * Factorial2(n -1);と記述してあります。メインルーチンからFactorial2(n)が呼ばれると、次の一連の出来事が起こります。
Factorial2(1)が呼ばれると、順次スタックに積まれた値とのかけ算をしながら戻ります。 最後に、Factorial2(n)で、 n * Factorial2(n -1)の計算が行われ、 Factorial2(n)を呼び出したルーチンに戻ります。 その結果、階乗が求められます。
ソースプログラムの再帰版と非再帰版の長さを比べて下さい。再帰版では短くなったと思います。 */
#include <stdio.h>
long Factorial1(int n) ;
long Factorial2(int n) ;
void main(void);
/* 階乗を求める（非再帰版） */
long Factorial1(int n)
{
long p = 1L;
if (n == 0 || n == 1) /* nが０か１なら */
return (1L); /* １を返す */
else if (n > 1) {
for ( ; n > 0; n--)
p = p * n;
return (p);
}
}
/* 階乗を求める（再帰版） */
long Factorial2(int n)
{
if (n == 0 || n == 1) /* nが０か１なら */
return (1L); /* １を返す */
else /* nに自分より１小さい自分を掛ける */
return (n * Factorial2(n -1));
}
void main(void)
{
int n;
long f;
printf("整数を入力して下さい\t");
scanf("%d", &n);
f = Factorial1(n);
printf("Factorial1( ) = %ld\n", f);
f = Factorial2(n);
printf("Factorial2( ) = %ld\n", f);
}
|
[２次元ポインタ配列]←このソース→[１０進数を１６進表示]
/* (C) 2000- ＹＦプロ. All Rights Reserved. */ 提供：Ｃ言語講座−それ自体コンパイルできる教材を使った講座です−