再帰について（C言語）

今、再帰処理を勉強しています。
しかし、以下のプログラムがどうしても理解できません。
流れ的には一体どういう手順になっているのでしょうか？
return i * fact( i - 1 )の部分を考えると頭が
こんがらがってしまいます。

#include <stdio.h>

int main( void ){
　printf("５の階乗は %d です", fact(5) );
　return 0;
}

int fact( int i ){
　if( i == 1 ) return 1;
　else return i * fact( i - 1 );
}

--------実行結果----------
５の階乗は 120 です

No.1 ベストアンサー 回答者： naktak 回答日時： 2006/10/05 10:13

回数,i,return

1,5,5 * fact(5-1)
2,4,4 * fact(4-1)
3,3,3 * fact(3-1)
4,2,2 * fact(2-1)
5,1,1

5回目の戻り値が1なので、4回目の戻り値は、2 * 1 = 2。
4回目の戻り値が2なので、3回目の戻り値は、3 * 2 = 6。
3回目の戻り値が6なので、2回目の戻り値は、4 * 6 = 24。
2回目の戻り値が24なので、1回目の戻り値は、5 * 24 = 120。
結果、呼び元に返される戻り値は、120。

と、トレースすれば理解出来ました？

No.10 回答者： BLUEPIXY 回答日時： 2006/10/05 17:29

fact(n) を求めたい時

fact(n-1) が判っていれば
fact(n)=n*fact(n-1)
ですね。
fact(x) を作っている最中に、fact(x)は、既に完成したものと考えてそれを使うということですね。
(実際に)使う時には、（それは既に完成しているので、)
fact(i-1) とすれば、i-1 の階乗がその関数で求まるので利用するだけです。
ただ、こういう関数を作る時には、それが本当に終わるのかどうか不安になりますよね？
なので、問題が(小さくなって)いずれ終わるようにしておく必要があります。
（新しく再帰的に呼び出す前に終了条件を調べる必要があります）
階乗の場合でいうとn*(n-1)*…*2*1 のように１までやればいいのですから-1 しておけばいずれ１になって呼び出しは終了します。

この回答へのお礼

皆さん本当にありがとうございます！
全員にレスを付けられなくて申し訳なく思いますが、
何とか理解できました。
でも再帰って不思議な概念ですね・・。

お礼日時：2006/10/06 09:15

No.9 回答者： connykelly 回答日時： 2006/10/05 17:18

もう既に多くの方がご回答されていますので、以下は蛇足のアドバイスです。

再帰処理というのはある関数が自分自身を呼び出すことですね。
(1)main{}の中で引数を5にしてfact()関数を呼び出しています。
(2)呼び出されたfact()関数は引数を変数iに入れて次の演算をしています。もしi=1であれば関数値1を返しますが、今はi=5ですので、returni*fact(i-1)のところは5*fact(4)の値を関数値として返します。
(3)ここで留意すべきはfact(4)を呼んでいる点です（←再帰処理）。従って(2)と同じようにreturni*fact(i-1)のところは5*4*fact(3)の値を返すことになります。
(4)同様にしてi=2まで繰り返すとreturni*fact(i-1)のところは5*4*3*2*fact(1)となりますね。
(5)最後にfact(1)の呼び出しはif( i == 1 ) return 1により1を返し、関数処理ルーチンからmain{}ルーチンに戻ることになりますから、結局fact(5)の関数は5*4*3*2*1=120を返すことになります。

No.8 回答者： jacta 回答日時： 2006/10/05 16:47

単に流れが分からないだけであれば、

int fact(int i)
{
　int result;
　printf("enter fact(%d)\n", i);
　if (i == 1) result = 1;
　else result = i * fact(i-1);
　printf("leave fact(%d) : %d\n", i, result);
　return result;　
}

のように、最初と最後にログ出力を行えばわかるようになるはずです。

再帰が分からないという人を見ていると、（特に階乗を例にしていると、）分からないのは処理の流れだけでなく、階乗が分かっていないことがよくあります。
また、本当に知りたいのは流れではなく、ループで済むものをなぜ再帰にするのかが分からないということだったりします。
そんなことはないのでしょうか？

No.7 回答者： AsanoNagi 回答日時： 2006/10/05 15:37

処理の流れは考えない……というのも手かもしれません。

まず、「階乗」はおわかりだと思いますが、

５！ ＝ 　５×４×３×２×１　です。
ここで、
４×３×２×１　というのは、よく見れば、４！です。
つまり、５！＝５×４！です。

というのは、いいですよね。

同じように、
ｎ！＝ｎ×（ｎ－１）！です。

これをそのままプログラミングすると、

int fact(n)
{
return n * fant(n - 1);
}
です。fact(n - 1) は、n - 1 の階乗ですから。
（実際には、これだと、無限に計算し続けるので、 n == 1 の時の条件がついていますが）

実際に、再帰の流れを追うのは（再帰を使うのが有効であればあるほど）大変になります。逆に、流れを追うことで、流れが理解できない処理は再帰で書くことができなくなる傾向があります。

もともと、再帰というのは、全体の処理の流れがわからなくても、一部分（今の場合は、n! と (n - 1)! ）の関係と、再帰の終了条件（今の場合は、n == 1）がわかれば、処理が書けるということが特徴です。

ですから、流れを追って処理を理解するよりは、階乗の隣通しの関係をそのまま、Ｃに置き換えたという理解の方がいいような気がします。

No.6 回答者： nerosuke 回答日時： 2006/10/05 11:47

>>return i * fact( i - 1 )の部分を考えると頭が

>>こんがらがってしまいます

再帰は初心者には結構とっつきにくいとおもいます。

頭で考えずに、fact関数の中にprintfを入れて#No1さんの表の用に
必要な値を出力してみれば流れが掴めるかと・・・

No.5 回答者： suzume00#2 回答日時： 2006/10/05 11:21

私もプログラマーなりたての頃、再帰処理の概念が理解できませんでした。

考え方としては・・・他の関数を呼ぶ代わりに、自分自身（例題では"fact"関数です）を呼ぶということです。

ただ、終了条件がないと、無限ループになってしまうので、ここでは終了条件として「iが１の時」が指定されているわけです。

いかがでしょう？
かえって混乱させちゃったら、ごめんなさい。

No.4 回答者： Yeti21 回答日時： 2006/10/05 10:18

また誤字です。

m(_"_)m

再起→再帰

No.3 回答者： Yeti21 回答日時： 2006/10/05 10:16

再起処理は難しく考える必要はありません。

落ち着いて手順どおり追えば良いです。

1.mainからfact(5)が呼ばれる。
2.factからfact(4)が呼ばれる。
3.factからfact(3)が呼ばれる。
4.factからfact(2)が呼ばれる。
5.factからfact(1)が呼ばれる。
6.fact(1)から1が戻され、2*1が計算される。
7.fact(2)から2が戻され、3*2が計算される。
8.fact(3)から6が戻され、4*6が計算される。
9.fact(4)から24が戻され、5*24が計算される。
10.fact(5)から120が返される。

No.2 回答者： tkun62 回答日時： 2006/10/05 10:13

factが呼ばれた時にもう１つ別のfactが発生し

生成されたfactはreturnで消えると考えれば
分かり易いかと思います。