如何看待以及理解Python的這種尾遞歸優化？

01-12

Python之父曾經明確表示Python將不會支持尾遞歸優化。但是最近查資料的時候發現了一種奇特的用decorator來進行尾遞歸優化的方法
Tail Call Optimization Decorator ? Python recipes ? ActiveState Code

Python與尾遞歸
首先這個是真正的尾遞歸優化么？其次如何理解這段代碼它到底做了哪些事？

TCO，tail-call optimization，其實有多種解讀方式。

最常見的解讀方式是：對於尾調用的函數調用，不要浪費棧空間，而要復用調用者的棧空間。這樣的結果就是一長串尾調用不會爆棧，而沒有TCO的話同樣的調用就會爆棧。

從這個意義上說，題主貼的那個recipe確實達到了TCO的部分目的：

通過stack introspection查看調用鏈上的調用者之中有沒有自己
有的話，通過拋異常來迫使棧回退（stack unwind）到之前的一個自己的frame
在回退到的frame接住異常，拿出後來調用的參數，用新參數再次調用自己

這樣就可以讓尾遞歸不爆棧。但這樣做性能是沒保證的…而且對於完全沒遞歸過的一般尾調用也不起作用。

一種對TCO的常見誤解是：由編譯器或運行時系統把尾調用/尾遞歸實現得很快。這不是TCO真正要強調的事情——不爆棧才是最重要的。也就是說其實重點不在「優化」，而在於「尾調用不爆棧」這個語義保證。

「proper tail-call」的叫法遠比「tail-call optimization」來得合適。

因而像題主說的那種做法，可以算部分TCO，但算不上「性能優化」意義上的優化。

更新：

很遺憾，之前這些都是錯誤的做法。

不久前剛剛做好了python的模式匹配庫，包含了尾遞歸優化，實現利用了coroutine。

https://github.com/Xython/pattern-matching

也可以大搖大擺地現代編程了。

關於尾遞歸實現：

很簡單，永遠不要在函數內部去調用自己，甚至不要調用任何東西。每一次調用，都讓外層一個agent來做。保證函數棧深永遠不超過2或3即可。

——————————————————————

原文（原文價值不高）：

把需要優化的函數的return改成yield，外面套個裝飾器，就叫tail_call_opm。裝飾器最內層的邏輯是

while True: try: ret=next(ret) except: return ret

這個應該沒有復用釋放的空間…但刷題時換了這個就不爆棧了。返回閉包的話情況應該會更複雜一些。

不失為一個快速簡單的辦法。

說一個一個比較微妙的點，

就是修飾函數裡面調用的g是被修飾的原函數，但原函數g進行遞歸的時候調用的卻是被魔改過的g，挺有意思的。

突破人為設定的1000條限制，跟一般意義上的尾遞歸優化是有區別的。