python如何实现递归转非递归

2023-07-05 04:42:03 98

先说总结，这种方案总的来说就是机械化的强转，时间复杂度和空间复杂度没什么变化，唯二的优点可能是1.不会爆栈，2.节省了函数调用的开销

而且最终产出的代码效果不那么美观，比较冗长

思路是：当发生递归调用时，模拟函数调用的压栈。并处理入参和返回值和记录返回到当前栈的时候该继续从哪里执行

以如下递归(leetcode爬楼梯)为例

deff(n):
ifn<=2:
returnn
returnf(n-1)+f(n-2)

第一步：

将涉及到递归调用的，单独变成最简单的一行

deff(n):
ifn<=2:
returnn
a=f(n-1)
b=f(n-2)
returna+b

第二步:

我们需要模拟递归栈调用，当执行完递归回到当前栈的时候需要知道从哪里继续执行，所以需要一个flag标记，开始的时候为0，我们先手工标记一下，再后序转换的时候可以方便查看

deff(n):
ifn<=2:
returnn
a=f(n-1)
#flag1
b=f(n-2)
#flag2
returna+b

第三步:

构建解题模版

deff_iter(n):
stack=[]
#入参，接收递归调用的(a,b),flag
base_frame=[None,{'a':None,'b':None},0]
first_frame=[(n,'a'),{},0]
stack.append(base_frame)
stack.append(first_frame)
whilelen(stack)>1:
arg,local,flag=stack[-1]
arg,aorb=arg
ifflag==0:
pass
elifflag==1:
pass
elifflag==2:
pass
returnstack[0][-2]['a']

first_frame=[(n,'a'),{},0]注意此时接收函数返回的时候为什么是一个字典，并且调用参数的时候传参多了一个'a'，因为函数被递归调用了两次，分别得到一个a和b,所以在返回的时候需要知道返回是给a还是给b，如果只递归调用了一次，那么就不需要带上'a'，返回的时候也不用是字典了，最后整个函数执行完成之后，base_frame里面就是最终的答案

第四步：

填充骨架，记住两点就可以了

函数调用的时候，先将当前栈的flag修改(等再次执行到当前栈的时候知道从哪里继续执行)
发生return的时候stack.pop出栈后，将结果写入栈顶的结果字典
其他照抄就行

deff_iter(n):
stack=[]
#入参，局部变量(a,b),flag
base_frame=[None,{'a':None,'b':None},0]
first_frame=[(n,'a'),{},0]
stack.append(base_frame)
stack.append(first_frame)
whilelen(stack)>1:
arg,local,flag=stack[-1]
arg,aorb=arg
ifflag==0:
ifarg<=2:
stack.pop()
stack[-1][-2][aorb]=arg
else:
stack[-1][-1]=1
new_frame=[(arg-1,'a'),{},0]
stack.append(new_frame)
elifflag==1:
stack[-1][-1]=2
new_frame=[(arg-2,'b'),{},0]
stack.append(new_frame)
elifflag==2:
a,b=local['a'],local['b']
stack.pop()
stack[-1][-2][aorb]=a+b
returnstack[0][-2]['a']

完结，撒花:tada:

另外：有一些函数编程语言，能将所有的递归调用转化成尾调用(非尾递归)，这样就不会发生爆栈的问题，但是目前流行的大多数语言都是没有这个功能的

附加练习

有兴趣可以自己按步骤试一试,如有见解，欢迎探讨:clap:

二叉树中序遍历

递归版本

classNode:
def__init__(self,val):
self.val=val
self.left=None
self.right=None

deflist2tree(l):
iflen(l)==1:
returnNode(l[0])
mid=(len(l)-1)>>1
root=Node(l[mid])
root.left=list2tree(l[:mid])
root.right=list2tree(l[mid+1:])
returnroot

definorder_recursive(root):
ifnotroot:
return[]
returninorder_recursive(root.left)+[root.val]+inorder_recursive(root.right)

l=list(range(1,2<<2))
tree=list2tree(l)

c=inorder_recursive(tree)
print(c)

非递归版本

classNode:
def__init__(self,val):
self.val=val
self.left=None
self.right=None

deflist2tree(l):
stack=[]
#(root,left_right),{'a':,'b':},flag
base_frame=[None,{},0]
first_frame=[(l,'a'),{},0]
stack.append(base_frame)
stack.append(first_frame)
whilelen(stack)>1:
cur=stack[-1]
arg,local,flag=cur
arg,aorb=arg
mid=(len(arg)-1)>>1
ifflag==0:
iflen(arg)==1:
stack.pop()
stack[-1][-2][aorb]=Node(arg[0])
else:
stack[-1][-1]=1
new_frame=[(arg[:mid],'a'),{},0]
stack.append(new_frame)
elifflag==1:
stack[-1][-1]=2
new_frame=[(arg[mid+1:],'b'),{},0]
stack.append(new_frame)
elifflag==2:
left,right=local['a'],local['b']
root=Node(arg[mid])
root.left=left
root.right=right
stack.pop()
stack[-1][-2][aorb]=root
returnstack[0][-2]['a']

definorder_recursive(root):
stack=[]
base_frame=[None,{},0]
first_frame=[(root,'a'),{'a':None,'c':None},0]
stack.append(base_frame)
stack.append(first_frame)
whilelen(stack)>1:
cur=stack[-1]
arg,local,flag=cur
arg,left_right=arg
ifflag==0:
ifnotarg:
stack.pop()
stack[-1][-2][left_right]=[]
else:
stack[-1][-1]=1
new_frame=[(arg.left,'a'),{},0]
stack.append(new_frame)
elifflag==1:
stack[-1][-1]=2
new_frame=[(arg.right,'c'),{},0]
stack.append(new_frame)
elifflag==2:
b=[arg.val]
ret=local['a']+b+local['c']
stack.pop()
stack[-1][-2][left_right]=ret
returnstack[0][-2]['a']

l=list(range(1,2<<2))
tree=list2tree(l)

c=inorder_recursive(tree)
print(c)

以上就是python如何实现递归转非递归的详细内容，更多关于python递归转非递归的资料请关注毛票票其它相关文章！

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。