Berapa kedalaman rekursi maksimum dalam Python, dan bagaimana cara meningkatkannya?

421

Saya memiliki fungsi rekursif ekor ini di sini:

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))

Ia bekerja hingga n=997, lalu rusak dan dimuntahkan a RecursionError: maximum recursion depth exceeded in comparison. Apakah ini hanya stack overflow? Apakah ada cara untuk menyiasatinya?

quantumSoup
sumber
3
Lihat juga stackoverflow.com/questions/5061582/…
Thomas Ahle
9
Memoisasi dapat mempercepat fungsi Anda dan meningkatkan kedalaman rekursif yang efektif dengan membuat nilai-nilai yang dihitung sebelumnya berakhir bukannya meningkatkan ukuran tumpukan.
Cyoce
2
Batas rekursi biasanya 1000.
Boris
1
@tonix interpreter menambahkan bingkai stack ( line <n>, in <module>in stack traces) dan kode ini membutuhkan 2 frame stack n=1(karena case dasarnya n < 1, jadi untuk n=1itu masih berulang). Dan saya kira batas rekursi tidak inklusif, seperti "kesalahan ketika Anda menekan 1000" tidak "kesalahan jika Anda melebihi 1000 (1001)". 997 + 2kurang dari 1000 sehingga tidak berfungsi 998 + 2karena mencapai batas.
Boris
1
@tonix no. recursive_function(997)berfungsi, rusak pada 998. Ketika Anda menyebutnya recursive_function(998)menggunakan 999 frame stack dan 1 frame ditambahkan oleh juru bahasa (karena kode Anda selalu dijalankan seolah-olah itu bagian dari modul level atas), yang membuatnya mencapai batas 1000.
Boris

Jawaban:

469

Itu adalah penjaga terhadap stack overflow, ya. Python (atau lebih tepatnya, implementasi CPython) tidak mengoptimalkan rekursi ekor, dan rekursi yang tidak terkendali menyebabkan stack overflow. Anda dapat memeriksa batas rekursi dengan sys.getrecursionlimitdan mengubah batas rekursi sys.setrecursionlimit, tetapi melakukan hal itu berbahaya - batas standarnya sedikit konservatif, tetapi stackframe Python bisa sangat besar.

Python bukan bahasa fungsional dan rekursi ekor bukanlah teknik yang sangat efisien. Menulis ulang algoritma secara iteratif, jika memungkinkan, umumnya merupakan ide yang lebih baik.

Thomas Wouters
sumber
4
Dari pengalaman saya, Anda perlu menambah batas dalam sysdan resourcemodul: stackoverflow.com/a/16248113/205521
Thomas Ahle
3
sebagai taktik untuk mengubahnya menjadi versi berulang, dekorator optimasi panggilan ekor dapat digunakan
jfs
3
Anda dapat menggunakan svn.python.org/projects/python/trunk/Tools/scripts/… untuk mengetahui batas atas OS Anda
Ullullu
8
Bagi mereka yang tertarik dengan sumbernya, batas rekursi default diatur ke 1000 hg.python.org/cpython/file/tip/Python/ceval.c#l691 dan dapat diubah menggunakan API di hg.python.org/cpython /file/tip/Python/sysmodule.c#l643 yang pada gilirannya menetapkan batas ke nilai baru di hg.python.org/cpython/file/tile/Python/ceval.c#l703
Pramod
17
Ekor rekursi adalah teknik yang sangat efisien dalam bahasa pemrograman yang dioptimalkan untuk itu. Untuk jenis masalah yang tepat, itu mungkin jauh lebih ekspresif dan merupakan implementasi berulang. Jawabannya mungkin berarti "dengan Python khusus" tetapi bukan itu yang dikatakannya
Peter R
136

Sepertinya Anda hanya perlu mengatur kedalaman rekursi yang lebih tinggi :

