再帰処理の処理を行う順序がわからなくなってしまうところが苦手です。
再帰処理自体はきっと理解はしているのですが、トレース途中で迷子になって解けずに、解説を見ると納得できることが多いです。が、またいざ解こうと思うと迷子になって解けません。。

（2022年12月26日公開）問9の再帰処理問題について、
下記gptに教えてもらったのですが、order(8)の出力まではできるのですが、その後どこまで帰ってどこから処理を再開すればよいのかわからなくなってしまいます。

order(1)
├─ order(2)
│  ├─ order(4)
│  │  ├─ order(8): 出力 8
│  │  └─ 出力 4
│  │  └─ order(9): 出力 9

再帰に関してのトレース表の書き方も理解しやすい書き方が上手く定まらずで、何か再帰処理のコツなど教えていただきたいです。。

本当は、下記のようにプログラムの頭に番号を触れたら自分のメモに書きやすいと思うのですが、テスト本番cbtなのでそんなことできないですよね、、
いちいち処理もトレース表に書くしかないのでしょうか。

 ①order(tree[n][1])
 ②nを出力
 ③order(tree[n][2])

私が回答に関わったスレッドはこちら。
https://www.fe-siken.com/bbs/5800.html
https://www.fe-siken.com/bbs/5898.html

jjon-comさんありがとうございます。
過去の投稿拝見しました。

やり方を理解したらこの手の問題は慣れていくしかないですかね、

メモに処理を書いている途中で、いつもどこに戻ればいいのかわからなくなってしまうのが一番の悩みです、、
当日も時間内に全て解ける気がしないです

データ構造を描いて視覚化すればいいのでは？
例題は多分バイナリサーチかと思いますが、実際にツリー構造を描いて動きを追えば俯瞰で把握出来ると思います。

当日の緊張感から冷静には判断つかないかもしれませんが、再起に限らず問題指定の値で考えないがコツだと思っています。

例えば問題文で１２３４５という５桁を入力とした場合。
とかがあると思います。
こういう時に１２とか１とか極端に小さい値で入力させると動きの理解に繋がりやすくなります。
（問９はデータ構造が指定されているので指定されている値で小さいものを使いますが、指定が特に無いのであれば適当な異常とならない数値や文字を使っていいです）

>https://www.fe-siken.com/kakomon/sample/b9.html
の問題であれば例えばデータ構造の一番上の１で入力した場合と言われていますが再起すると深くなります。
なので末端に近い7とかで入力した場合だったら考え安くないですか？という感じです。

仮に７だった場合、１４，７となりますね。
実はこれだけで回答の選択肢が既にウとエに絞られています。
では今度はとなりの６だった場合、１２，６，１３となりますね。
これで正解がウと絞れました。

ついでになのですが、３だった場合まともに再起を追っていくとプログラムになれている人でもすこし面倒です。

ですが３は６と７と分かっています。
ですが６と７は
・６＝１２，６，１３
・７＝１４，７
と分かっています。
これをつなげればいいので
（１２，６，１３）、３、（１４，７）
と深い再起を追う必要もなく結果を導ける事が多いです。

冒頭でも書きましたが試験中の緊張感があるので毎回うまく行くとは限りませんが小さい値にすることを心がけてください。

774さんありがとうございます。

参考書やYouTubeなどいろんなものをたくさん見ましたが、理解力がないのか考えすぎなのか（もしくは両者；；）でどの書き方も上手くいかず、自分なりの書き方を模索中です、、、

ツリー構造というのは、こんな感じに書いていくイメージでしょうか。
order(1)
├─ order(2)
│  ├─ order(4)
│  │  ├─ order(8): 出力 8
│  │  └─ 出力 4
│  │  └─ order(9): 出力 9

電タックさんありがとうございます。

ご丁寧に解説いただいたアドバイスを頭に置きながらなんとか頑張っていきたいと思います＞＜
過去問などを解く限り、再帰を含むプログラムは多くて二問程度かなという印象なのですが、当日は（再帰が時間がかかって苦手なので）最後に回してしまう作戦も有効だと感じますでしょうか。

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

