我有以下两个相互递归的函数
由于python不能很好地处理尾部调用优化,程序员应该将这些函数表示为有状态循环。python社区使用什么技术将这种等式转换为显式循环?你知道吗
或者这些变换依赖于算法,每个递归函数必须单独分析?你知道吗
递归实现:
让C1 = xpa, C2 = p and C3 = xpb
然后
def obaraSaika(p,s00x,i,j,xpa,xpb):
if i < 0 or j < 0: return 0
if i == 0 and j == 0: return s00x
if i >= 1: return xpa*(obaraSaika(p,s00x,i-1,j,xpa,xpb)) + \
p*((i-1)*(obaraSaika(p,s00x,i-2,j)) + j*(obaraSaika(p,s00x,i-1,j-1,xpa,xpb) ) )
if j >= 1: return xpb*(obaraSaika(p,s00x,i-1,j,xpa,xpb)) + \
p*(i * (obaraSaika(p,s00x,i-1,j-1)) + (j-1)*(obaraSaika(p,s00x,i,j-2,xpa,xpb) ) )
这个实现的思想是首先使用i
索引遍历树,然后使用j
索引缩减树。你知道吗
将任何递归算法转换为非递归等价算法都很简单。你知道吗
当您执行递归调用时,实际上您所做的是将一组参数推送到堆栈上。这个堆栈由Python解释器提供给您。你知道吗
所以,不使用递归重写算法的方法是。。。你自己管理堆栈!当您要进行递归调用时,取而代之的是您将要传递的所有参数,并将它们推送到堆栈对象上。然后有一个“驱动程序”循环,它会反复弹出堆栈并执行其中列出的计算。你知道吗
这类程序的特征是有一个堆栈对象,你用一个初始状态元组/对象来初始化它,然后是一个
while len(stack) > 0
循环,它一直运行到你完成为止。你知道吗您基本上只做递归所做的事情,但是当您自己管理相关的数据结构时,它为您提供了获得效率的更好机会。你知道吗
这种特殊类型的变换适用于任何算法。其他的,特别是那些涉及在不同的函数调用之间传递全局状态的函数,依赖于算法。你知道吗
相关问题 更多 >
编程相关推荐