import sys
sys.setrecursionlimit(1500)
David Young
sumber
Dalam kasus saya, saya lupa pernyataan kembali dalam kasus dasar dan terus melebihi 1000. Python mulai melemparkan pengecualian ini dan saya kagum, karena saya yakin tentang tidak. dari tumpukan yang akan dibuat untuk menjalankannya.
vijayraj34
sys.setrecursionlimit (50) atau sejumlah kecil berguna jika program Anda memasuki rekursi dan Anda ingin pesan kesalahan TIDAK menjadi halaman dan halaman dari teks yang sama. Saya menemukan ini sangat membantu saat debugging (saya) kode rekursif buruk.
peawormsworth
56

Ini untuk menghindari stack overflow. Penerjemah Python membatasi kedalaman rekursi untuk membantu Anda menghindari rekursi tak terbatas, yang mengakibatkan tumpukan meluap. Coba tambah batas rekursi ( sys.setrecursionlimit) atau tulis ulang kode Anda tanpa rekursi.

Dari dokumentasi Python :

sys.getrecursionlimit()

Kembalikan nilai saat ini dari batas rekursi, kedalaman maksimum tumpukan juru bahasa Python. Batas ini mencegah rekursi tak terbatas dari menyebabkan overflow tumpukan C dan menabrak Python. Itu bisa diatur oleh setrecursionlimit().

Scharron
sumber
Pada Anaconda x64 saya, 3,5 Python di Windows, batas defaultnya adalah 1000.
Guillaume Chevalier
30

Jika Anda sering perlu mengubah batas rekursi (mis. Saat memecahkan teka-teki pemrograman), Anda dapat menetapkan pengelola konteks sederhana seperti ini:

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)

Kemudian untuk memanggil fungsi dengan batas khusus yang dapat Anda lakukan:

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

Saat keluar dari badan withpernyataan, batas rekursi akan dikembalikan ke nilai default.

Eugene Yarmash
sumber
Anda juga ingin menaikkan batas rekursi proses denganresource . Tanpa itu, Anda akan mendapatkan Segmentasi Fault dan seluruh proses Python akan macet jika Anda setrecursionlimitterlalu tinggi dan mencoba menggunakan batas baru (sekitar 8 megabita bingkai tumpukan, yang diterjemahkan menjadi ~ 30.000 bingkai tumpukan dengan fungsi sederhana di atas, pada laptop saya).
Boris
16

Gunakan bahasa yang menjamin optimisasi panggilan ekor. Atau gunakan iterasi. Atau, dapatkan lucu dengan dekorator .

Marcelo Cantos
sumber
36
Itu agak membuang bayi keluar dengan air mandi.
Russell Borogove
3
@Russell: Hanya salah satu opsi yang saya tawarkan menyarankan ini.
Marcelo Cantos
"Bercinta dengan dekorator" bukanlah pilihan.
Tn. B
@Br. B kecuali jika Anda membutuhkan lebih ulimit -sdari tumpukan frame, ya itu stackoverflow.com/a/50120316
Boris
14

resource.setrlimit juga harus digunakan untuk menambah ukuran tumpukan dan mencegah segfault

Kernel Linux membatasi tumpukan proses .

Python menyimpan variabel lokal pada stack interpreter, dan rekursi mengambil ruang stack interpreter.

Jika juru bahasa Python mencoba untuk melampaui batas tumpukan, kernel Linux membuatnya kesalahan segmentasi.

Ukuran batas tumpukan dikontrol dengan getrlimitdan setrlimitpanggilan sistem.

Python menawarkan akses ke panggilan sistem tersebut melalui resourcemodul.

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)

Tentu saja, jika Anda terus meningkatkan ulimit, RAM Anda akan habis, yang akan memperlambat komputer Anda karena berhenti kegilaan, atau membunuh Python melalui OOM Killer.

Dari bash, Anda dapat melihat dan mengatur batas tumpukan (dalam kb) dengan:

ulimit -s
ulimit -s 10000

Nilai default untuk saya adalah 8MB.

Lihat juga:

Diuji pada Ubuntu 16.10, Python 2.7.12.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
sumber
1
Mencoba mengatur rlimit_stacksetelah perbaikan Stack Clash dapat mengakibatkan kegagalan atau masalah terkait. Lihat juga Masalah
jww
Saya menggunakan ini (bagian sumber daya Python) untuk membantu implementasi algoritma Kosaraju saya pada dataset mean (besar) profesor Tim Roughgarden. Implementasi saya bekerja pada set kecil, tentu masalah dengan dataset besar adalah batas rekursi / tumpukan ... Atau apakah itu? Ya itu! Terima kasih!
nilo
9

