- 主题:请问循环和递归是等价的吗？
如题，循环和递归，是不是等价的呢？
--
FROM 112.224.151.*
尾递归一定等价循环，比如阶乘
普通递归=循环+栈，比如二叉树遍历
【 在 chairmao 的大作中提到: 】
: 如题，循环和递归，是不是等价的呢？
--
FROM 223.104.5.*
那么，如何判定一个问题，可以用循环或递归来解决呢？
这个问题需要具有什么样的特性？
【 在 MegaStone 的大作中提到: 】
: 尾递归一定等价循环，比如阶乘
: 普通递归=循环+栈，比如二叉树遍历
:
--
FROM 112.224.149.*
不考虑空间时间约束，所有可计算问题都可以用递归，也可以通过维护空间无限的栈转为循环
但现实中时间空间有限，所以问题需要满足你的时间空间约束，都能用递归或者循环。
这个说起来太形而上了。。。
【 在 chairmao 的大作中提到: 】
: 那么，如何判定一个问题，可以用循环或递归来解决呢？
: 这个问题需要具有什么样的特性？
:
--
FROM 120.244.191.*
那么具体一点。
我现在考虑程序自动生成的问题（或者说，定理自动证明的问题）。
顺序语句和条件语句，都可以用搜索的办法，来生成。
那么，我如何判断，需要生成一段循环程序，来解决某个问题呢？
【 在 MegaStone 的大作中提到: 】
: 不考虑空间时间约束，所有可计算问题都可以用递归，也可以通过维护空间无限的栈转为循环
: 但现实中时间空间有限，所以问题需要满足你的时间空间约束，都能用递归或者循环。
: 这个说起来太形而上了。。。
: ...................
--
FROM 112.224.152.*
这个方向我完全不懂，只能乱讲。。。
有条件语句和顺序语句，再加上函数调用，就已经图灵完备了吧。
函数调用和递归相比循环跟自然语言更接近，
循环语句从尾递归自动转化就行
【 在 chairmao 的大作中提到: 】
: 那么具体一点。
: 我现在考虑程序自动生成的问题（或者说，定理自动证明的问题）。
:
: ...................
--
FROM 120.244.191.*
准确的说不等价，循环堆栈不扩充，减少缓存缺失，小范围多循环的时候x86 LSD会帮助我们避免跳转预测带来的冗余cycle和超线程之间的预测干扰，另外对于call/ret的预测率与普通循环相比略逊，我们的代码完全避免使用递归。
【 在 chairmao 的大作中提到: 】
: 如题，循环和递归，是不是等价的呢？
--
FROM 42.120.75.*
你这是从计算的实现方式来说的，都下降到硬件层面了。
我想问的是，从计算能力上，二者是否等价。
也就是，是否所有循环能处理的问题，递归也能处理；
是否所有递归能处理的问题，循环也能处理？
【 在 MaLing 的大作中提到: 】
: 准确的说不等价，循环堆栈不扩充，减少缓存缺失，小范围多循环的时候x86 LSD会帮助我们避免跳转预测带来的冗余cycle和超线程之间的预测干扰，另外对于call/ret的预测率与普通循环相比略逊，我们的代码完全避免使用递归。
--
FROM 106.119.2.*
那你发错版了吧
【 在 chairmao 的大作中提到: 】
: 你这是从计算的实现方式来说的，都下降到硬件层面了。
:
: 我想问的是，从计算能力上，二者是否等价。
: ....................
- 来自「最水木 for iPhone 11」
--
FROM 112.65.61.*