再帰を理解する
再帰は関数が自分自身を呼び出して問題を小さくしていく手法である。停止するための基底条件と、呼出しが戻る順序を理解する。
この単元で学ぶこと
- 再帰呼出しの意味と役割を説明できる
- 基底条件の意味と役割を説明できる
- 再帰ステップの意味と役割を説明できる
- 基底条件までの呼出し列と戻り値の展開を追える
本文解説
再帰呼出しのたびに引数や局所状態が呼出しスタックへ積まれ、基底条件へ到達すると最後に呼ばれたものから逆順に戻る。
再帰呼出し 関数が自分自身を呼び出すこと。 引数を変化させ問題を小さくする。
基底条件 それ以上再帰せず直接結果を返す条件。 停止条件がないと無限再帰になる。
再帰ステップ 元の問題を小さい同型問題へ変換する処理。 基底条件へ近づく必要がある。
呼出しスタック 未完了の関数呼出し状態をLIFOで保持する仕組み。 戻り時は最後の呼出しから処理を再開する。
戻り展開 基底条件から戻り値を逆順に組み立てること。 再帰式の結果計算に使う。
下降（呼出し）と上昇（戻り）を別々に書く。
fact(3)=3*fact(2)=3*2*fact(1)、fact(1)=1なので戻りは2→6。
図解
重要ポイント
- 再帰呼出し: 関数が自分自身を呼び出すこと。
- 基底条件: それ以上再帰せず直接結果を返す条件。
- 再帰ステップ: 元の問題を小さい同型問題へ変換する処理。
- 呼出しスタック: 未完了の関数呼出し状態をLIFOで保持する仕組み。
- 再帰問題は「どこで止まるか」と「戻りながら何を計算するか」の二段階。
間違えやすい点
- 基底条件を飛ばさない。
- 引数が基底条件へ近づかない再帰を見逃さない。
- 呼出し順と戻り順を同じ向きと考えない。
用語解説
- 再帰呼出し
- 関数が自分自身を呼び出すこと。
- 基底条件
- それ以上再帰せず直接結果を返す条件。
- 再帰ステップ
- 元の問題を小さい同型問題へ変換する処理。
- 呼出しスタック
- 未完了の関数呼出し状態をLIFOで保持する仕組み。
- 戻り展開
- 基底条件から戻り値を逆順に組み立てること。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。