現在【でるとこだけ】の参考書で科目Bを学習中です。

再帰について質問させて頂きます。
以下、私の解き方を途中まで記載していますが、⑩の工程で6行目か7行目どちらに処理が移るのでしょうか。
参考書の回答は3になっていますが、解説を見ても理解できていないため、ご教示頂きたく思います。
宜しくお願いします。

【私の解き方】
①3行目がfalseになり、elseに処理に移る
②r(2)を呼び出し、3行目がfalseになる
③再度6行目が処理され、r(1)で呼び出す
④3行目がtrueになって、1がreturnされる
⑤6行目の変数aに1が代入される
⑥7行目でr(0)で呼び出す（7行目の時点でxは1のため、1 - 2で0を渡しています）
⑦3行目がtrueになって、1returnされる
⑧7行目で変数bに1が代入される
⑨8行目でa + bで2がreturnされる

【問題】
r(3)として関数rを呼び出した場合の戻り値を求めよ。

【プログラム】
1:整数型：r（整数型：x）
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

【回答】
3

ｘが3の引数で呼ばれた（問題最初の呼び出し）時の7行目になります。

分解すると
①の呼び出しで
・処理６行目の呼び出しが②から⑨で完結します。
・処理７行目の呼び出しが⑩・・・
となります。

この手の問題だけでなく解き方の裏技というわけではないですが、分かっている終了条件付近や小さく分かりやすい値に変えて読み取ると結構楽に解ける時が多いです。

問題ではr（3）と言っていますが、r（1）で呼んだ場合即returnされプログラムが終わることが解ります。

ここから考えると楽です。
・r（０以下） = 1となる。
・r（1）= 1となる。
この２つは即答えが出ますね。

後は
・r（2）としたときは、r（1）とr（0）を呼ぶのだからこれは上で既に分かっていて１と１で、２となる。
・r（3）としたときは、r（2）とr（1）を呼ぶのだからこれは２と１で、３となる。
仮に
・ｒ（4）としたときは、r（3）とr（2）を呼ぶのだからこれは３と２で、５となる。
・r（5）としたときは、r（4）とr（3）を呼ぶのだからこれは５と３で、８となる。
・r（6）としたときは・・・

３や４ぐらいだったら再帰の再帰でもトレースしきれると思いますが、再帰は必ず終わりがあるはずなので終了の値から逆算するのもテクニックとして知っておくと楽できます。

またいくつか出力された値の差にも注目するとよりGOODです。
今回の問題はフィボナッチぽいなーとか等差・階差ぽいなとかが再帰ではよくあります。

こんにちは。
自分も学習中の者です。

再帰は頭抱えますよね、わかります。。。
実際に解いてみたところ、以下のようになりました。

1:r(3)のとき
2:a, b = null
3:if (3<2) //Falseのため、5行目以降に移動
6:a ← r(2) //ここでr(2)が来たため、再帰が始まり再度1行目へ

1:r(2)のとき
2:a, b = null
3:if(2<2) //Falseのため、5行目以降に移動
6:a ← r(1) //ここでr(1)が来たため、再帰が始まり再度1行目へ

1:r(1)のとき
2:a, b = null
3:if(1<2) //Trueのため、4行目へ
4:return 1 //この時、r(1)にreturn 1しているため、以下のようにわかる
r(1) = 1
/*ここでr(1)の処理が終了*/
つまり、r(2)の残りを解く

6:a ← r(1)=1 //a=1となる
7:b ← r(0) //ここで再度r(0)が来たため、再帰が始まり1行目へ

1:r(0)のとき
2:a, b =null
3:if(0<2) //Trueのため、4行目へ
4:return 1 //この時、r(0)にreturn 1しているため、以下のようにわかる
r(0) = 1
/*ここでr(0)の処理が終了*/
＊つまり、r(2)の残りを解く

7:b ← r(0)=1 //b=1となる
8:return 1 + 1 //a + b=2
/*ここでr(2)の処理が終了*/
＊つまり、r(3)の残りを解く

6:a ← r(2)=2 //a=2となる
7:b ← r(1) //ここで再度r(1)が来たため、再帰が始まり1行目へ