Saya menyadari ini adalah pertanyaan lama tetapi bagi mereka yang membaca, saya akan merekomendasikan untuk tidak menggunakan rekursi untuk masalah seperti ini - daftar jauh lebih cepat dan menghindari rekursi sama sekali. Saya akan menerapkan ini sebagai:

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])

(Gunakan n + 1 di xrange jika Anda mulai menghitung urutan fibonacci Anda dari 0 bukan 1.)

Daniel
sumber
13
mengapa menggunakan O (n) ruang saat Anda dapat menggunakan O (1)?
Janus Troelsen
11
Kalau-kalau komentar ruang O (n) membingungkan: jangan gunakan daftar. Daftar akan menyimpan semua nilai ketika semua yang Anda butuhkan adalah nilai ke-n. Algoritma sederhana adalah untuk menyimpan dua angka fibonacci terakhir dan menambahkannya sampai Anda mendapatkan yang Anda butuhkan. Ada juga algoritma yang lebih baik.
Milimetri
3
@ Madathime: xrangedisebut sederhana range, dengan Python 3.
Eric O Lebigot
1
@ EOL Saya tahu ini
Mathime
7
@ Madathime Saya membuat semuanya eksplisit bagi mereka yang membaca komentar ini.
Eric O Lebigot
9

Tentu saja angka Fibonacci dapat dihitung dalam O (n) dengan menerapkan rumus Binet:

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))

Sebagai catatan berkomentar itu bukan O (1) tetapi O (n) karena 2**n. Perbedaannya adalah Anda hanya mendapatkan satu nilai, sementara dengan rekursi Anda mendapatkan semua nilai Fibonacci(n)hingga nilai itu.

pertama
sumber
8
Tidak ada ukuran maksimum panjang dalam python.
pppery
8
Perlu dicatat bahwa ini gagal untuk lebih besar nkarena ketidaktepatan floating point - perbedaan antara (1+sqrt(5))**ndan (1+sqrt(5))**(n+1)menjadi kurang dari 1 ulp, sehingga Anda mulai mendapatkan hasil yang salah.
2
Sebenarnya tidak ada bilangan bulat besar di NumPy ...
Eric O Lebigot
@Mego Apa? Perbedaan antara (1+sqrt(5))**ndan ((1+sqrt(5))**n)+1itu menjadi kurang dari 1 ulp! (kesalahan ketik kecil) Juga, {@} pertama Bukan O (1)! Menghitung 2**nmembutuhkan setidaknya O (n) waktu.
user202729
3
@ user202729 Itu tidak benar, menghitung 2**nsecara efektif O (log (n)) menggunakan Exponentiattion dengan mengkuadratkan .
Sam
6

Saya memiliki masalah serupa dengan kesalahan "Max rekursi kedalaman terlampaui". Saya menemukan kesalahan yang dipicu oleh file yang rusak di direktori yang saya ikuti os.walk. Jika Anda memiliki masalah untuk menyelesaikan masalah ini dan Anda bekerja dengan jalur file, pastikan untuk mempersempitnya, karena mungkin file yang rusak.

Tyler
sumber
2
OP memang memberikan kodenya, dan eksperimennya dapat direproduksi sesuka hati. Itu tidak melibatkan file yang rusak.
T. Verron
5
Anda benar, tetapi jawaban saya tidak ditujukan untuk OP, karena ini sudah lebih dari empat tahun yang lalu. Jawaban saya ditujukan untuk membantu mereka yang memiliki kesalahan MRD secara tidak langsung disebabkan oleh file yang rusak - karena ini adalah salah satu hasil pencarian pertama. Itu membantu seseorang, karena sudah dipilih. Terima kasih atas suaranya.
Tyler
2
Ini adalah satu-satunya hal yang saya temukan di mana saja ketika mencari masalah saya yang menghubungkan traceback "kedalaman rekursi maksimum" ke file yang rusak. Terima kasih!
Jeff
5

