- 主题:请问循环和递归是等价的吗?
尾递归一定等价循环,比如阶乘
普通递归=循环+栈,比如二叉树遍历
【 在 chairmao 的大作中提到: 】
: 如题,循环和递归,是不是等价的呢?
--
FROM 223.104.5.*
不考虑空间时间约束,所有可计算问题都可以用递归,也可以通过维护空间无限的栈转为循环
但现实中时间空间有限,所以问题需要满足你的时间空间约束,都能用递归或者循环。
这个说起来太形而上了。。。
【 在 chairmao 的大作中提到: 】
: 那么,如何判定一个问题,可以用循环或递归来解决呢?
: 这个问题需要具有什么样的特性?
:
--
FROM 120.244.191.*
这个方向我完全不懂,只能乱讲。。。
有条件语句和顺序语句,再加上函数调用,就已经图灵完备了吧。
函数调用和递归相比循环跟自然语言更接近,
循环语句从尾递归自动转化就行
【 在 chairmao 的大作中提到: 】
: 那么具体一点。
: 我现在考虑程序自动生成的问题(或者说,定理自动证明的问题)。
:
: ...................
--
FROM 120.244.191.*