Home  >  Article  >  Backend Development  >  如何看待以及理解Python的这种尾递归优化?

如何看待以及理解Python的这种尾递归优化?

WBOY
WBOYOriginal
2016-06-06 16:23:431429browse

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,但算不上“性能优化”意义上的优化。 突破人为设定的1000条限制,跟一般意义上的尾递归优化是有区别的。
Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn