基本情報技術者試験の練習問題です。 （プログラム〕 ◎整数型：r（整数型：x） 整数型：a、b if（x＜ …

Question

基本情報技術者試験の練習問題です。

（プログラム〕
◎整数型：r（整数型：x）
整数型：a、b
if（x＜ 2）
return 1
else
a←r(x-1)
b←r(x-2)return a + b
endif

r= 3だったときの戻り値は3になるんですけど、解き方(再帰呼び出しが特に)わかりません。脳内無限ループでオーバーフローしました。どなたか教えてください。

Answer 1

r(3)の戻り値が3ということですね。

r(3)ということですとx=3ということですので、
この時点ではelseのほうになり、（⓪）
r(3-1) …①
と
r(3-2) …②
を呼び出すことになります。

次に①と②の戻り値について考えます。

①について
==========================
r(3-1)=r(2)で、ここでもelseのほうになり、
r(2-1) …③
と
r(2-2) …④
を呼び出すことになります。

③はr(2-1)=r(1)なのでifのほうになり、r(1)=1 …⑤
④はr(2-2)=r(0)なのでifのほうになり、r(0)=1 …⑥

従って
③は⑤から1を値に返し、
④は⑥から1を値に返すので、
①において
a←r(2-1)
はa←1
同様に
b←r(2-2)
はb←1
となることから
①のr(3-1)=a+b=2で2を値に返します。
==========================

②について
==========================
r(2-1)=r(1)で、
ifのほうになりなりますので1を値に返します。
==========================

①②の値がそれぞれ2と１を値に返すことが分かりました。
ここで⓪のところを思い出してほしいのですが、
elseに入って
a←r(3-1) …①
b←r(2-2) …②
から
それぞれ①②の戻り値を確認しましたので。
a←2
b←1
となります。
返す値はa+b=2+1=3

となります。

Answer 2

◎整数型：r（整数型：x）
ㅤ整数型：a、b
ㅤif（x＜ 2）
ㅤㅤreturn 1
ㅤelse
ㅤㅤa←r(x-1)
ㅤㅤb←r(x-2)
ㅤㅤreturn a + b
ㅤendif

最初にr(3)で呼び出されたとします。
r(3)
ㅤr(3)
ㅤif (3 < 2) 偽
ㅤelse
ㅤㅤa ← r(3 - 1) … r(2)で呼び出し①
ㅤㅤb ← r(3 - 2) … r(1)で呼び出し②
ㅤㅤ① r(2)
ㅤㅤㅤif (2 < 2) 偽
ㅤㅤㅤelse
ㅤㅤㅤㅤa ← r(2 - 1) … r(1)で呼び出し③
ㅤㅤㅤㅤb ← r(2 - 2) … r(0)で呼び出し④
ㅤㅤㅤㅤ③ r(1)
ㅤㅤㅤㅤㅤ if (1 < 2) 真
ㅤㅤㅤㅤㅤ ㅤreturn 1
ㅤㅤㅤㅤ④ r(0)
ㅤㅤㅤㅤㅤ if (0 < 2) 真
ㅤㅤㅤㅤㅤ ㅤreturn 1
ㅤㅤ① return 1 + 1 … return 2
ㅤㅤ② r(1)
ㅤㅤㅤ if (1 < 2) 真
ㅤㅤㅤ ㅤreturn 1
ㅤㅤreturn 2 + 1
3

Answer 3

>解き方(再帰呼び出しが特に)
別の教科書で勉強した方がいいです。試験対策本は試験の対策を教えるものであって、再帰などの細かいところを教えるような本ではないです。あくまで試験対策本です。疑似コードも試験向けにちょっと捻られてるので、応用からやらされています。

なのでゼロから勉強するには向いてないです。別途解説が必要になってしまうからです。