非負の整数nに対して次のように定義された
関数F(n),G(n)がある。F(5)の値はいくらか。
関数
F(n):if n=<1 then return1 else return n×G(n-1)
G(n):if n=0 then return0 else return n+F(n-1)
(1)50 (2)65 (3)100 (4)120
正解
(2)65
以下解説
F(5):5×G(5-1)=5×(G(4))
=5×(4+F(4-1))=5×(4+(F(3)))
=5×(4+(3×G(3-1)))=5×(4+(+3×G(2))))
=5×(4+(3×(2+F(2-1))))=5×(4+(+3×(2+F(1)))))
=5×(4+(3×(2+(1))))
=65
再帰関数についての知識が皆無なので
教えて頂きたいのですが、なぜ=後の5×は残るのでしょうか。
そもそも再帰関数とは、どんなことを言っているのでしょうか。
具体例を挙げて頂くか、分かり易いURLを教えて頂けると幸いです。
お手数ですが、上記について1つ1つ丁寧に解説して頂きたいです。
大変ご迷惑な質問かと思いますが、分かる方おられましたら、
お手数ですが、ご教授お願いします。
以上、よろしくお願い致します。
No.2ベストアンサー
- 回答日時:
>そもそも再帰関数とは、どんなことを言っているのでしょうか。
http://ja.wikipedia.org/wiki/再帰
の「再帰呼出し」を参照。
>なぜ=後の5×は残るのでしょうか。
質問文のプログラムコードの実行過程は次のとおり。
(1a) 引数を5として関数F()を呼出し。その中でG(4)を使う
(2a) 引数を4として関数G()を呼出し。その中でF(3)を使う
(3a) 引数を3として関数F()を呼出し。その中でG(2)を使う
(4a) 引数を2として関数G()を呼出し。その中でF(1)を使う
(5) 引数を1として関数F()を呼出し。その戻り値は1
(4b) F(1)の戻り値を得てG(2)を求める。その戻り値は2+1=3
(3b) G(2)の戻り値を得てF(3)を求める。その戻り値は3×3=9
(2b) F(3)の戻り値を得てG(4)を求める。その戻り値は4+9=13
(1b) G(4)の戻り値を得てF(5)を求める。その戻り値は5×13=65
イメージ程度の把握でよいのなら,下記URLの「nの階乗」のイラストを参照すればよいでしょう。
http://www.ced.is.utsunomiya-u.ac.jp/lecture/200 …
「5はどこに残っているのか,きちんと知りたい」のであれば,適当な再帰プログラムをデバッガを使って実行し,下記URLの内容を理解することになります。
http://ja.wikipedia.org/wiki/リエントラント
(1a)(2a)(3a)(4a)(5)と進んでいく段階で,関数呼出しが発生するたびに戻り番地がスタックに積まれていることは分かりますか? 単純に言うならば,引数である5,4,3,2,1も関数呼出しのたびにスタックに積まれているのです。だから残っている。
ご回答ありがとうございました。
ご丁寧に説明して頂き、理解が出来ました。
当方、少し問題文を読み間違えていました。
また、各URLありがとうございます。
非常に役に立ちました。
以上、ありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
「ヒープサイズの設定」て何?
-
プログラム実行中に強制終了
-
解放と開放 漢字について
-
再帰関数について
-
CPUやメモリの使用率を調べ...
-
C,C++プログラムの強制終了時の...
-
C言語における再帰呼び出しの...
-
「memcpy」と「strcpy」について
-
動的メモリとexit(C言語)
-
C言語で、メモリを解放しないで...
-
エクセル キャッシュメモリー...
-
メモリの増加に関して
-
エクセルのメモリ使用状況/Appl...
-
値のコピーについて
-
CImage::ReleaseDC()のエラーで...
-
ウインドウズのシステムにおけ...
-
大容量のメモリ確保をスワップ...
-
Macターミナルで実行中のプログ...
-
HTA(HTMLアプリケーション)にて...
-
StrConvの使い方について教えて...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VBAの配列サイズとメモリに関して
-
C言語で、メモリを解放しないで...
-
C言語における再帰呼び出しの...
-
メモリ不足
-
「ヒープサイズの設定」て何?
-
動的メモリとexit(C言語)
-
エクセルのメモリ使用状況/Appl...
-
大容量のメモリ確保をスワップ...
-
【C言語】再帰が時間がかかる...
-
バッチファイルでの実行EXEのメ...
-
メモリのセグメント違反の解決...
-
「memcpy」と「strcpy」について
-
ExcelのVBAでメモリ解放できない
-
これて逆じゃないですか?
-
メモリを解放しないとどうなる?
-
ファイルマッピング関数で失敗
-
エクセルVBA 大容量CSVファイル...
-
メモリアロケーション異常の発...
-
エクセル キャッシュメモリー...
-
Apacheでバーチャルホストの最...
おすすめ情報