科目Bサンプル問題9について、
orderを繰り返して最終的に子のないorder(8)にたどり着き、nとして8を出力することは分かりました。
しかし、解説を読むとそこから「呼び出し元のorder(4)に戻る」と書いており「なんで！？」となりました。
プログラムに「一つ前(親)に戻れ」ということが読み取れる言葉ないはずです。
なぜこうなるのでしょうか。

例えばfunc1がfunc2、func3を実行する関数だった場合、
func1{

func2()

func3()

}

のようになるので、func2の実行が終わったらfunc3が実行されますよね？

再帰関数は、関数の中でその関数自身が呼び出される関数です。func1をfunc1、func2を実行する関数としましょう。

func1｛

func1()

func2()

}

func1の中にfunc1があるため再帰関数ですね。このように定義されたfunc1を呼び出すと、func1が再帰的に実行され、func1の処理が終わるとfunc2が実行されますよね。func1()で8を出力し、呼び出し元のfunc1の処理にまだfunc2が残っているため、呼び出し元に戻り、func2を実行しなければいけません。これが呼び出し元に戻るイメージです。

以前、別のスレで書きましたが、再掲します。

order関数の定義・・どこか分かるようにorderの定義の行頭に記号を付けました。

order(整数型：n)
if(tree[n]の要素数が２と等しい)
①  order(tree[n][1])
②  nを出力
③  orrder(tree[n][2])
elseif(tree[n]の要素数が１と等しい)
④  order(tree[n][1])
⑤  nを出力
else
⑥  nを出力
endif

order(4)にあてはめると、

order(4)
  if(tree[4]の要素数が２と等しい)
    ＊tree[4]={8,9} 要素数2  なので真になります。
    ＊よって、関数の①②③の部分が実行されます
      ①order(tree[4][1]=8)→order(8)です
          if(tree[8]の要素数が２と等しい)
          tree[8]={}    要素数0  なので偽となり次の
          elseif(tree[8]の要素数が１と等しい)
          これも偽となり
          else
          order(8)についての⑥の部分を実行、8を出力します。
          endif  order(8)が終わります。
      ①終了
      ②の処理で、4を出力します。
      続けて③の処理になります。
      ・・・・
      ③が終わるとendifになり、
order(4)終了です。
（order(4)については、④、⑤、⑥は実行されません）

いかがでしょうか。
[4739]に続きがあります。

手続きorder()の処理内容を記述した次の擬似言語において

○order(整数型: n)
  if (tree[n]の要素数が2と等しい)
    order(tree[n][1])
    nを出力
    order(tree[n][2])
  elseif (tree[n]の要素数が1と等しい)
    order(tree[n][1])
    nを出力
  else
    nを出力
  endif
  ★呼び出し元に戻る★

という最後の★の箇所が自明のこととして省略されています。

--------
実は、情報処理技術者試験の擬似言語でも
★に該当する return という命令があるのですが、
関数、すなわち、戻り値がある場合のみ return文 を記述します。
手続き、すなわち、戻り値がない場合は return は書きません。

質問の意図と違うようでしたらすみません。
プログラムの基本的な挙動についてです。return句の有無に関わらず、プログラムは基本的にはメソッドを呼び出したら、呼び出したメソッドが完了するまで次の処理を実行しません。 例えば、F()がG()を呼び出した場合、G()が完了するまで次の処理である「6を出力」は実行されません。 したがって、明示的に戻ると書いていなくても、すべてのプログラムは基本的には呼び出し元に戻るという挙動をします。戻ってきたら、そこから処理を再開します。 F()、F2()の処理結果は同じです。

F()
・1を出力
・G()を呼び出す
・6を出力

G()
・2を出力
・3を出力
・4を出力
・5を出力

F2()
・1を出力
・2を出力
・3を出力
・4を出力
・5を出力
・6を出力

したがって、再帰処理の問題でもO(4)がO(8)を呼び出し、O(8)の処理が完了した後にO(4)に処理が戻ってきて、O(4)が続きの処理を再開したというだけです。 メソッドを展開すると、次のようになります。

O(2)
{ 
 ・O(4) 
   { 
   ・O(8) { 8を出力 } 
   ・4を出力 
   ・O(9) { 9を出力 }
    } 
 ・2を出力 
}

order(整数型：n)
①if(tree[n]の要素数が２と等しい)
②  order(tree[n][1])
③  nを出力
④  order(tree[n][2])
⑤elseif(tree[n]の要素数が１と等しい)
⑥  order(tree[n][1])
⑦  nを出力
⑧else
⑨  nを出力
⑩endif

この時点で、order関数の中にorder関数がある＝再帰する必要がある。とわかる


order(1)の実行手順をトレースします。
①if tree[1]の要素数が２個  →  {2,3}なのでTrue
②order(tree[1][1])  ＝  order(2)を実行

order(2)の実行手順
①if tree[2]の要素数が２個  →  {4,5}なのでTrue
②order(tree[2][1])  ＝  order(4)を実行

order(4)の実行手順
①if tree[4]の要素数が２個  →  {8,9}なのでTrue
②order(tree[4][1])  ＝  order(8)を実行

order(8)の実行手順
①if tree[8]の要素数が２個  →  {}なのでFalse
⑤elseif(tree[8]の要素数が１個  →  {}なのでFalse
⑨  nを出力  →  n{8}

order(8)の手順はorder(4)の途中②なので
次の手順はorder(4)の③になる
③  nを出力  →  n[8,4]
④  order(tree[4][2])と続いていくのだが
この時点で、解答は【ウ】となる

問題レベルでいうと基本レベルなので
このトレースがわからなければ、①再帰関数が解けない、②トレースがそもそもできていない
ということがわかりますので、試験勉強頑張ってください。

皆さんありがとうございました。