プログラミング基礎概念

再帰さいき

再帰関数基底条件スタック分割統治フィボナッチアルゴリズム

再帰について教えて

簡単に言うとこんな感じ！

「自分自身を呼び出す関数」のことだよ！ロシアのマトリョーシカ人形をイメージしてみて。人形の中に同じ形の人形が入っていて、それを開けるとまた同じ形の…って続くやつ。プログラムも同じで、ある処理の中で「もう一回自分自身を実行して！」ってやるのが再帰なんだ。

再帰とは

再帰（Recursion）とは、ある関数が自分自身を呼び出すことで問題を解くプログラミングの手法です。「大きな問題を同じ形の小さな問題に分解する」という考え方が根本にあり、繰り返し処理（ループ）と並んでプログラムの基本的な制御構造の一つとして位置づけられています。

たとえば「階段を降りる」という動作を再帰で表すなら「1段降りて、残りの階段を降りる」と書けます。「残りの階段を降りる」という部分が、もとの「階段を降りる」と全く同じ構造になっているのがポイントです。このように問題の構造が自己相似（自分と同じ形が繰り返し現れる）なときに再帰は特に威力を発揮します。

再帰を正しく動かすためには、必ず「いつ止まるか」を決める条件（基底条件・ベースケース）を設ける必要があります。これがないと関数が永遠に自分自身を呼び続け、最終的にプログラムがクラッシュします（スタックオーバーフロー）。

再帰の構造と仕組み

再帰の2大要素

要素	英語名	役割
基底条件	Base Case	「ここで止まれ」という終了条件。必ず必要
再帰ステップ	Recursive Step	自分自身を呼び出す部分。問題を少し小さくして渡す

再帰の動き方（階乗の例）

「5の階乗（5!）= 5×4×3×2×1 = 120」を再帰で計算するイメージ：

factorial(5)
  └─ 5 × factorial(4)
         └─ 4 × factorial(3)
                └─ 3 × factorial(2)
                       └─ 2 × factorial(1)
                              └─ 1 ← 基底条件！ここで折り返す
                       └─ 2 × 1 = 2
                └─ 3 × 2 = 6
         └─ 4 × 6 = 24
  └─ 5 × 24 = 120

コードで見ると（疑似コード）

function factorial(n):
    if n == 1:          ← 基底条件（ここで止まる）
        return 1
    return n * factorial(n - 1)  ← 再帰ステップ

サブトピック1: 覚え方

「マトリョーシカ」で覚えよう！

人形を開ける → 関数を呼ぶ
中に同じ形の人形 → 自分自身を呼び出す（再帰ステップ）
一番小さい人形（開けられない）→ 基底条件

「マ（まず基底条件）・ト（途中で自分を呼ぶ）・リ（リターンで積み上げる）」でも覚えられます。

サブトピック2: 再帰でよく解く問題の分類

問題の種類	具体例	再帰が向く理由
数学的定義が再帰的	階乗・フィボナッチ数列	定義そのものが「n番目 = n-1番目を使う」
ツリー構造の探索	ファイルシステム・組織図	フォルダの中にフォルダがある自己相似構造
分割統治アルゴリズム	マージソート・クイックソート	半分に割り続けて最後にまとめる
迷路・パズルの探索	数独・チェスの手読み	「試して→ダメなら戻る」の繰り返し

歴史と背景

1950年代: 再帰の概念自体は数学の「帰納的定義」として古くから存在していたが、プログラミングへの応用はこの頃から始まった
1958年: John McCarthy がLISPを設計。LISPは再帰を中心的な制御構造として採用した最初期の言語の一つで、ループよりも再帰を好む文化が生まれた
1960年代: ALGOL 60が再帰呼び出しを正式にサポート。コールスタック（関数呼び出しの状態を積み上げるメモリ構造）という概念も定着した
1970〜80年代: Prolog・Haskell など関数型・論理型言語が再帰をほぼ唯一の繰り返し手段として採用。「再帰こそ美しい」という考え方が広まる
現在: Python・JavaScriptなど主流言語すべてが再帰をサポート。ただし再帰の深さに上限（スタック深さ制限）が設けられるのが一般的

再帰 vs ループ：どちらを使う？

再帰とループ（for文・while文）はどちらも「繰り返し」を表現できます。選び方の目安を整理します。

観点	再帰	ループ
コードの読みやすさ	ツリー・分割問題では直感的	単純な繰り返しでは明快
メモリ使用量	呼び出しごとにスタックを消費	一定量で済む
速度	関数呼び出しのオーバーヘッドあり	一般的に高速
無限ループのリスク	基底条件を忘れるとクラッシュ	条件次第では無限ループ
向いている問題	自己相似・ツリー・分割統治	単純カウント・配列の走査

再帰と関数呼び出しスタックの関係（SVG図解）

末尾再帰（Tail Recursion）について

再帰の問題のひとつはスタックの消費です。末尾再帰とは、再帰呼び出しが関数の最後の処理になっている形で、一部の言語（HaskellやScalaなど）ではコンパイラが自動的にループに変換（末尾再帰最適化）してくれます。Pythonはこの最適化を意図的に行わない設計になっています。