再帰関数について

質問

非負の整数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

jjon-com · ベストアンサー

>そもそも再帰関数とは、どんなことを言っているのでしょうか。

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の「ｎの階乗」のイラストを参照すればよいでしょう。
http://www.ced.is.utsunomiya-u.ac.jp/lecture/2004/prog/p1/debugger/factor.php

「５はどこに残っているのか，きちんと知りたい」のであれば，適当な再帰プログラムをデバッガを使って実行し，下記URLの内容を理解することになります。
http://ja.wikipedia.org/wiki/リエントラント

(1a)(2a)(3a)(4a)(5)と進んでいく段階で，関数呼出しが発生するたびに戻り番地がスタックに積まれていることは分かりますか？　単純に言うならば，引数である５，４，３，２，１も関数呼出しのたびにスタックに積まれているのです。だから残っている。

お礼

ご回答ありがとうございました。

ご丁寧に説明して頂き、理解が出来ました。
当方、少し問題文を読み間違えていました。

また、各URLありがとうございます。
非常に役に立ちました。

以上、ありがとうございました。

回答No.3

higeG

再帰関数の動作原理を知るためには、スタックの概念と関数呼び出し時に引数やローカル変数がどの様にスタックを使用しているかを理解する必要があります。
この辺を理解した上で、もう一度再帰関数の解説を良く読んでみることをお勧めします。
それでも理解できない部分があれば補足で挙げて下さい。

お礼

ご回答ありがとうございます。

スタックの概念を勉強してから
再度ご質問させて頂きます。

以上、ありがとうございました。

回答No.1

Tacosan

「=後の 5×」がどこのことを指しているのかわかりませんが, 普通に計算するんだから残ってないとおかしいでしょ? それとも, あなたは
5×(3+2) = 3+2 = 5
という計算が正しいと信じている?

お礼

ご回答ありがとうございます。

当方、少し問題文を読み間違えていました。
「5×」が残るのは当たり前ですよね。
失礼しました。

以上、ありがとうございました。