応用情報技術者 2018年 春期 午前2 問08
問題文
再帰的な処理を実現するためには、再帰的に呼び出したときのレジスタ及びメモリの内容を保存しておく必要がある。そのための記憶管理方式はどれか。
選択肢
ア：FIFO
イ：LFU
ウ：LIFO（正解）
エ：LRU
再帰的処理の記憶管理方式【午前2 解説】
要点まとめ
- 結論：再帰処理では呼び出し元の状態を後で復元するため、LIFO方式の記憶管理が必要です。
- 根拠：再帰呼び出しは入れ子構造で、最後に呼び出した処理から順に戻るため、後入れ先出しの管理が適しています。
- 差がつくポイント：FIFOやLRUは順序管理の目的が異なり、再帰処理の状態保存には不向きである点を理解しましょう。
正解の理由
再帰処理では、関数が自分自身を呼び出すたびに現在の処理状態（レジスタやメモリの内容）を保存し、処理が終わったら直前の状態に戻す必要があります。この保存と復元の順序は「最後に保存したものから先に復元する」必要があり、これはLIFO（Last In First Out）方式で管理されます。したがって、正解はウ: LIFOです。
よくある誤解
FIFOは先入れ先出しでキューの管理に使われ、再帰の戻り順序とは逆です。LRUやLFUはキャッシュ置換アルゴリズムであり、再帰処理の状態管理とは目的が異なります。
解法ステップ
- 再帰処理の特徴を理解する（関数が自分自身を呼び出す）。
- 呼び出しごとに状態を保存し、戻るときに復元する必要があることを確認。
- 保存・復元の順序が「最後に保存したものから先に復元」であることを認識。
- LIFO方式がこの順序管理に該当することを判断。
- 選択肢の意味を整理し、LIFOを選択する。
選択肢別の誤答解説
- ア: FIFO（先入れ先出し）はキューの管理方式で、再帰の戻り順序と合わず不適切です。
- イ: LFU（Least Frequently Used）はキャッシュの置換アルゴリズムで、再帰処理の状態管理とは無関係です。
- ウ: LIFO（最後に入れたものを最初に出す）は再帰処理の状態保存に最適な方式で正解です。
- エ: LRU（Least Recently Used）もキャッシュ置換アルゴリズムであり、再帰処理の管理には使いません。
補足コラム
再帰処理の実装では「コールスタック」と呼ばれるスタック領域が使われます。スタックはLIFO構造で、関数の呼び出しごとに戻り先や局所変数を保存し、処理終了時に復元します。これにより、複雑な入れ子の呼び出しも正しく処理できます。
FAQ
Q: なぜFIFOでは再帰処理の状態管理ができないのですか？
A: FIFOは先に保存した状態から順に復元するため、再帰の戻り順序（最後に呼び出したものから戻る）と逆になり不適切です。
A: FIFOは先に保存した状態から順に復元するため、再帰の戻り順序（最後に呼び出したものから戻る）と逆になり不適切です。
Q: LRUやLFUはどのような場面で使われますか？
A: LRUやLFUは主にキャッシュメモリの置換アルゴリズムで、使用頻度や最近使われたかどうかでデータを管理します。
A: LRUやLFUは主にキャッシュメモリの置換アルゴリズムで、使用頻度や最近使われたかどうかでデータを管理します。
関連キーワード: 再帰処理、コールスタック、LIFO, スタック、記憶管理方式
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！