この記事を読むと、以下のことができるようになります

再帰処理がどんな仕組みで成立しているのか説明できる
実際にPythonで再帰関数を書いて動かせる
再帰処理でよくある失敗（無限ループ）を避けられる

再帰処理とは何か——「鏡の前に鏡を置く」

合わせ鏡を思い浮かべてください。鏡の前にもう1枚鏡を置くと、**鏡の中に鏡が映り、その中にまた鏡が映り……**と、像が無限に続いていくように見えます。

**再帰処理（Recursion）**とは、これと同じように、関数が自分自身を呼び出すプログラミングの手法です。

ただし、合わせ鏡と決定的に違う点が1つあります。それは、「必ずどこかで止まる仕組み」を持っていなければならないということです。鏡の像は無限に続いても実害はありませんが、プログラムが無限に自分自身を呼び出し続けると、メモリを使い果たしてクラッシュしてしまいます。

再帰処理の2つの必須要素

再帰処理を書くときは、必ず次の2つを用意します。

① 基底ケース（止まる条件）

鏡を合わせるのをやめる「最後の1枚」にあたる部分です。「この条件になったら、もう自分自身を呼び出さずに答えを返す」という終了条件です。

② 再帰ケース（自分自身を呼び出す部分）

「もう1枚、鏡を合わせる」部分にあたります。少しだけ条件を変えて、自分自身を呼び出します。

実際にコードで体験する：階乗計算

「5の階乗（5! = 5×4×3×2×1）」を計算する再帰関数を書いてみます。

def factorial(n):
    # 基底ケース：これ以上分解できない、鏡合わせの「最後の1枚」
    if n == 1:
        return 1
    # 再帰ケース：少し条件（nの値）を変えて自分自身を呼び出す
    return n * factorial(n - 1)

print(factorial(5))

実行結果：
120

この関数の動きを、鏡合わせのイメージで追ってみます。


`factorial(5)`は、いきなり答えを計算するのではなく、「`factorial(4)`の答えが分かれば、それに5を掛ければいい」という形で、**問題を少しずつ小さくしながら、鏡の奥へ奥へと呼び出しを重ねていきます**。そして`factorial(1)`という「これ以上小さくできない基底ケース」に到達した瞬間、鏡に映った像が手前に向かって順番に答えを返していくように、**計算結果が逆順に積み上がって最終的な答えになります**。

---

## なぜ無限ループにならないのか

`factorial(5)`が`factorial(4)`を呼び、`factorial(4)`が`factorial(3)`を呼び……というように、**呼び出すたびに`n`の値が確実に1ずつ減っていく**ことがポイントです。「鏡合わせの奥行きが、確実に短くなっていく」設計になっているからこそ、いつか必ず`n == 1`という基底ケースに到達し、処理が止まります。

もし基底ケースを書き忘れると、どうなるでしょうか。

```python
# 危険な例：基底ケースがない
def broken_factorial(n):
    return n * broken_factorial(n - 1)  # 永遠に呼び出し続けてしまう

# broken_factorial(5) を実行すると...
# RecursionError: maximum recursion depth exceeded

鏡を合わせる「最後の1枚」を用意し忘れると、像が無限に続こうとしてしまい、Pythonが「これ以上は危険」と判断してエラーを出して強制的に止めてくれます。このエラーメッセージは、まさに「無限に鏡が続こうとしていますよ」という警告だと考えると理解しやすくなります。

再帰処理が向いている場面

再帰処理は、**「同じ構造が入れ子になっている問題」**を扱うときに特に威力を発揮します。

たとえば、フォルダの中にフォルダが入れ子になっているファイルシステムを全部探索したい場合、以下のように書けます。

import os

def list_all_files(directory):
    for entry in os.listdir(directory):
        full_path = os.path.join(directory, entry)
        if os.path.isdir(full_path):
            # フォルダの中にフォルダがあれば、同じ処理を繰り返す（再帰ケース）
            list_all_files(full_path)
        else:
            # ファイルなら表示する（基底ケースに相当する部分）
            print(full_path)

フォルダの中にフォルダがあり、その中にまたフォルダがあるという**「同じ構造の繰り返し」**は、まさに合わせ鏡と同じ性質を持っています。こうした入れ子構造には、for文よりも再帰処理の方が自然に対応できることが多くあります。

同じ計算を繰り返さない工夫：メモ化

再帰処理には、同じ計算を何度も繰り返してしまうという弱点があります。フィボナッチ数列を再帰で計算する例で見てみます。

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

fibonacci(3)が、fibonacci(5)を計算する過程で何度も重複して計算されていることがわかります。鏡合わせで言えば、「一度映した像を、もう一度最初から作り直している」ような無駄が発生している状態です。

この無駄を防ぐのがメモ化というテクニックです。一度計算した結果を記録しておき、同じ計算が必要になったら再計算せずに記録を使い回すようにします。

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]  # すでに計算済みなら、計算せずに使い回す
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

一度作った鏡の像を写真に撮っておき、次に同じ像が必要になったらもう一度鏡を合わせ直さずに、写真を見せるだけで済ませるイメージです。この工夫だけで、計算量が劇的に改善されることがあります。

よくある勘違い：再帰処理は常にfor文より優れているわけではない

「再帰処理はスマートでカッコいい」という印象を持たれがちですが、実際には呼び出しを重ねるたびにメモリを消費するため、非常に深い階層を扱う場合は、for文などの繰り返し処理の方が効率的なことがあります。「入れ子構造をわかりやすく表現したいとき」には再帰処理が向いていますが、「単純な繰り返し」であればfor文で十分なケースも多く、問題の性質に応じて使い分けることが大切です。

ビフォーアフター

【ビフォー】

再帰処理 → 「関数が自分自身を呼ぶ、なんだか怖いコード」
動作の理解 → 「なぜ無限ループにならないのか説明できなかった」
使いどころ → 「なんとなくカッコいいから使う」

【アフター】

再帰処理 → 「鏡合わせのように、問題を少しずつ小さくしながら自分自身を呼び出す仕組み」
動作の理解 → 「基底ケースがあるから、必ずどこかで呼び出しが止まる」
使いどころ → 「フォルダ構造など、入れ子構造の問題に向いている」

まとめ

この記事では、再帰処理の考え方を整理しました。

再帰処理は「鏡の前に鏡を置く」ように、関数が自分自身を呼び出す仕組み
「基底ケース（止まる条件）」と「再帰ケース（自分自身を呼ぶ部分）」の2つが必須
呼び出すたびに問題が確実に小さくなっていくことで、無限ループを防いでいる
フォルダ構造など、入れ子になった同じ構造の問題に向いている
深い階層ではメモリ消費に注意し、for文との使い分けを意識する

今度、自分自身を呼び出す関数を見かけたら、「基底ケースはどこか」を探してみてください。

ハンズオンラボでは、未経験からでも「作って覚える」をモットーにしたITハンズオンイベントを定期開催しています。

👉 イベント一覧はこちら

運営メンバーのXはこちら
えむ / わたる

面白かったら
「👇いいね」で応援