基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

再帰の問題がわかりません。どなたか教えてください。
r(3)として関数rを呼び出した場合の戻り値を求めよ。
プログラム
整数型：r(整数型：ｘ）
整数型:a,b
if(x<2)
 return 1
else
 a  ←  r(x-1)
 b  ←  r(x-2)
 return a+b
endif
解答群  ア  2  イ  3  ウ  4  エ  5
特にa  ← r(x-1)の計算式とかがわかりません。

考え方として関数を途中で呼び出す（再帰でもそれ以外でも）場合、その場所に関数がまるごと入る感じになります。

○関数A
  関数B呼び出し
  関数C呼び出し
○関数B
  Bと出力
○関数C
  Cと出力
  関数B呼び出し

この場合「呼び出し」となっている場所に「内容がそのまま」貼り付く感じになります。

つまり関数Cは
○関数C
  Cと出力
  Bと出力  →  元々は関数B呼び出し
となります。

次に関数Aは
○関数A
  Bと出力  →  元々は関数B呼び出し
  Cと出力  →｝元々は関数C呼び出し
  Bと出力  →｝元々は関数C呼び出し
となります。

この考えを踏まえた上で

r(3)はelseで以下の処理となります。
  a = r(2)  →  ■A
  b = r(1)  →  ■B
  return a + b

■A・r(2)はelseで以下の処理になります。
  a = r(1)
  b = r(0)
  a + b  ←  return a + bの事
■B・r(1)はtrueで以下の処理になります。
  1 ←  return 1の事。■b-1
が貼り付きます。

更に■A
r(1)はtrueで以下の処理になります。
  1 ←  return 1の事。■a-1
r(0)はtrueで以下の処理になります。
  1 ←  return 1の事。■a-2
が貼り付きます。

こうやって再帰や他の関数呼び出しがなくなったらくっつけていきます。

■A・r(2)はelseで以下の処理になります。
  a = 1 → ■a-1
  b = 1 → ■a-2
  return a + b

r(3)はelseで以下の処理となります。
  a = 2  →  ■A・r(2)のreturn a + b
  b = 1  →  ■b-1
  return a + b

書き方はこんな全部の変数を書き並べると大変なので、線を引っ張ったりメモ書きで追えるようにいろいろ試してみると良いと思います。

ちなみにこの手の再帰で例えばr(6)と問われた場合ですが、いきなり6の再帰を考えるのは大変なのでr(2)やr(3)と小さな数にして動きを掴んでからr(6)を検討する方が良いです。

答えは5ですか？

プログラム
1: 整数型：r(整数型：ｘ）
2: 整数型:a,b
3: if(x<2)
4:  return 1
5: else
6:  a  ←  r(x-1)
7:  b  ←  r(x-2)
8:  return a+b
9: endif

↑を手書きでトレースすると↓になります

○ r(3) # 1行目
├ a = r(3-1) # 6行目
│    ○ r(2) # 1行目
│    ├ a = r(2-1）# 6行目
│    │    ○ r(1) # 1行目
│    │    └ return 1; # if (x<2)の条件を満たすため
│    └ b = r(2-2）# 7行目
│    │    ○ r(0) # 1行目
│    │    └ return 1; # if (x<2)の条件を満たすため
│    └ return a + b; # 2を返却
├ b = r(3-2) # 7行目
│    ○ r(1)
│    └ return 1; # if (x<2)の条件を満たすため
└ return a + b; # 3を返却

答えは、イ  3

「出るとこだけ！基本情報技術者 科目Ｂ」の表記に倣って呼び出した関数には「○」をつけています
「セミコロン（;）」はプログラム最後の行であることを示します
「シャープ(#）」以降はコメントを表します

自分から自分（再帰）を呼び出しているのでトレースをすると混乱をしているのだと思います
例えば、おなじプログラムを何度も何度も呼び出して1行目が何度もでてきている！変数の値はどうなっちゃってるの？！とか……

自分（r関数）から他の関数（例えばr関数→foo関数→bar関数→baz関数→qux関数）を呼び出しているのとなにも変わりません
自分自身を呼んでいるのでおなじ処理をなんどもなんども繰り返しているように錯覚（混乱）してしまいがちですが、まったく別の関数を呼び出しているのだと脳みそを納得させてください（コンピュータもまったく別の関数を呼び出しているのだと割り切っているので……）

r(3) → foo(x-1) → bar(x-1) → baz(x-1) → qux(x-1)のように別の関数を次々に呼び出していれば普通にトレースできますよね？
r(3) → r(x-1)もおなじようにトレースをすればよいのです

それはわかるけど変数の値がどうなっているかわからない！と混乱されるようでしたら、変数のスコープに局所変数（ローカル変数）と大域変数（グローバル変数）という2種類があることを思い出してください
r関数（便宜的にA）からr関数（便宜的にB）を呼び出しても、変数xや変数a, 変数bなどはすべて局所変数なのでBで値を変数に代入してもそれがAに影響することはありません（その逆もしかりです）

「出るとこだけ！基本情報技術者 科目Ｂ」には他にもトレースのテクニック（メモに書く方法）が書かれていますが、その中でも関数の先頭に「○」をつけるのは有益なテクニックです
特に再帰呼び出しの場合は、繰り返し繰り返しおなじ関数を呼び出すことになるので開始を表す○を付けておくと見通しがよくなるのでおすすめです

余談ですが科目Ａのコーディング規約で再帰処理を使わないというのはこういったプログラムのことです
r()からr()、さらにr()からr()と何度も何度も呼ぶことでスタックオーバーフローが起きてしまいます

ありがとうございました。
よくわかりました。

ちょっと違った考え方です。参考までに、

r(3)から始めないで、x<2から考えます。
条件式より、xが2より小さいときは、r(x)=1になるので、
・・・r(-2),r(-1),r(0),r(1)までは、1になります。
elseの処理になるr(2)からは、
r(2)=r(1)+r(0)=1+1=2
r(3)=r(2)+r(1)=2+1=3
となり、答えは3
x=nの時は、
r(n)=r(n-1)+r(n-2)
フィボナッチ数列と同じ増え方ですね。