Pythonの最大再帰深度はどれくらいですか?それを増やす方法は?

2010年07月24日に質問されました。  ·  閲覧回数 542.7k回  ·  ソース

quantumSoup picture
2010年07月24日

私はここにこの末尾再帰関数を持っています:

def recursive_function(n, sum):
    if n < 1:
        return sum
    else:
        return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))

n=997 、その後、壊れてRecursionError: maximum recursion depth exceeded in comparisonを吐き出します。 これは単なるスタックオーバーフローですか? それを回避する方法はありますか?

回答

Thomas Wouters picture
2010年07月24日
538

はい、スタックオーバーフローに対するガードです。 Python(またはCPython実装)は末尾再帰を最適化せず、制限のない再帰はスタックオーバーフローを引き起こします。 sys.getrecursionlimit再帰制限を確認できます:

import sys
print(sys.getrecursionlimit())

sys.setrecursionlimit再帰制限を変更します:

sys.setrecursionlimit(1500)

ただし、そうすることは危険です。標準の制限は少し控えめですが、Pythonスタックフレームはかなり大きくなる可能性があります。

Pythonは関数型言語ではなく、末尾再帰は特に効率的な手法ではありません。 可能であれば、アルゴリズムを繰り返し書き直すことをお勧めします。

David Young picture
2010年07月24日
140

より高い再帰深度

import sys
sys.setrecursionlimit(1500)
Scharron picture
2010年07月24日
57

スタックオーバーフローを回避するためです。 Pythonインタープリターは、再帰の深さを制限して、無限の再帰を回避し、スタックオーバーフローを回避できるようにします。 再帰制限( sys.setrecursionlimit )を増やすか、再帰なしでコードを書き直してみてください。

Pythonドキュメントから:

sys.getrecursionlimit()

再帰制限の現在の値、Pythonインタープリタースタックの最大深度を返します。 この制限により、無限再帰によってCスタックのオーバーフローが発生し、Pythonがクラッシュするのを防ぎます。 setrecursionlimit()で設定できます。

Eugene Yarmash picture
2018年05月02日
36

再帰制限を頻繁に変更する必要がある場合(プログラミングパズルの解決中など)、次のような単純なコンテキストマネージャーを定義できます。

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit
        self.old_limit = sys.getrecursionlimit()

    def __enter__(self):
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

次に、カスタム制限を使用して関数を呼び出すには、次の操作を実行できます。

with recursionlimit(1500):
    print(fib(1000, 0))

withステートメントの本文を終了すると、再帰制限がデフォルト値に復元されます。

resource.setrlimitは、スタックサイズを増やし、セグメンテーション違反を防ぐためにも使用する必要があります

Linuxカーネルは、プロセスのスタックを制限します

Pythonはローカル変数をインタープリターのスタックに格納するため、再帰はインタープリターのスタックスペースを占有します。

Pythonインタープリターがスタック制限を超えようとすると、Linuxカーネルはセグメンテーション違反になります。

スタック制限サイズは、 getrlimitおよびsetrlimitシステムコールで制御されます。

Pythonは、 resourceモジュールを介してこれらのシステムコールへのアクセスを提供します。

たとえばhttps://stackoverflow.com/a/3323013/895245で言及されているsys.setrecursionlimitは、Pythonインタープリターが自身のスタックサイズに課す制限を増やすだけですが、Linuxカーネルによって課される制限には触れません。 Pythonプロセスで。

プログラム例:

main.py

import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()
print

# Will segfault without this line.
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

def f(i):
    print i
    sys.stdout.flush()
    f(i + 1)
f(0)

もちろん、 setrlimit増やし続けると、RAMが最終的に不足し、スワップの狂気のためにコンピューターが停止するか、 OOMKillerを介してPythonが

bashから、次のコマンドでスタック制限(KB単位)を確認および設定できます。

ulimit -s
ulimit -s 10000

私のデフォルト値は8Mbです。

参照:

Ubuntu 16.10、Python2.7.12でテスト済み。

Marcelo Cantos picture
2010年07月24日
14

末尾呼び出しの最適化を保証する言語を使用してください。 または、反復を使用します。 または、デコレータでかわいくなります。

rwst picture
2015年10月08日
9

もちろん、フィボナッチ数は、 Binetの式を適用することによってO(n)で計算できます。

from math import floor, sqrt

def fib(n):                                                     
    return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))

コメント提供者が指摘しているように、 2**nため、O(1)ではなくO(n)です。 また、違いは1つの値しか取得できないのに対し、再帰を使用すると、その値までのFibonacci(n)すべての値を取得することです。

Daniel picture
2013年09月06日
8

これは古い質問だと思いますが、このような問題には再帰を使用しないことをお勧めします。リストははるかに高速で、再帰を完全に回避します。 私はこれを次のように実装します:

def fibonacci(n):
    f = [0,1,1]
    for i in xrange(3,n):
        f.append(f[i-1] + f[i-2])
    return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1])

(フィボナッチ数列を1ではなく0からカウントし始める場合は、xrangeでn + 1を使用します。)

Tyler picture
2014年10月15日
8

「最大再帰深度を超えました」というエラーで同様の問題が発生しました。 os.walkループしているディレクトリ内の破損したファイルによってエラーがトリガーされていることを発見しました。 この問題の解決に問題があり、ファイルパスを操作している場合は、ファイルが破損している可能性があるため、必ず絞り込んでください。

bebidek picture
2018年02月17日
6

少数のフィボナッチ数のみを取得したい場合は、行列法を使用できます。

from numpy import matrix

def fib(n):
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)

numpyは高速べき乗アルゴリズムを使用しているため、高速です。 O(log n)で答えが得られます。 また、整数のみを使用するため、Binetの式よりも優れています。 ただし、すべてのフィボナッチ数をnまでにしたい場合は、暗記することをお勧めします。