概念 / 再帰の考え方

小さい同じ問題に
分けて、自分を呼ぶ。

再帰は、問題を小さくして同じ形で解く考え方です。停止条件と再帰呼び出しが揃ってはじめて正しく動きます。

停止条件が必要木で考えると見やすいDP とも接続する

このページの目次

このページでわかること

1. どこで止まるか

2. 1回呼ぶごとに何が小さくなるか

3. 戻りながら値が組み立つ様子

概要

再帰は、問題を小さくして同じ形で解く考え方です。停止条件と再帰呼び出しが揃ってはじめて正しく動きます。

考え方

if 問題が十分小さいなら直接答える
そうでなければ、少し小さい同じ問題を解く
小さい答えから元の答えを組み立てる

要点

テーマ

横断概念

重要

停止条件

図

再帰木

よくある失敗

停止条件がない、または問題が小さくならないと無限に呼び出します。

教え方

コードだけでなく呼び出し木を一緒に見ると理解しやすいです。

次の接続

同じ部分問題を何度も解くとき、メモ化や DP につながります。

動きで確認

ここでは「どこで止まるか」を見ながら、上で読んだ内容を動きと結びつけます。

今いる呼び出し完了済み

次に見る

比較すると違いがわかりやすいページを先に置いています。