Apakah Python mengoptimalkan rekursi ekor?

Saya memiliki cuplikan kode berikut yang gagal dengan kesalahan berikut:

RuntimeError: kedalaman rekursi maksimum terlampaui

Saya mencoba menulis u>

 def trisum(n, csum): if n == 0: return csum else: return trisum(n - 1, csum + n) print(trisum(1000, 0)) 

Haruskah saya menyimpulkan bahwa Python tidak melakukan semua jenis TCO, atau apakah saya hanya perlu mendefinisikannya secara berbeda?

144
27 нояб. diatur oleh Jordan Mack 27 nov. 2012-11-27 22:53 '12 pada pukul 10:53 2012-11-27 22:53
@ 6 balasan

Tidak, dan itu tidak akan pernah terjadi, karena Guido lebih suka memiliki jejak yang tepat.

http://neopythonic.blogspot.com.au/2009/04/tail-recursion-elimination.html

http://neopythonic.blogspot.com.au/2009/04/final-words-on-tail-calls.html

Anda dapat secara manual menghi>

 >>> def trisum(n, csum): ... while True: # change recursion to a while loop ... if n == 0: ... return csum ... n, csum = n - 1, csum + n # update parameters instead of tail recursion >>> trisum(1000,0) 500500 
151
27 нояб. Balasan yang diberikan oleh John La Rooy 27 November 2012-11-27 22:55 '12 pada jam 10:55 2012-11-27 22:55

Sunting (2015-07-02): Seiring waktu, jawaban saya menjadi cukup populer, dan karena awalnya lebih masuk akal daripada yang lain, saya memutuskan untuk meluangkan waktu dan mengu>

Sunting (2015-07-12): Akhirnya, saya menerbitkan sebuah modul yang melakukan optimasi panggilan ekor (memproses rekursi dan kelanjutan ekor): https://github.com/baruchel/tco

Optimasi rekursi ekor di python

Sudah sering diperdebatkan bahwa rekursi ekor tidak sesuai dengan metode pengkodean pythonic dan bahwa seseorang tidak perlu khawatir tentang cara memasukkannya ke dalam loop. Saya tidak ingin berdebat dengan sudut pandang ini; Kadang-kadang saya suka mencoba atau memperkenalkan ide-ide baru sebagai fungsi rekursif ekor, dan tidak dengan loop karena berbagai alasan (dengan fokus pada bukan pada proses, memiliki dua puluh fungsi pendek pada layar saya di fungsi yang sama dan tidak hanya tiga "pythonic" yang bekerja pada daripada mengedit kode saya, dll.).

Mengoptimalkan rekursi ekor dengan Python sebenarnya cukup sederhana. Meskipun dikatakan bahwa ini tidak mungkin atau sangat sulit, saya pikir ini dapat dicapai dengan bantuan solusi yang elegan, singkat dan umum; Saya bahkan berpikir bahwa sebagian besar solusi ini tidak menggunakan fungsi Python berbeda dari yang seharusnya. Ekspresi lambda murni yang bekerja bersama-sama dengan loop yang sangat standar menghasilkan alat yang cepat, efisien, dan sepenuhnya digunakan untuk mengimplementasikan optimisasi rekursi ekor.

Sebagai kenyamanan pribadi, saya menulis modul kecil yang mengimplementasikan optimasi ini dengan dua cara berbeda. Saya ingin membahas di sini tentang dua fungsi utama saya.

Cara bersih: ganti Y combinator

Y combinator dikenal; ini memungkinkan Anda untuk menggunakan fungsi lambda secara rekursif, tetapi itu saja tidak memungkinkan panggilan rekursif dibangun ke dalam loop. Lambda Calculus sendiri tidak dapat melakukan ini. Namun, perubahan kecil pada Y combinator dapat melindungi panggilan rekursif yang sebenarnya akan dievaluasi. Karena itu, evaluasi dapat ditunda.

Berikut adalah ungkapan terkenal untuk kombinator Y:

 lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args))) 

Dengan sedikit perubahan, saya bisa mendapatkan:

 lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args))) 

Alih-alih memanggil dirinya sendiri, fungsi f sekarang mengembalikan fungsi yang melakukan panggilan yang sama, tetapi karena mengembalikannya, evaluasi dapat dilakukan kemudian dari luar.

Kode saya adalah:

 def bet(func): b = (lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args))))(func) def wrapper(*args): out = b(*args) while callable(out): out = out() return out return wrapper 

Fungsi tersebut dapat digunakan sebagai berikut; Berikut adalah dua contoh dengan versi rekursif ekor faktorial dan Fibonacci:

 >>> from recursion import * >>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) ) >>> fac(5,1) 120 >>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) ) >>> fibo(10,0,1) 55 

Jelas, kedalaman rekursi tidak lagi menjadi masalah:

 >>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000) 42 

Ini, tentu saja, adalah satu-satunya tujuan sebenarnya dari fungsi tersebut.

Hanya satu hal yang tidak dapat dilakukan dengan optimasi ini: tidak dapat digunakan dengan fungsi rekursif ekor yang mengevaluasi fungsi lain (ini mengikuti fakta bahwa objek yang dipanggil diperlakukan sebagai panggilan rekursif lebih lanjut tanpa perbedaan). Karena saya biasanya tidak memerlukan fungsi seperti itu, saya sangat senang dengan kode di atas. Namun, untuk menyediakan modul yang lebih umum, saya pikir sedikit lebih banyak untuk menemukan beberapa cara untuk menyelesaikan masalah ini (lihat bagian selanjutnya).

