再帰関数の基本と実装ステップ

再帰関数の基本と実装ステップ

---

✅ 目標

再帰関数（recursive function）の基本的な考え方と実装方法を理解し、
典型的な例題を通して、再帰の動作を体験しながら学ぶ。

---

📌 再帰とは？

関数の中で自分自身を呼び出す関数のことを「再帰関数」と呼ぶ。

def recursive():
    recursive()

⚠️ このままだと無限ループになるので、**終了条件（ベースケース）**が必要！

---

📌 終了条件とは？

再帰呼び出しを止めるための条件。
例えば「nが1以下になったら止める」など。

def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n - 1)

---

🧮 例①：階乗（factorial）

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 出力: 120

• 5! = 5 × 4 × 3 × 2 × 1
• 再帰で自然に書ける構造！

---

🧮 例②：フィボナッチ数列

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(6))  # 出力: 8

• フィボナッチ数列: 0, 1, 1, 2, 3, 5, 8, 13...
• 繰り返し計算が多いので、大きな数では非効率（メモ化で改善可）

---

🌲 例③：DFS（深さ優先探索）に応用

graph = [[1, 2], [0, 3], [0, 3], [1, 2]]
visited = [False] * 4

def dfs(v):
    visited[v] = True
    print(v, end=' ')
    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs(neighbor)

dfs(0)

• 再帰関数はグラフ探索（DFS）にも非常に便利！

---

💡 ポイントまとめ

概念	説明
再帰	自分自身を呼び出す関数
終了条件	無限ループを防ぐために必須
スタック	呼び出しはスタック構造で積まれる
応用例	階乗、フィボナッチ、DFSなど

---