記事の内容

先日、競技プログラミングの問題で再帰を使っていたらエラーに遭遇しました。エラーの原因は、再帰の上限です。ここで改めて、再帰の上限についてまとめたく、この記事を公開します。

Pythonの再帰におけるsetrecursionlimitの解説

再帰呼び出しは、関数が自分自身を呼び出すプロセスです。再帰を使用することで、問題をより小さなサブプロブレムに分割して解決することができます。しかし、再帰には限界があります。それが再帰の深さです。

再帰の深さとsetrecursionlimit

再帰の深さは、関数が何回自分自身を呼び出すことができるかを示す指標です。再帰が深くなると、プログラムのスタックメモリを消費します。Pythonには、再帰の深さに制限があり、これを超えるとRecursionErrorが発生します。

RecursionError: maximum recursion depth exceeded in comparison

デフォルトでは、Pythonの再帰深さの制限は1000に設定されています。この制限は、無限再帰によるスタックオーバーフローを防ぐために存在します。

sys.setrecursionlimitの目的と必要性

sys.setrecursionlimitは、この再帰深さの制限を変更するための関数です。以下のように使用します：

import sys
sys.setrecursionlimit(2000)  # 再帰の深さの制限を2000に設定

目的と必要性

より深い再帰を許容：特定のアルゴリズム、特に深い再帰が必要なアルゴリズムでは、デフォルトの再帰深さが不十分な場合があります。例えば、深い再帰を使用する分割統治法やグラフ探索などです。
プログラムの安定性：デフォルトの設定は、多くの一般的なシナリオでの安定性を確保するために設計されていますが、特定の問題解決には調整が必要です。

具体例

再帰の深さ制限に直面する例として、深いツリー構造を探索する場合を考えてみましょう。

def deep_recursion(n):
    if n == 0:
        return
    deep_recursion(n - 1)

deep_recursion(1001)  # デフォルトの再帰深さを超えるとエラーが発生する

このコードはデフォルトの設定ではエラーになります。sys.setrecursionlimitを使って制限を変更してみましょう。

import sys
sys.setrecursionlimit(2000)

def deep_recursion(n):
    if n == 0:
        return
    deep_recursion(n - 1)

deep_recursion(1001)  # これでエラーが発生しなくなる

歴史的背景

再帰の深さ制限は、プログラムが無限再帰によってクラッシュするのを防ぐために導入されました。CやC++のような言語でも、スタックオーバーフローを防ぐために再帰深度に実質的な制限があります。Pythonでも同様に、デフォルトで比較的低い再帰深度制限を設けることで、ユーザーが無意識にシステムをクラッシュさせないようにしています。

注意点

sys.setrecursionlimitの値を大きく設定しすぎると、スタックオーバーフローを引き起こし、システムがクラッシュする可能性があります。設定する値は、システムのメモリ容量や使用しているアルゴリズムの特性に応じて慎重に決定する必要があります。

まとめ

再帰の深さは、関数が自分自身を呼び出す回数を制限する指標。
sys.setrecursionlimitを使って、この制限を変更できる。
目的は、無限再帰を防ぎつつ、必要に応じて深い再帰を許容すること。
慎重な設定が求められる。

参考資料

Python公式ドキュメント：sysモジュール

おすすめ記事

論理学って何を扱うの？論理学入門
線形代数の「背景と概念」をもっとよく分かりたい【数学弱者・凡人のための線形代数入門】
弱者・凡人のための競技プログラミング入門『競技プログラミングの鉄則』本を使いこなしたい ①二分探索
【Python リストの基礎】[ ]とlist() の違いが気になったから調べてみた