先说总结，这种方案总的来说就是机械化的强转，时间复杂度和空间复杂度没什么变化，唯二的优点可能是1. 不会爆栈，2. 节省了函数调用的开销
而且最终产出的代码效果不那么美观，比较冗长
思路是：当发生递归调用时，模拟函数调用的 压栈 。并处理 入参 和 返回值 和 记录返回到当前栈的时候该继续从哪里执行
以如下递归( leetcode爬楼梯 )为例
def f(n): if n <= 2: return n return f(n - 1) + f(n - 2)
第一步：
将涉及到递归调用的，单独变成最简单的一行
def f(n): if n <= 2: return n a = f(n - 1) b = f(n - 2) return a + b
第二步:
我们需要模拟递归栈调用，当执行完递归回到当前栈的时候需要知道从哪里继续执行，所以需要一个flag标记，开始的时候为0，我们先手工标记一下，再后序转换的时候可以方便查看
def f(n): if n <= 2: return n a = f(n - 1) # flag1 b = f(n - 2) # flag2 return a + b
第三步:
构建解题模版
def f_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)
while len(stack) > 1:
arg, local, flag = stack[-1]
arg, aorb = arg
if flag == 0:
pass
elif flag == 1:
pass
elif flag == 2:
pass
return stack[0][-2]['a']
first_frame =
本文来源gao!%daima.com搞$代*!码$网9
[(n, ‘a’), {}, 0] 注意此时接收函数返回的时候为什么是一个字典，并且调用参数的时候传参多了一个’a’，因为函数被递归调用了两次，分别得到一个a和b, 所以在返回的时候需要知道返回是给a还是给b， 如果只递归调用了一次，那么就不需要带上’a’，返回的时候也不用是字典了，最后整个函数执行完成之后，base_frame里面就是最终的答案
第四步：
填充骨架，记住两点就可以了
函数调用的时候，先将当前栈的flag修改(等再次执行到当前栈的时候知道从哪里继续执行)
发生 return 的时候 stack.pop 出栈后，将结果写入栈顶的结果字典
其他照抄就行
def f_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)
while len(stack) > 1:
arg, local, flag = stack[-1]
arg, aorb = arg
if flag == 0:
if arg <= 2:
stack.pop()
stack[-1][-2][aorb] = arg
else:
stack[-1][-1] = 1
new_frame = [(arg - 1, 'a'), {}, 0]
stack.append(new_frame)
elif flag == 1:
stack[-1][-1] = 2
new_frame = [(arg - 2, 'b'), {}, 0]
stack.append(new_frame)
elif flag == 2:
a, b = local['a'], local['b']
stack.pop()
stack[-1][-2][aorb] = a + b
return stack[0][-2]['a']
完结，撒花:tada:
另外：有一些函数编程语言，能将所有的递归调用转化成尾调用(非尾递归)，这样就不会发生爆栈的问题，但是目前流行的大多数语言都是没有这个功能的
附加练习
有兴趣可以自己按步骤试一试, 如有见解，欢迎探讨:clap:
二叉树中序遍历
递归版本
class Node: def __init__(self, val): self.val = val self.left = None self.right = None def list2tree(l): if len(l) == 1: return Node(l[0]) mid = (len(l) - 1) >> 1 root = Node(l[mid]) root.left = list2tree(l[:mid]) root.right = list2tree(l[mid + 1:]) return root def inorder_recursive(root): if not root: return [] return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right) l = list(range(1, 2 << 2)) tree = list2tree(l) c = inorder_recursive(tree) print(c)
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：python如何实现递归转非递归
转载请注明原文链接：python如何实现递归转非递归
