では、再帰呼び出し定番のプログラムを紹介します。
大体どのプログラミングサイトを見ても、再帰の紹介はこんな感じで行われています。
１つめは「数列の和」です。
１から１０までの和を求めるプログラムを作ってみます。
正直、再帰呼び出しを使わなくても↓のプログラムで出来ますよね。
<sample program 149-01>
#include <stdio.h>
int main(void)
{
int i;
int answer;
answer = 0;
for (i = 1; i <= 10; i++) {
answer += i;
}
printf("answer = %d\n", answer);
return 0;
}
|
<実行結果>
answer = 55 続行するには何かキーを押してください・・・
しかし、再帰呼び出しを説明するための章ですから、これを無理やり再帰呼び出しを使ったプログラムにしてみます。
<sample program 149-02>
#include <stdio.h>
int Sum(const int value);
int main(void)
{
int answer;
answer = Sum(10);
printf("answer = %d\n", answer);
return 0;
}
int Sum(const int value)
{
if (value > 0) {
return value + Sum(value - 1);
}
else {
return 0;
}
}
|
<実行結果>
answer = 55 続行するには何かキーを押してください・・・
結果はきちんと出ていますが、慣れていないとどんな風に動いているのか分かりません。
計算の途中で自分自身を呼び出していますので、より複雑になった気がします。
１から１０までの和だと、説明が長くなりますので１から３までの和にして説明します。
<sample program 149-03>
#include <stdio.h>
int Sum(const int value);
int main(void)
{
int answer;
answer = Sum(3);
printf("answer = %d\n", answer);
return 0;
}
int Sum(const int value)
{
if (value > 0) {
return value + Sum(value - 1);
}
else {
return 0;
}
}
|
<実行結果>
answer = 6 続行するには何かキーを押してください・・・
戻り場所については省いて説明します。
１．main関数からSum関数（１回目：引数３）が呼び出されます。 ２．１回目：引数valueは０より大きいので、計算式に入ります。 return文は計算した後で実行されますので、先に value + Sum(value - 1) が実行されます。 これは、 3 + Sum(2) と同じ意味です。 この時点で、Sum関数（２回目：引数２）が呼び出されます。 ３．２回目：引数valueは０より大きいので、計算式に入ります。 ここでは、 2 + Sum(1) という計算をしようとします。 この時点で、Sum関数（３回目：引数１）が呼び出されます。 ４．３回目：引数valueは０より大きいので、計算式に入ります。 ここでは、 1 + Sum(0) という計算をしようとします。 この時点で、Sum関数（４回目：引数０）が呼び出されます。 ５．４回目：引数が０なので、０を返却し４回目の関数を終えます。 ６．３回目の関数が４回目の関数から戻ってきた「０」を受け取り、 1 + 0 → 1 を返却(return)し３回目の関数を終えます。 ７．２回目の関数が３回目の関数から戻ってきた「１」を受け取り、 2 + 1 → 3 を返却し２回目の関数を終えます。 ８．１回目の関数が２回目の関数から戻ってきた「３」を受け取り、 3 + 3 → 6 を返却し１回目の関数を終えます。 ９．main関数が１回目の関数から戻ってきた「６」を受け取り表示します。
慣れてくると感覚で理解できるのですが、慣れるまでが大変かも知れません。
これを利用して、再帰呼び出し定番の階乗を求めるプログラムを書きます。
下のプログラムでは、５の階乗を求めています。
５×４×３×２×１＝１２０
という計算ですね。
<sample program 149-04>
#include <stdio.h>
int Factorial(const int value);
int main(void)
{
int answer;
answer = Factorial(5);
printf("answer = %d\n", answer);
return 0;
}
int Factorial(const int value)
{
if (value > 0) {
return value * Factorial(value - 1);
}
else {
return 1;
}
}
|
<実行結果>
answer = 120 続行するには何かキーを押してください・・・
様々なプログラムサイトで紹介されていますので、探してみてください。
ただ、階乗を求めるプログラムをいつ使うのか・・・
次回はもう少し再帰の使い道について踏み込んでみましょう。