再帰

「自分自身をもう一度呼ぶ」というのは、問題を少し小さくして、同じやり方をまた当てはめることです。短い規則から、手数や形がどれだけ育つのかを見ていきます。

• ハノイの塔: n枚を移すのは「n−1枚をよける」「大きい1枚を移す」「n−1枚を戻す」に分けられます。最短手数は 2のn乗 − 1 で、枚数が1つ増えるごとにほぼ倍になります。
• フィボナッチ数: 定義どおりに計算すると同じ計算を何度も繰り返します。一度出した答えを覚えておく（メモ化）と、呼び出し木が大きく縮みます。
• フラクタル: コッホ雪片・シェルピンスキーの三角形・再帰的な木を、深さを変えながら描けます。規則は1つでも、深さを増やすと部品の数が何倍にも増えます。
• 再帰には必ず「ここで止まる」という終了条件が要ります。
• コールスタック: 呼び出しが積まれ、順に戻ってくる様子を右側に並べて表示します。あとから積んだものが先に取り除かれる、スタックそのものの動きです。