1:r(1)のとき
2:a, b =null
3:if(1<2) //Trueのため、4行目へ
4:return 1 //この時、r(1)にreturn 1しているため、以下のようにわかる
r(1) = 1
/*ここでr(1)の処理が終了*/
＊つまり、r(3)の残りを解く

7:b ← r(1)=1 //b=1となる
8:return 2 + 1 //a + b=3
/*ここで全処理が終了*/

結果：3になります。
長くなってしまいすみません。

やり方は人それぞれだと思いますが，トレースの際，Python風にインデントを付けたらいかがですか？私はそうしてました。

再帰を自分自身の呼び出しと考えず、同じ処理をおこなう別人の呼び出しと考えてみてはどうでしょう。
https://www.fe-siken.com/bbs/5800.html
と過去に発言しました。

自分自身の3行目の if (x < 2) に何度も処理が戻ってくるのではなく、
r(3)を実行中の3行目と
r(2)を実行中の3行目と
r(1)を実行中の3行目は
それぞれ異なるというイメージが脳裏にないと、再帰の問題はトレースではややこしくて解いていられないと思います。

> Python風にインデントを付けたらいかがですか？ (No.4)
を参考にするとこうなるでしょうか。

最初は r(3)のレベルの処理の流れです。

●r(3)のトレース
1-① 呼び出される
1-② 3行目がfalseなのでelseに処理が移る
1-③ 6行目の変数aにr(2)の戻り値を代入する
1-④ 7行目の変数bにr(1)の戻り値を代入する
1-⑤ 戻り値としてa＋bを返す

次に 1-③ に登場する r(2)のレベルを別の処理として組み込んでみます。

●r(3)のトレース
1-① 呼び出される
1-② 3行目がfalseなのでelseに処理が移る
1-③ 6行目の変数aに【2-①～2-⑤】の戻り値を代入する
  ●r(2)のトレース
  2-① 呼び出される
  2-② 3行目がfalseなのでelseに処理が移る
  2-③ 6行目の変数aにr(1)の戻り値を代入する
  2-④ 7行目の変数bにr(0)の戻り値を代入する
  2-⑤ 戻り値としてa＋bを返す
1-④ 7行目の変数bにr(1)の戻り値を代入する
1-⑤ 戻り値としてa＋bを返す

さらに r(1) や r(0) を同じように処理として組み込むこともできるのですが、
> 分かっている終了条件付近や小さく分かりやすい値に変えて読み取ると結構楽に解ける (No.2)
という助言のとおり、
r(1) や r(0) ならば「4: return 1」になることは容易に読み取れますから、
r(1) や r(0) を一連の処理ではなく【1】という値として埋め込んでみます。

●r(3)のトレース
1-① 呼び出される
1-② 3行目がfalseなのでelseに処理が移る
1-③ 6行目の変数aに【2-①～2-⑤】の戻り値を代入する
  ●r(2)のトレース
  2-① 呼び出される
  2-② 3行目がfalseなのでelseに処理が移る
  2-③ 6行目の変数aに【1】を代入する
  2-④ 7行目の変数bに【1】を代入する
  2-⑤ 戻り値としてa＋bを返す
1-④ 7行目の変数bに【1】を代入する
1-⑤ 戻り値としてa＋bを返す

よって（2-③【1】 ＋ 2-④【1】）＋ 1-④【1】の答は 3 です。

電タックさん
ご丁寧にご教示頂き有難うございます。
今までトレース図を書いて解いていましたので、テクニックに目から鱗でした。
参考にさせて頂きます。

がんばってますよ！さん
トレース図を書いて解いていたので、インデントも参考にさせて頂きます。
ご教示頂き有難うございます。

sugar41さん
ご丁寧にご教示頂き有難うございます。
個人的に科目Bで一番躓いたのが再帰ですね。
一つ前の処理に戻るというのがいまいちしっくり来ていないです。
ご教示頂いた内容と合致するよう、参考にさせて頂きます。

jjon-comさん
ご丁寧にご教示頂き有難うございます。
"同じ処理をおこなう別人の呼び出し"という視点を参考に解いてみます。
有難うございます。