作者:摩羯法国反弹 | 来源:互联网 | 2017-05-14 02:43
php中文网(www.php.cn)提供了最全的编程技术基础教程,介绍了HTML、CSS、Javascript、Python,Java,Ruby,C,PHP,MySQL等各种编程语言的基础知识。同时本站中也提供了大量的在线实例,通过实例,您可以更好的学习编程。..
回复内容:
所有的递归调用,都可以做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) {
Function<Integer, Integer> k = (x) -> x;
while(true) {
if (n == 0)
return k.apply(1);
else {
final Function<Integer, Integer> k0 = k;
final int n0 = n;
k = (x) -> k0.apply(n0 * x);
n -= 1;
}
}
}
}
用循环实现?
可以自己建个栈来保存状态。你只需要搞明白在递归的时候程序往栈上面放了些什么,然后用自己的栈模拟即可。
技巧上倒是可以参照从fortran时代积累的递归转迭代的技术。
不是完全没有解决方案:
Does Python optimize tail recursion?
时代积累的递归转迭代的技术。
然后用自己的栈模拟即可。
,话j