Python 哪些可以代替递归的算法?
程序员文章站
2022-05-24 14:25:44
...
回复内容:
所有的递归调用,都可以做CPS变换改写成尾递归形式,然后尾递归可以改写成循环:def fact(n):
if n == 0:
return 1
else:
return n * fact(n - 1)
id = lambda x: x
def factCPS(n):
def f(n, k):
if n == 0:
return k(1)
else:
return f(n - 1, lambda x: k(n * x))
return f(n, id)
def factNoRec(n):
def factory(n, k):
return lambda x: k(n * x)
k = id
while True:
if n == 0:
return k(1)
else:
k = factory(n, k)
n -= 1
def factHolyCrap(n):
k = ()
while True:
if n == 0:
x = 1
while k:
x = k[0] * x
k = k[1]
return id(x)
else:
k = (n, k)
n -= 1
if __name__ == '__main__':
print([f(5) for f in [fact, factCPS, factNoRec, factHolyCrap]])
递归过程中需要维护一个调用栈如果不想递归,硬是要循环,那么可以自己手动来维护这个调用栈
这样唯一的好处或许就是解除了最大递归深度的限制吧。。。 给邵大神补一个java sample
public class RecursionEliminationSample {
int factorRec(int n) {
if (n == 0)
return 1;
else
return n * factorRec(n-1);
}
int factor(int n) {
FunctionInteger, Integer> k = (x) -> x;
while(true) {
if (n == 0)
return k.apply(1);
else {
final FunctionInteger, Integer> k0 = k;
final int n0 = n;
k = (x) -> k0.apply(n0 * x);
n -= 1;
}
}
}
}
用循环实现?
可以自己建个栈来保存状态。你只需要搞明白在递归的时候程序往栈上面放了些什么,然后用自己的栈模拟即可。技巧上倒是可以参照从fortran时代积累的递归转迭代的技术。 不是完全没有解决方案:
Does Python optimize tail recursion? 时代积累的递归转迭代的技术。 然后用自己的栈模拟即可。 ,话j
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。
相关文章
相关视频
专题推荐
-
独孤九贱-php全栈开发教程
全栈 170W+
主讲:Peter-Zhu 轻松幽默、简短易学,非常适合PHP学习入门
-
玉女心经-web前端开发教程
入门 80W+
主讲:灭绝师太 由浅入深、明快简洁,非常适合前端学习入门
-
天龙八部-实战开发教程
实战 120W+
主讲:西门大官人 思路清晰、严谨规范,适合有一定web编程基础学习
网友评论
文明上网理性发言,请遵守 新闻评论服务协议
我要评论