平成30年度春期 プロジェクトマネージャ 午前Ⅰ 問3

再帰処理の記憶管理を見極める視点

再帰処理を読むときは、呼び出しが重なる場面で、各段階の情報がどのように保持され、処理の進行に応じてどう扱われるかという一つの観点に集中し、段階ごとに整理しましょう。

この問題で問われていること

確認の中心は、再帰呼び出しが入れ子になるにつれて、途中の状態や戻り先を管理する仕組みをどのように捉えるかです。個別の方式名ではなく、状態の対応関係に注目してください。

視点

呼び出しの深さが変化する過程を追い、各段階で必要な情報が互いに混ざらず、処理の順序と対応づけて扱われるかを整理します。

確認ポイント

• 呼び出しが重なる順序と、各段階で保持される情報を対応づける
• 処理が進むときと戻るときで、記憶上の状態の扱いを分けて考える
• 一時的な情報と後続処理に必要な情報を区別して確認する

正解

ウ

解説

再帰処理では、後から呼び出された処理が先に終了して元の処理へ戻るため、保存したレジスタやメモリの内容も最後に保存したものから復元する必要がある。この方式はLIFOです。

理由

再帰では、ある処理の途中で同じ処理をさらに呼び出すため、呼出しごとの状態を保存する。最も内側の呼出しが終了してから外側の呼出しへ戻るので、最後に保存した状態を最初に取り出す順序になる。したがって正答はウのLIFOです。

比較

FIFOは最初に保存した状態を先に取り出す方式で、再帰からの復帰順序と一致しない。LFUは使用頻度の少ないものを対象とする管理方式、LRUは最後に使われてからの時間が長いものを対象とする方式であり、再帰呼出しの復帰順序を表すものではありません。

選択肢ア

これは不正解だよ。FIFOはFirst In, First Outの略で、最初に保存したデータを最初に取り出す方式である。しかし再帰処理では、内側の呼出しが先に終了し、その状態から順に復帰するため、保存した状態を呼出し順のまま取り出すFIFOは条件に合わない。

選択肢イ

これは不正解だよ。LFUはLeast Frequently Usedの略で、利用回数が少ないデータを対象にする管理方式である。再帰処理で必要なのは、データの利用頻度による選択ではなく、呼出しごとに保存した状態を復帰順に取り出すことであり、LFUは設問の条件を示していない。

選択肢ウ（正解）

これは正解だよ。LIFOはLast In, First Outの略で、最後に保存したデータを最初に取り出す方式である。再帰では呼出しが入れ子になり、最も内側で最後に保存されたレジスタやメモリの状態から先に復元して外側へ戻るため、この順序が適している。

選択肢エ

これは不正解だよ。LRUはLeast Recently Usedの略で、最近使われていないデータを対象にする管理方式である。これはキャッシュなどで利用状況を基準に置換対象を決める考え方であり、再帰処理に必要な保存状態の復帰順序を表す方式ではない。

学習のポイント

再帰呼出しとスタックの関係、保存状態を復元する順序を理解する。