【Python】恐怖の「RecursionError: maximum recursion depth exceeded」から紐解く再帰関数とスタックメモリの真実

Python

2026.05.16

競技プログラミング（AtCoderやLeetCode）に挑戦したり、木構造（Tree）データの探索アルゴリズムなどを実装したりしていると、突然ターミナル上に数百行にも及ぶ真っ赤なエラーログが滝のように流れ出し、プログラムが強制終了することがあります。

RecursionError: maximum recursion depth exceeded in comparison

「最大再帰深度を超過しました」。
直訳すると「自分自身を呼び出しすぎ（マトリョーシカの開けすぎ）で、もう限界だよ！」というPythonの悲鳴です。
このエラーは、単なるプログラムのバグというだけでなく、言語仕様・システムメモリ構造といったコンピュータサイエンスの非常に「深い（Deepな）」領域にあなたを誘う入り口でもあります。
本記事では、再帰関数（Recursion）の美しさと恐ろしさ、そしてこのエラーを回避するプロのテクニックを徹底解剖します！

1. 再帰関数とは「マトリョーシカ人形」である

再帰とは、ある関数の中で「自分自身の関数」を再び呼び出す処理のことです。
最も有名な例が、階乗（Factorial）を求める計算です。例えば「5の階乗（5!）」は 5 * 4 * 3 * 2 * 1 ですね。これを再帰で書くと、恐ろしくシンプルで美しいコードになります。

def factorial(n):
    # 【ベースケース（終了条件）】
    # マトリョーシカの一番中身。これ以上自分を呼び出さずに、具体的な値を返す！
    if n == 1:
        return 1
        
    # 【再帰ステップ】
    # まだ計算が終わらないので、「n-1」の計算を自分自身の分身に丸投げする！
    return n * factorial(n - 1)
print(factorial(5)) # => 120

このコードの最大の問題点は、「ベースケース（終了条件）が設定されていなかったり、データが多すぎてそこにたどり着かなかった場合、永遠に自分自身を呼び出し続けてしまう」という点にあります。

2. コールスタック（Call Stack）というメモ帳の限界

「なぜ永遠に呼び出し続けるとプログラムが落ちるの？パソコンのメモリはまだ何GBも空いているから、永遠と動き続ければいいじゃないか」と思うかもしれません。

実はコンピュータは、関数が呼び出されるたびに「今どこまで実行していて、変数には何が入っていたか」を、「コールスタック（Call Stack）」という非常に狭くて手狭な専用のメモ帳（メモリ領域）に書き込んで保存します。
関数が呼び出されるたびにこのメモ帳の一番上に付箋が積まれていき（Push）、関数が終わると付箋が剥がされて（Pop）元の場所に戻ります。

しかし、あまりに何度も連続して自分自身を呼び出すと（深い再帰）、この狭いメモ帳（コールスタック）のスペースがすぐに溢れかえってしまいます。
これが「スタック・オーバーフロー（Stack Overflow）」と呼ばれる現象の正体です。
Pythonは、このスタックが溢れてOS全体がクラッシュ（ブルースクリーン等）するのを未然に防ぐため、「再帰は1000回まで！」という安全装置（リミッター）を標準で設けているのです。これこそが、あのエラーの正体です。

3. エラー回避術：リミッター解除か、設計変更か

深さ1000以上の探索をどうしても行いたい場合、アプローチは大きく2つあります。

回避策A：再帰リミッターを力業で引き上げる

Pythonの「sys」モジュールを使えば、上限の1000回という安全装置を無理やり解除することができます。
競プロなど、競技時間内でとりあえず動かせば良い場合にはよく使われる即効性のあるハックです。

import sys
# 再帰の最大深度を 1,000,000回 に引き上げる！（自己責任で）
sys.setrecursionlimit(10**6)
# これで深さ1万の木構造も、エラーを出さずに探索可能になる！
def deep_recursion(n):
    if n == 0:
        return 0
    return 1 + deep_recursion(n - 1)
print(deep_recursion(5000)) # ギリギリ動く！

回避策B：本当に美しいプロの対応（ループへの変更）

実際のビジネス環境（サーバーシステムなど）でリミッターを解除するのは御法度です。最悪の場合、Pythonインタプリタごと不時着し、サーバープロセスが即死する危険があります。

プログラミングの面白く深い理論として、「全ての再帰関数は、whileループ（やforループ）と自前のスタック配列（リスト）を使うことで、再帰なしで完全に同じ動作に書き換えることができる」という定理があります。
このようにループで書き直せば、手狭な「コールスタック（関数呼び出し用のメモリ）」ではなく、MacやPCの持つ広大な「ヒープメモリ（リスト用のメモリ等）」を使うことができるため、文字通り無限に探索を続ける堅牢なコードになります！

まとめ：エラーから「アルゴリズムとデータ構造」の世界へ

RecursionError は、ただ「書き間違えた」という単純なエラーではなく、「あなたが実装したアルゴリズムが、コンピュータの基本的な設計思想（スタックメモリの仕組み）を超高負荷で試練にかけている」という高度な通知でもあります。

エラーが出たときは、「sys.setrecursionlimit を使えばいいや」で終わらせず、「なぜスタックが積まれるのか？」「ループ（幅優先探索等のイテラティブな手法）に書き換えるにはどうすべきか？」とアルゴリズムを再考する絶好のチャンスです。
この疑問を通して「アルゴリズムとデータ構造」を深く学ぶことで、あなたのエンジニアとしてのコーディング力は別次元へと進化するはずです。

リンク