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?
line <n>, in <module>
in stack traces) dan kode ini membutuhkan 2 frame stackn=1
(karena case dasarnyan < 1
, jadi untukn=1
itu masih berulang). Dan saya kira batas rekursi tidak inklusif, seperti "kesalahan ketika Anda menekan 1000" tidak "kesalahan jika Anda melebihi 1000 (1001)".997 + 2
kurang dari 1000 sehingga tidak berfungsi998 + 2
karena mencapai batas.recursive_function(997)
berfungsi, rusak pada998
. Ketika Anda menyebutnyarecursive_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.Jawaban:
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.getrecursionlimit
dan mengubah batas rekursisys.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.
sumber
sys
danresource
modul: stackoverflow.com/a/16248113/205521Sepertinya Anda hanya perlu mengatur kedalaman rekursi yang lebih tinggi :
sumber
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 :
sumber
Jika Anda sering perlu mengubah batas rekursi (mis. Saat memecahkan teka-teki pemrograman), Anda dapat menetapkan pengelola konteks sederhana seperti ini:
Kemudian untuk memanggil fungsi dengan batas khusus yang dapat Anda lakukan:
Saat keluar dari badan
with
pernyataan, batas rekursi akan dikembalikan ke nilai default.sumber
resource
. Tanpa itu, Anda akan mendapatkan Segmentasi Fault dan seluruh proses Python akan macet jika Andasetrecursionlimit
terlalu 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).Gunakan bahasa yang menjamin optimisasi panggilan ekor. Atau gunakan iterasi. Atau, dapatkan lucu dengan dekorator .
sumber
ulimit -s
dari tumpukan frame, ya itu stackoverflow.com/a/50120316resource.setrlimit
juga harus digunakan untuk menambah ukuran tumpukan dan mencegah segfaultKernel 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
getrlimit
dansetrlimit
panggilan sistem.Python menawarkan akses ke panggilan sistem tersebut melalui
resource
modul.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:
Nilai default untuk saya adalah 8MB.
Lihat juga:
Diuji pada Ubuntu 16.10, Python 2.7.12.
sumber
rlimit_stack
setelah perbaikan Stack Clash dapat mengakibatkan kegagalan atau masalah terkait. Lihat juga MasalahSaya 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:
(Gunakan n + 1 di xrange jika Anda mulai menghitung urutan fibonacci Anda dari 0 bukan 1.)
sumber
xrange
disebut sederhanarange
, dengan Python 3.Tentu saja angka Fibonacci dapat dihitung dalam O (n) dengan menerapkan rumus Binet:
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 nilaiFibonacci(n)
hingga nilai itu.sumber
n
karena ketidaktepatan floating point - perbedaan antara(1+sqrt(5))**n
dan(1+sqrt(5))**(n+1)
menjadi kurang dari 1 ulp, sehingga Anda mulai mendapatkan hasil yang salah.(1+sqrt(5))**n
dan((1+sqrt(5))**n)+1
itu menjadi kurang dari 1 ulp! (kesalahan ketik kecil) Juga, {@} pertama Bukan O (1)! Menghitung2**n
membutuhkan setidaknya O (n) waktu.2**n
secara efektif O (log (n)) menggunakan Exponentiattion dengan mengkuadratkan .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.sumber
Jika Anda ingin mendapatkan hanya beberapa angka Fibonacci, Anda dapat menggunakan metode matriks.
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.
sumber
Gunakan generator?
di atas fungsi fib () diadaptasi dari: http://intermediatepythonista.com/python-generators
sumber
[fibs().next() for ...]
akan membuat generator baru setiap kali.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:
sumber
Banyak yang merekomendasikan bahwa meningkatkan batas rekursi adalah solusi yang baik tetapi itu bukan karena akan selalu ada batasnya. Alih-alih menggunakan solusi berulang.
sumber
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:
Ini masih bersifat rekursif, tetapi menggunakan hashtable sederhana yang memungkinkan penggunaan kembali angka Fibonacci yang dihitung sebelumnya alih-alih melakukannya lagi.
sumber
sumber
Kita dapat melakukannya menggunakan
@lru_cache
dekorator dansetrecursionlimit()
metode:Keluaran
Sumber
functools lru_cache
sumber
Kita juga bisa menggunakan variasi pendekatan pemrograman bottom-up yang dinamis
sumber