C言語での再帰について説明しています。再帰呼び出しの例としてはユークリッドの互除法を用いて最大公約数を求めるプログラムを挙げています。
C言語の関数は再帰的に使用できます。すなわち、Cの関数は自分自身を直接(あるいは間接的に)呼び出すことが可能です。関数が自らを再帰呼出しすると、各呼出し毎に、処理中の値を保持したまま、新たな局所変数が生成されます。
再帰呼出しはツリー構造のような再帰的に定義されるデータ構造を扱う際に便利です。また、階乗計算やフィボナッチ数列のように再帰的な構造のアルゴリズムを記述するのにも適しています。
再帰呼び出しが正常に行われるには、その関数がリエントラントである必要があります。つまり、外部変数やstaticな局所変数の使用が不可です。また、その関数からリエントラントではない関数を呼び出してもいけません。
再帰呼び出しされる関数には、処理を中断・終了する条件が必ず必要です。その部分に誤りがあると無限に関数を呼び出すことになりますので注意しましょう。
再帰呼び出しの例として最大公約数を求めるプログラムを示します。
/*
gcd.c
最大公約数を求めるプログラム
*/
/* インクルードヘッダ */
#include <stdio.h>
#include <stdlib.h>
/* プロトタイプ宣言 */
int gcd(int x, int y);
int main(int argc, char *argv[])
{
int a = 0;
int b = 0;
/* 引数のチェック */
if (argc != 3) {
printf("Usage: %s <number 1> <number 2>¥n", argv[0]);
return 0;
}
/* 引数をintに変換 */
a = atoi(argv[1]);
b = atoi(argv[2]);
/* 結果を出力 */
printf("%d¥n", gcd(a, b));
return 0;
}
/*
最大公約数算出
gcd
<概要>
指定された値の最大公約数を返す
<戻り値>
指定された値の最大公約数
<引数>
int x:(i)負ではない値
int y:(i)負ではない値
<補足>
ユークリッドの互除法を用いて最大公約数を求める
負でない整数 x，yの最大公約数は以下で求まる
・yが0の時はx
・それ以外の時はyとxをyで割った余りの最大公約数
*/
int gcd(int x, int y)
{
if (y == 0) {
return x;
} else {
return gcd(y, x % y);
}
}