2

我定义了一个名为的阶乘函数fab。我使用生成器来避免堆栈溢出。但是当我尝试编写更直观的装饰器版本时出现了一些我无法理解的问题:

import types

def TCO(f):    
    def inner(*nkw,**kw):
        gen=f(*nkw,**kw)
        while isinstance(gen,types.GeneratorType):
            gen=gen.next()
        return gen
    return inner



def fab(n,s=1):
    if n<2:
        yield s
    else:
        yield fab(n-1,s*n)


x=TCO(fab)
print x(2500) #this works fine, overcoming the limitation of tail-recursion.

fab=TCO(fab) #now just change the variable name.
print fab(5) #this woks fine.
print fab(2500) #this will raise an error :maximum recursion limit exceeded

为什么?我知道它与同名有关fab,但为什么fab(5)可以正常工作?我认为当我定义时fab=TCO(fab),我实际上将fin引用的对象更改inner为 object TCO(fab)。所以当 fab(5) 运行时,gen永远不会是生成器!因为inner永不返回生成器!

我很生气……为什么?

4

3 回答 3

3
fab=TCO(fab)

语句现在使变量fab指向函数inner。之后,当

yield fab(n-1,s*n)

遇到时,它实际上不是调用原始fab函数,而是inner调用原始函数的fab函数。基本上,您每次都从生成器中出来并输入另一个函数。这就是你收到maximum recursion limit exceeded错误的原因。

于 2013-11-04T10:19:30.390 回答
1

我认为这将是一个很好的例子来解释发生了什么:

def f(x):
    print 'original'
    if x > 0:
        return f(x-1)
    return 0
g = f
def f(x):
    print 'new'
    return x
print g(5)

结果:

original
new
4

这证明:

1.when g(5) runs, origninal `f` is called, not new `f`.
2.as 5>0, 'return f(x-1)' is executed
3.new `f` is called when `f(x-1)` runs. so the result is 4.
于 2013-11-04T16:54:27.743 回答
0

您的原始版本产生一个生成器,该生成器产生一个生成器,等等。要评估该链表,您然后使用装饰器while中的循环。TCO这一切都基于您正在链接生成器以避免大堆栈这一事实。

当您为变量分配新的东西时,这个概念就被打破了fab。然后yielding fab(n-1, s*n)infab正在访问新fab变量,因此不再返回生成器,而是返回一个值。为了计算该值,使用了堆栈,因此您可以得到堆栈溢出问题。

于 2013-11-04T10:21:21.833 回答