問題 No.1968
再帰呼び出しを用いたアルゴリズムを非再帰の反復処理によるアルゴリズムへと書き換える際に、一般的にプログラム内部のデータ構造として使用されるものはどれか。
【正解の解説】
関数呼び出しの履歴やローカル変数を順次退避させて復元するためのスタック
食器のトレーを重ねて上から出し入れするように、後から入れたものを先に取り出す仕組みです。再帰処理では、途中の計算を一旦ストップして別の処理を呼び出すため、元の状態を順に積み上げて記憶しておく必要があり、この「あと入れ、はじめだし」のルールを持つデータ構造がまさにピッタリなのです。
スポンサーリンク
【その他の選択肢の解説】
処理対象のデータ構造を先入れ先出しの順序で保持して順次処理するためのキュー
これはキュー（待ち行列）の説明です。遊園地のアトラクションの列のように、最初に並んだ人が最初に処理される仕組みです。再帰の巻き戻しでは『最後に中断した場所から順に再開する』必要があるため、先頭から処理するキューを使うと順番が逆になってしまい、正しく復元できなくなります。
探索時の経路や状態の遷移を網羅的に記憶して効率よく追跡するためのグラフ
これはネットワーク状の繋がりを表すグラフ構造の説明です。迷路の経路探索などで使われることが多いため再帰と結びつけられがちですが、プログラム内部で関数を呼び出す際の『履歴の管理』という目的においては、データの順序を一直線に積み上げるスタックの仕組みが不可欠となります。
複数回にわたる演算結果や参照頻度の高いデータを効率よく保持するキャッシュ
これは一度計算した結果を保存しておき再利用するキャッシュの説明です。処理の高速化という意味では再帰処理の最適化（メモ化など）で使われることがありますが、再帰を非再帰（反復処理）に書き換える際に、プログラムの実行履歴や変数を管理するための必須のデータ構造とは役割が異なります。