Adapun kecepatan proses ini (tapi ini bukan masalah nyata), itu terjadi cukup baik; fungsi rekursif ekor dievaluasi lebih cepat daripada dengan kode berikut ini menggunakan ekspresi yang lebih sederhana:

 def bet1(func): def wrapper(*args): out = func(lambda *x: lambda: x)(*args) while callable(out): out = func(lambda *x: lambda: x)(*out()) return out return wrapper 

Saya pikir evaluasi satu ekspresi, bahkan yang kompleks, terjadi jauh lebih cepat daripada mengevaluasi beberapa ekspresi sederhana, yang merupakan kasus dalam versi kedua ini. Saya tidak menyimpan fitur baru ini dalam modul saya, dan saya tidak melihat keadaan apa pun ketika itu dapat digunakan sebagai ganti yang "resmi".

Gaya Berlanjut dengan Pengecualian

Berikut ini adalah fungsi yang lebih umum; ia mampu memproses semua fungsi rekursif ekor, termasuk yang mengembalikan fungsi lainnya. Panggilan rekursif diakui dari nilai balik lainnya menggunakan pengecualian. Solusi ini lebih lambat dari yang sebelumnya; kode yang lebih cepat mungkin dapat ditulis menggunakan beberapa makna khusus seperti "bendera" yang ditemukan di loop utama, tetapi saya tidak menyukai gagasan untuk menggunakan makna khusus atau kata kunci internal. Ada beberapa interpretasi konyol tentang penggunaan pengecualian: jika Python tidak suka panggilan rekursif ekor, pengecualian harus terjadi ketika panggilan rekursif ekor terjadi, dan jalur python akan menangkap pengecualian untuk menemukan beberapa solusi bersih yang benar-benar terjadi di sini ...

 class _RecursiveCall(Exception): def __init__(self, *args): self.args = args def _recursiveCallback(*args): raise _RecursiveCall(*args) def bet0(func): def wrapper(*args): while True: try: return func(_recursiveCallback)(*args) except _RecursiveCall as e: args = e.args return wrapper 

Sekarang Anda dapat menggunakan semua fitur. Dalam contoh berikut, f(n) dievaluasi untuk nilai positif n:

 >>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) ) >>> f(5)(42) 42 

Tentu saja, dapat diperdebatkan bahwa pengecualian tidak dimaksudkan untuk digunakan untuk maksud mengarahkan u>goto , atau lebih tepatnya, semacam kelanjutan dari lewatnya gaya), yang harus saya akui. Tetapi, sekali lagi, gagasan untuk menggunakan try garis tunggal yang merupakan return menurut saya lucu: kami berusaha mengembalikan sesuatu (perilaku normal), tetapi kami tidak dapat melakukannya karena panggilan rekursif (pengecualian).

Jawaban awal (2013-08-29).

Saya menulis sebuah plugin yang sangat kecil untuk menangani rekursi ekor. Anda dapat menemukannya dengan penjelasan saya di sana: https://groups.google.com/forum/?hl=fr#!topic/comp.>

Ia dapat menyisipkan fungsi lambda yang ditulis menggunakan gaya rekursi ekor ke dalam fungsi lain yang akan mengevaluasinya sebagai loop.

Fitur yang paling menarik dari fungsi kecil ini, menurut pendapat saya, adalah bahwa fungsi tersebut tidak bergantung pada beberapa peretasan perangkat lunak kotor, tetapi pada kalkulus lambda sederhana: perilaku fungsi berubah ke yang lain ketika dimasukkan ke lambda lain. fungsi yang sangat mirip dengan Y-combinator.

Salam

29 авг. Balasan yang diberikan oleh Thomas Baruchel 29 Agustus 2013-08-29 12:08 '13 pada 12:08 2013-08-29 12:08

Kata Guido ada di http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

Saya baru-baru ini memposting entri di blog sejarah Python saya tentang asal-usul fungsi Python. Catatan samping tentang kurangnya eliminasi rekursi dukungan ekor (TRE) segera menyebabkan beberapa komentar tentang betapa disayangkan bahwa Python tidak melakukan ini, termasuk tautan ke entri blog terbaru oleh orang lain yang mencoba untuk “membuktikan” bahwa TRE dapat ditambahkan ke Python dengan mudah. Jadi biarkan saya mempertahankan posisi saya (dan ini yang saya tidak ingin TRE dalam bahasa). Jika Anda membutuhkan jawaban singkat, cukup unpythonic. Inilah jawaban panjangnya:

19
27 нояб. Jawaban diberikan oleh Jon Clements 27 November 2012-11-27 22:56 '12 pada pukul 10:56 2012-11-27 22:56

CPython tidak, dan mungkin tidak akan pernah, mendukung optimalisasi ekor berdasarkan pernyataan Guido tentang masalah ini. Saya telah mendengar argumen bahwa ini membuat debugging sulit karena cara mengubah jejak stack.

6
27 нояб. jawabannya diberikan secara rekursif 27 Nov. 2012-11-27 22:55 '12 pada jam 10:55 2012-11-27 22:55

Coba implementasi TCO makropi eksperimental untuk ukuran.

3
15 июля '15 в 3:11 2015-07-15 03:11 balasan yang diberikan oleh Mark Lawrence pada 15 Juli '15 di 3:11 2015-07-15 03:11

Selain mengoptimalkan rekursi ekor, Anda dapat secara manual mengatur kedalaman rekursi:

 import sys sys.setrecursionlimit(5500000) print("recursion limit:%d " % (sys.getrecursionlimit())) 
1
09 июня '16 в 17:38 2016-06-09 17:38 jawabannya diberikan zhenv5 09 Juni '16 pada 17:38 2016-06-09 17:38