
























有Python函数一枚,用递归写成。运行时超出Python的递归深度,现欲将其由在堆栈中分配空间改为在堆中分配空间(即用malloc)。
首先,from heaprecursion import *。然后对目标函数进行改造,假设要改造的递归函数为def func(p1, p2):
1.把函数中的递归调用func(exp1,exp2)改成yield RECURSION(exp1,exp2),即把所有"func"替换成"yield RECURSION"。
2.把函数中所有的"return"替换成yield。如果是尾递归return func(exp1, exp2)则改成yield TAIL(exp1, exp2)。
最后这样调用改造好的函数:heaprun(f, exp1, exp2)

from heaprecursion import *def sumlist(l):
if len(l)==0: return 0
x=l.pop()
y=sumlist(l)
return x+y
改造成这样:
def sumlist2(l):t
=(1,def forward(it, arg):
# move iterator 'it' by calling 'next'(when 'arg' is None) or 'send'
# return what 'next' or 'send' returns, or None if 'it' is at its end
try:
if arg==None:
return it.next()
else:
return it.send(arg)
except StopIteration: pass
return Noneclass RECURSION(object):
def __init__(self, *args):
self.args=args
class TAIL(RECURSION):
passdef heaprun(f, *args):
stack=[f(*args)]
param=None
while(1):
v=forward(stack[-1], param)
if isinstance(v, RECURSION):
if type(v)==TAIL:
stack.pop()
stack.append(f(*(v.args)))
param=None
else:
stack.pop()
if stack:
param=v
else:
return v
目前heaprecursion.py只对自递归起作用,还不能用于互递归。
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。