最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
python如何实现递归转非递归 python实现递归转非递归代码
时间:2021-02-25 编辑:袖梨 来源:一聚教程网
python如何实现递归转非递归?本篇文章小编给大家分享一下python实现递归转非递归代码,文章代码介绍的很详细,小编觉得挺不错的,现在分享给大家供大家参考,有需要的小伙伴们可以来看看。
思路是:当发生递归调用时,模拟函数调用的 压栈 。并处理 入参 和 返回值 和 记录返回到当前栈的时候该继续从哪里执行
以如下递归( 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:
另外:有一些函数编程语言,能将所有的递归调用转化成尾调用(非尾递归),这样就不会发生爆栈的问题,但是目前流行的大多数语言都是没有这个功能的
相关文章
- Golang ProtoBuf的基本语法详解 10-20
- Python识别MySQL中的冗余索引解析 10-20
- Python+Pygame绘制小球代码展示 10-18
- Python中的数据精度问题介绍 10-18
- Python随机值生成的常用方法介绍 10-18
- python3解压缩.gz文件分析 09-27