您的位置:首页技术文章
文章详情页

python如何实现递归转非递归

【字号: 日期:2022-06-27 10:24:52浏览:3作者:猪猪

先说总结,这种方案总的来说就是机械化的强转,时间复杂度和空间复杂度没什么变化,唯二的优点可能是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 = [(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 = Nonedef 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 rootdef 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)

非递归版本

class Node: def __init__(self, val): self.val = val self.left = None self.right = Nonedef list2tree(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) while len(stack) >1: cur = stack[-1] arg, local, flag = cur arg, aorb = arg mid = (len(arg) - 1) >> 1 if flag == 0: if len(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) elif flag == 1: stack[-1][-1] = 2 new_frame = [(arg[mid+1:],’b’),{}, 0] stack.append(new_frame) elif flag == 2: left, right = local[’a’], local[’b’] root = Node(arg[mid]) root.left = left root.right = right stack.pop() stack[-1][-2][aorb] = root return stack[0][-2][’a’]def inorder_recursive(root): stack = [] base_frame = [None, {}, 0] first_frame = [(root, ’a’), {’a’: None, ’c’: None}, 0] stack.append(base_frame) stack.append(first_frame) while len(stack) > 1: cur = stack[-1] arg, local, flag = cur arg, left_right = arg if flag == 0: if not arg: stack.pop() stack[-1][-2][left_right] = [] else: stack[-1][-1] = 1 new_frame = [(arg.left, ’a’), {}, 0] stack.append(new_frame) elif flag == 1: stack[-1][-1] = 2 new_frame = [(arg.right, ’c’), {}, 0] stack.append(new_frame) elif flag == 2: b = [arg.val] ret = local[’a’] + b + local[’c’] stack.pop() stack[-1][-2][left_right] = ret return stack[0][-2][’a’]l = list(range(1, 2 << 2))tree = list2tree(l)c = inorder_recursive(tree)print(c)

以上就是python如何实现递归转非递归的详细内容,更多关于python 递归转非递归的资料请关注好吧啦网其它相关文章!

标签: Python 编程
相关文章: