Saya memiliki potongan kode berikut yang gagal dengan kesalahan berikut:

RuntimeError: kedalaman rekursi maksimum terlampaui

Saya mencoba untuk menulis ulang ini untuk memungkinkan optimasi rekursi ekor (TCO). Saya percaya bahwa kode ini seharusnya berhasil jika TCO terjadi.

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?

Tidak, dan itu tidak akan pernah terjadi sejak Guido van Rossum memilih untuk dapat memiliki traceback yang tepat:

Eliminasi Rekursi Ekor (2009-04-22)

Kata-Kata Akhir tentang Panggilan Ekor (2009-04-27)

Anda dapat secara manual menghilangkan rekursi dengan transformasi seperti ini:

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

Saya menerbitkan sebuah modul yang melakukan optimasi panggilan-tail (menangani gaya rekursi ekor dan passing-kelanjutan): https://github.com/baruchel/tco

Mengoptimalkan rekursi ekor dengan Python

Telah sering diklaim bahwa rekursi ekor tidak sesuai dengan cara pengkodean Pythonic dan bahwa seseorang seharusnya tidak peduli bagaimana cara menanamkannya dalam satu lingkaran. Saya tidak ingin berdebat dengan sudut pandang ini; Namun kadang-kadang saya suka mencoba atau menerapkan ide-ide baru sebagai fungsi rekursif ekor daripada dengan loop karena berbagai alasan (berfokus pada ide daripada pada proses, memiliki dua puluh fungsi pendek di layar saya dalam waktu yang sama daripada hanya tiga "Pythonic" fungsi, bekerja dalam sesi interaktif daripada mengedit kode saya, dll.)

Mengoptimalkan rekursi ekor dengan Python sebenarnya cukup mudah. Meskipun dikatakan tidak mungkin atau sangat rumit, saya pikir itu dapat dicapai dengan solusi yang elegan, singkat dan umum; Saya bahkan berpikir bahwa sebagian besar solusi ini tidak menggunakan fitur Python selain dari yang seharusnya. Ekspresi lambda yang bersih bekerja bersama dengan loop yang sangat standar menghasilkan alat yang cepat, efisien, dan sepenuhnya dapat digunakan untuk mengimplementasikan optimisasi rekursi ekor.

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

Cara bersih: memodifikasi combinator Y

The Y combinator terkenal; itu memungkinkan untuk menggunakan fungsi lambda secara rekursif, tetapi tidak memungkinkan dengan sendirinya untuk menanamkan panggilan rekursif dalam satu lingkaran. Kalkulus Lambda sendiri tidak dapat melakukan hal seperti itu. Namun sedikit perubahan pada Y combinator dapat melindungi panggilan rekursif untuk benar-benar dievaluasi. Evaluasi dengan demikian dapat ditunda.

Berikut adalah ungkapan terkenal untuk penggabung 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 nanti 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 ini dapat digunakan dengan cara berikut; berikut adalah dua contoh dengan versi faktorial dan Fibonacci rekursif ekor:

>>> 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 tujuan sebenarnya dari fungsi ini.

Hanya satu hal yang tidak dapat dilakukan dengan optimasi ini: itu tidak dapat digunakan dengan fungsi rekursif ekor mengevaluasi ke fungsi lain (ini berasal dari kenyataan bahwa objek yang dikembalikan callable semua ditangani sebagai panggilan rekursif lebih lanjut tanpa perbedaan). Karena saya biasanya tidak memerlukan fitur seperti itu, saya sangat senang dengan kode di atas. Namun, untuk menyediakan modul yang lebih umum, saya berpikir sedikit lebih banyak untuk menemukan solusi untuk masalah ini (lihat bagian selanjutnya).

Mengenai kecepatan proses ini (yang bukan masalah sebenarnya), itu terjadi cukup baik; fungsi rekursif ekor bahkan dievaluasi jauh 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 mengevaluasi satu ekspresi, bahkan rumit, jauh lebih cepat daripada mengevaluasi beberapa ekspresi sederhana, yang merupakan kasus dalam versi kedua ini. Saya tidak menyimpan fungsi baru ini dalam modul saya, dan saya tidak melihat keadaan di mana ia bisa digunakan daripada yang "resmi".

Gaya passing berkelanjutan dengan pengecualian

Berikut ini adalah fungsi yang lebih umum; ia mampu menangani semua fungsi rekursif ekor, termasuk yang mengembalikan fungsi lainnya. Panggilan rekursif diakui dari nilai balik lainnya dengan menggunakan pengecualian. Solusi ini lebih lambat dari yang sebelumnya; kode yang lebih cepat mungkin dapat ditulis dengan menggunakan beberapa nilai khusus sebagai "bendera" yang terdeteksi di loop utama, tetapi saya tidak suka gagasan menggunakan nilai khusus atau kata kunci internal. Ada beberapa interpretasi lucu menggunakan pengecualian: jika Python tidak suka panggilan rekursif ekor, pengecualian harus dimunculkan ketika panggilan ekor rekursif terjadi, dan cara Pythonic akan menangkap pengecualian untuk menemukan beberapa bersih solusi, yang sebenarnya apa yang 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 semua fungsi bisa digunakan. Dalam contoh berikut, f(n)dievaluasi ke fungsi identitas 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 mengarahkan ulang penerjemah (sebagai semacam gotopernyataan atau mungkin semacam gaya kelanjutan lewat), yang harus saya akui. Tetapi, sekali lagi, saya menemukan ide lucu menggunakan trysatu baris sebagai returnpernyataan: kami mencoba mengembalikan sesuatu (perilaku normal) tetapi kami tidak dapat melakukannya karena panggilan rekursif terjadi (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.lang.python/dIsnJ2BoBKs

Ini dapat menanamkan fungsi lambda ditulis dengan gaya rekursi ekor di fungsi lain yang akan mengevaluasinya sebagai loop.

Fitur yang paling menarik dalam fungsi kecil ini, menurut pendapat saya, adalah bahwa fungsi tidak bergantung pada beberapa hack pemrograman kotor tetapi pada kalkulus lambda belaka: perilaku fungsi diubah ke yang lain ketika dimasukkan dalam fungsi lambda lain yang terlihat sangat seperti combinator Y.

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

Saya baru-baru ini memposting entri di blog Python History saya tentang asal-usul fitur fungsional Python. Sebuah komentar sampingan tentang tidak mendukung penghapusan rekursi ekor (TRE) segera memicu beberapa komentar tentang betapa sayangnya bahwa Python tidak melakukan ini, termasuk tautan ke entri blog terbaru oleh orang lain yang mencoba "membuktikan" bahwa TRE dapat ditambahkan ke Python dengan mudah. Jadi izinkan saya mempertahankan posisi saya (yaitu saya tidak ingin TRE dalam bahasa ini). Jika Anda ingin jawaban singkat, itu hanya unpythonic. Inilah jawaban panjangnya:

CPython tidak dan mungkin tidak akan pernah mendukung optimasi panggilan berdasarkan pernyataan Guido van Rossum pada subjek.

Saya pernah mendengar argumen yang membuat debugging lebih sulit karena cara memodifikasi jejak stack.

Coba implementasi TCO makropi eksperimental untuk ukuran.

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

import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))