と私は発言しました。ですから、私が次の問題をトレースで解くなら、
トレース表は巨大な1枚ではなく（流れをすべて1人で追うのではなく）、
小さなトレース表が複数 集まってできた姿になります。

サンプル問題 科目B 問9
https://www.fe-siken.com/kakomon/sample/b9.html

まず、プログラム開始時の「order(1)を呼び出す」のトレース表です。
引数 n に 1 を代入して次の関数を呼び出します。
tree[1] は {2, 3} であり、要素数は 2 ですから「……」より後ろは実行対象外です。
ですから、このレベルのトレース表は次のようになります。

次に「【別人】order(2)を呼び出す」のトレース表です。
引数 n に 2 を代入して次の関数を呼び出します。
tree[1] は {4, 5} であり、要素数は 2 ですから「……」より後ろは実行対象外です。
ですから、このレベルのトレース表は次のようになります。

さらに「【別人】order(3)を呼び出す」のトレース表です。
引数 n に 3 を代入して次の関数を呼び出します。
tree[1] は {6, 7} であり、要素数は 2 ですから「……」より後ろは実行対象外です。
ですから、このレベルのトレース表は次のようになります。

解説の続きです。

この時点でトレース表は、小さなポストイット用紙 3枚に別々に書かれており、
別のポストイットに処理が進む矢印線、
元のポストイットに処理が戻る矢印線、で結ばれることで
一連の大きなトレース表を構成するわけです。

●「order(1)を呼び出す」のトレース表
●「order(2)を呼び出す」のトレース表
●「order(3)を呼び出す」のトレース表

ちなみに、最初のトレース表に後者2つの中身を組み込むとこうなります。

●「order(1)を呼び出す」のトレース表

以降、最後までトレースをしてもいいのですが、この時点で正解は判明しました。
1 よりも前に 2 が出力され、1 よりも後に 3 が出力されるのは、選択肢 ウ だけです。

２分木をなぞってみます。
1 2 4 8 4 9 4 2 5 10 5 11 5 2 1 3 6 12 6 13 6 3 7 14 7 3 1
になると思います。これを手続きorderに合わせてみます。

order(1)
if (・・・)
 order(tree[n][1]) ①
 nを出力      ②
 order(tree[n][2]) ③
elseif (・・・)
 order(tree[n][1]) ④
 nを出力      ⑤
else
 nを出力      ⑥
endif

トレースすると
order(1) ① order(2) ① order(4) ① order(8) ⑥ order(4) ②③
order(9) ⑥ order(4) ③まで実行済みなので order(2) ②③ order(5) ①
order(10) ⑥ order(5) ②③ order(11) ⑥ order(5)  ③まで実行済みなのでorder(2) ③まで実行済みなのでorder(1) ②③ ・・・
比べるとorder(☆)の☆は、上でなぞったのと同じ順番で出てきます。
プログラムをトレースするより２分木をなぞった方が分かりやすいかと思います。
出力しているのは、②と⑥なので、
8 4 9 2 10 5 11 1 ・・・
になります。

ちょっと詳しく問題を見てみると
節番号の左側をなぞったらL
節番号の下側をなぞったらC
節番号の右側をなぞったらR
として半分なぞってみると以下のようになります。

1 2 4 8 8 8 4 9 9 9 4 2 5 10 10 10 5 11 11 11 5 2 1
L L L L C R C L C R R C L  L   C  R  C  L   C  R  R R C

Lで出力すると、
1 2 4 8 9 5 10 11 イになります。行きがけ
Cで出力すると、
8 4 9 2 10 5 11 1 ウになります。通りがけ
Rで出力すると、
8 9 4 10 11 5 2   エになります。帰りがけ

orderの①から⑤を
②
①
③

⑤
④
の順にすると、行きがけ

①
③
②

④
⑤
の順にすると、帰りがけ

になるかな。