Jika Anda ingin mendapatkan hanya beberapa angka Fibonacci, Anda dapat menggunakan metode matriks.

from numpy import matrix

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

Ini cepat karena numpy menggunakan algoritma eksponensial cepat. Anda mendapatkan jawaban dalam O (log n). Dan itu lebih baik daripada rumus Binet karena hanya menggunakan bilangan bulat. Tetapi jika Anda ingin semua angka Fibonacci hingga n, maka lebih baik melakukannya dengan menghafal.

bebidek
sumber
Sayangnya Anda tidak dapat menggunakan numpy di sebagian besar juri pemrograman kompetitif. Tapi ya, solusi Anda adalah favorit saya. Saya telah menggunakan matriks untuk beberapa masalah. Ini adalah solusi terbaik ketika Anda membutuhkan angka fibonacci yang sangat besar dan Anda tidak dapat menggunakan modulus. Jika Anda diizinkan menggunakan modulus, periode pisano adalah cara yang lebih baik untuk melakukannya.
mentatkgs
4

Gunakan generator?

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

fibs = fib() #seems to be the only way to get the following line to work is to
             #assign the infinite generator to a variable

f = [fibs.next() for x in xrange(1001)]

for num in f:
        print num

di atas fungsi fib () diadaptasi dari: http://intermediatepythonista.com/python-generators

alex
sumber
1
alasan harus menetapkan generator ke variabel adalah karena [fibs().next() for ...]akan membuat generator baru setiap kali.
tox123
3

Seperti yang disarankan @alex , Anda dapat menggunakan fungsi generator untuk melakukan ini secara berurutan alih-alih secara rekursif.

Berikut ini persamaan kode dalam pertanyaan Anda:

def fib(n):
    def fibseq(n):
        """ Iteratively return the first n Fibonacci numbers, starting from 0. """
        a, b = 0, 1
        for _ in xrange(n):
            yield a
            a, b = b, a + b

    return sum(v for v in fibseq(n))

print format(fib(100000), ',d')  # -> no recursion depth error
martineau
sumber
2

Banyak yang merekomendasikan bahwa meningkatkan batas rekursi adalah solusi yang baik tetapi itu bukan karena akan selalu ada batasnya. Alih-alih menggunakan solusi berulang.

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)
Harun ERGUL
sumber
1

Saya ingin memberi Anda contoh untuk menggunakan memoisasi untuk menghitung Fibonacci karena ini akan memungkinkan Anda untuk menghitung angka yang jauh lebih besar menggunakan rekursi:

cache = {}
def fib_dp(n):
    if n in cache:
        return cache[n]
    if n == 0: return 0
    elif n == 1: return 1
    else:
        value = fib_dp(n-1) + fib_dp(n-2)
    cache[n] = value
    return value

print(fib_dp(998))

Ini masih bersifat rekursif, tetapi menggunakan hashtable sederhana yang memungkinkan penggunaan kembali angka Fibonacci yang dihitung sebelumnya alih-alih melakukannya lagi.

pengguna3393266
sumber
1
import sys
sys.setrecursionlimit(1500)

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

c = 998
print(fib(c, 0))
pengguna11462758
sumber
1
Jawaban yang sama ini telah diberikan berkali-kali. Tolong hapus itu.
ZF007
0

Kita dapat melakukannya menggunakan @lru_cachedekorator dan setrecursionlimit()metode:

import sys
from functools import lru_cache

sys.setrecursionlimit(15000)


@lru_cache(128)
def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fib(n - 2) + fib(n - 1)


print(fib(14000))

Keluaran

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125

Sumber

functools lru_cache

Emma
sumber
0

Kita juga bisa menggunakan variasi pendekatan pemrograman bottom-up yang dinamis

def fib_bottom_up(n):

    bottom_up = [None] * (n+1)
    bottom_up[0] = 1
    bottom_up[1] = 1

    for i in range(2, n+1):
        bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]

    return bottom_up[n]

print(fib_bottom_up(20000))
algowhiz
sumber