再帰の試験問題への適用
本番の再帰問題では、出力順や戻り値が「呼出し前」と「呼出し後」で変わる。各呼出しフレームの引数を縦に積んで追う。
この単元で学ぶこと
- 前処理の意味と役割を説明できる
- 後処理の意味と役割を説明できる
- 引数列の意味と役割を説明できる
- 再帰呼出し前後の処理順と戻り値をスタック図で追える
本文解説
再帰呼出し前に出力する処理は下降順、再帰から戻った後に出力する処理は上昇順になる。戻り値を持つ場合は基底値から順に式へ代入する。
前処理 再帰呼出しより前に実行する処理。 呼出しが深くなる順に現れる。
後処理 再帰呼出しから戻った後に実行する処理。 戻りながら逆順に現れる。
引数列 各呼出しで変化する引数の並び。 停止条件へ近づくか確認する。
戻り値展開 基底値を使って親呼出しの式を順に評価する。 下から上へ計算する。
スタック深さ 同時に未完了となる再帰呼出し数。 入力サイズとメモリ使用量に関係する。
呼出し時に下へ積み、基底で折り返し、戻り時に上へ処理する。
f(n){if n=0 return; print(n);f(n-1)}ならf(3)は3,2,1。printが呼出し後なら1,2,3。
図解
重要ポイント
- 前処理: 再帰呼出しより前に実行する処理。
- 後処理: 再帰呼出しから戻った後に実行する処理。
- 引数列: 各呼出しで変化する引数の並び。
- 戻り値展開: 基底値を使って親呼出しの式を順に評価する。
- 同じ再帰でも処理が呼出し前か後かで出力順が逆になる。
間違えやすい点
- 下降時の処理と戻り時の処理を混同しない。
- 基底フレームで実行しない処理を勝手に実行しない。
- 戻り値式を上から計算しない。
用語解説
- 前処理
- 再帰呼出しより前に実行する処理。
- 後処理
- 再帰呼出しから戻った後に実行する処理。
- 引数列
- 各呼出しで変化する引数の並び。
- 戻り値展開
- 基底値を使って親呼出しの式を順に評価する。
- スタック深さ
- 同時に未完了となる再帰呼出し数。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。