令和6年度 春期 応用情報技術者試験 午前 問6

再帰処理とは

再帰処理とは、ある処理の実行中に再び自分自身を呼び出す手法のことです。木構造のデータを探索する際によく用いられます。2分木における探索では、左の子、右の子、親ノードをどの順番で処理するかによって、データの出力順序が変わります。

正解の根拠

図の2分木は次のように構成されています。

• 根ノードは「＋」
• 「＋」の左の子ノードは「A」、右の子ノードは「÷」
• 「÷」の左の子ノードは「×」、右の子ノードは「－」
• 「×」の左の子ノードは「B」、右の子ノードは「C」
• 「－」の左の子ノードは「D」、右の子ノードは「E」

与えられた再帰処理 $f(n)$ の定義に従うと、各ノードにおいて「右の子の処理 $\rightarrow$ 左の子の処理 $\rightarrow$ 自身の出力」という順序で実行されます。根ノード「＋」から始めたときの処理の流れは以下の通りです。

1. $f(＋)$ : 右の子「÷」に対して $f(÷)$ を実行
2. $f(÷)$ : 右の子「－」に対して $f(－)$ を実行
3. $f(－)$ : 右の子「E」に対して $f(E)$ を実行。子がないため「E」を出力
4. $f(－)$ : 左の子「D」に対して $f(D)$ を実行。子がないため「D」を出力
5. $f(－)$ : 子の処理が完了したため、自身の「－」を出力
6. $f(÷)$ : 左の子「×」に対して $f(×)$ を実行
7. $f(×)$ : 右の子「C」に対して $f(C)$ を実行。子がないため「C」を出力
8. $f(×)$ : 左の子「B」に対して $f(B)$ を実行。子がないため「B」を出力
9. $f(×)$ : 子の処理が完了したため、自身の「×」を出力
10. $f(÷)$ : 子の処理が完了したため、自身の「÷」を出力
11. $f(＋)$ : 左の子「A」に対して $f(A)$ を実行。子がないため「A」を出力
12. $f(＋)$ : 子の処理が完了したため、自身の「＋」を出力

これらを順番に並べると、「ED－CB×÷A＋」となります。

各選択肢の解説

• ア: 指定された「右の子 $\rightarrow$ 左の子 $\rightarrow$ 自身」という実行順序に合致しないため、誤りです。

• イ: 指定された「右の子 $\rightarrow$ 左の子 $\rightarrow$ 自身」という実行順序に合致しないため、誤りです。

• ウ: 指定された「右の子 $\rightarrow$ 左の子 $\rightarrow$ 自身」という実行順序に合致しないため、誤りです。

• エ: 正しい実行順序で導き出される結果です。