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

WBOY
Libérer: 2016-06-06 16:23:43
original
1429 Les gens l'ont consulté

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条限制,跟一般意义上的尾递归优化是有区别的。
Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!