今、再帰処理を勉強しています。
しかし、以下のプログラムがどうしても理解できません。
流れ的には一体どういう手順になっているのでしょうか?
return i * fact( i - 1 )の部分を考えると頭が
こんがらがってしまいます。
#include <stdio.h>
int main( void ){
printf("5の階乗は %d です", fact(5) );
return 0;
}
int fact( int i ){
if( i == 1 ) return 1;
else return i * fact( i - 1 );
}
--------実行結果----------
5の階乗は 120 です
No.1ベストアンサー
- 回答日時:
回数,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
- 回答日時:
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までやればいいのですから-1 しておけばいずれ1になって呼び出しは終了します。
皆さん本当にありがとうございます!
全員にレスを付けられなくて申し訳なく思いますが、
何とか理解できました。
でも再帰って不思議な概念ですね・・。
No.9
- 回答日時:
もう既に多くの方がご回答されていますので、以下は蛇足のアドバイスです。
再帰処理というのはある関数が自分自身を呼び出すことですね。
(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
- 回答日時:
単に流れが分からないだけであれば、
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
- 回答日時:
処理の流れは考えない……というのも手かもしれません。
まず、「階乗」はおわかりだと思いますが、
5! = 5×4×3×2×1 です。
ここで、
4×3×2×1 というのは、よく見れば、4!です。
つまり、5!=5×4!です。
というのは、いいですよね。
同じように、
n!=n×(n-1)!です。
これをそのままプログラミングすると、
int fact(n)
{
return n * fant(n - 1);
}
です。fact(n - 1) は、n - 1 の階乗ですから。
(実際には、これだと、無限に計算し続けるので、 n == 1 の時の条件がついていますが)
実際に、再帰の流れを追うのは(再帰を使うのが有効であればあるほど)大変になります。逆に、流れを追うことで、流れが理解できない処理は再帰で書くことができなくなる傾向があります。
もともと、再帰というのは、全体の処理の流れがわからなくても、一部分(今の場合は、n! と (n - 1)! )の関係と、再帰の終了条件(今の場合は、n == 1)がわかれば、処理が書けるということが特徴です。
ですから、流れを追って処理を理解するよりは、階乗の隣通しの関係をそのまま、Cに置き換えたという理解の方がいいような気がします。
No.6
- 回答日時:
>>return i * fact( i - 1 )の部分を考えると頭が
>>こんがらがってしまいます
再帰は初心者には結構とっつきにくいとおもいます。
頭で考えずに、fact関数の中にprintfを入れて#No1さんの表の用に
必要な値を出力してみれば流れが掴めるかと・・・
No.5
- 回答日時:
私もプログラマーなりたての頃、再帰処理の概念が理解できませんでした。
考え方としては・・・他の関数を呼ぶ代わりに、自分自身(例題では"fact"関数です)を呼ぶということです。
ただ、終了条件がないと、無限ループになってしまうので、ここでは終了条件として「iが1の時」が指定されているわけです。
いかがでしょう?
かえって混乱させちゃったら、ごめんなさい。
No.3
- 回答日時:
再起処理は難しく考える必要はありません。
落ち着いて手順どおり追えば良いです。
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が返される。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・14歳の自分に衝撃の事実を告げてください
- ・架空の映画のネタバレレビュー
- ・「お昼の放送」の思い出
- ・昨日見た夢を教えて下さい
- ・ちょっと先の未来クイズ第4問
- ・【大喜利】【投稿~10/21(月)】買ったばかりの自転車を分解してひと言
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・ハマっている「お菓子」を教えて!
- ・最近、いつ泣きましたか?
- ・夏が終わったと感じる瞬間って、どんな時?
- ・10秒目をつむったら…
- ・人生のプチ美学を教えてください!!
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・都道府県穴埋めゲーム
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
win10で、正確な待ち時間の作り方
-
VBでパスワード認証
-
絶対パスの取得について
-
SQLの速度をあげるには・・・
-
DoEvents関数って何?
-
小数点を含む数値かどうか判断...
-
ナップザック問題?をエクセル...
-
キャッシュを意識したプログラ...
-
プログラム上のCPU稼働率低減に...
-
VBでの簡易電卓の作成(減算方...
-
数値計算に適している言語
-
見やすい・メンテしやすいプロ...
-
空メール送信の宛先アドレスを...
-
Excelでのセル内容の高速消去方法
-
Windows 7 比較
-
どちらが効率的/美しい書き方で...
-
私たちの日常の行動は構造化プ...
-
Excel VBA データ削除の高速化
-
非同期プログラミングは必ずマ...
-
Macターミナルで実行中のプログ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
Excelでのセル内容の高速消去方法
-
DoEvents関数って何?
-
win10で、正確な待ち時間の作り方
-
小数点を含む数値かどうか判断...
-
ノットイコールを教えて下さい
-
SQLの速度をあげるには・・・
-
テキストファイルの空行をスキ...
-
プログラム上のCPU稼働率低減に...
-
絶対パスの取得について
-
実行時のCPU使用率を増やしたい
-
ナップザック問題?をエクセル...
-
If Not c Is Nothing Then ~延...
-
ソートにかかった時間を測りたい。
-
符号付きにすべきか、符号なし...
-
VC++2010 GDIオブジェクトの解...
-
基本情報技術者試験詳しい方へ...
-
VBでの簡易電卓の作成(減算方...
-
Excel VBA データ削除の高速化
-
Excel(VBA)でSetTimer関数を使...
-
ゲームプログラミングの乱数で...
おすすめ情報