递归迭代对比 [英] recursion versus iteration

问题描述

它是正确的说，到处递归用一个for循环，可以用吗？如果递归通常慢是什么技术原因，直到永远使用它在for循环迭代？

Is it correct to say that everywhere recursion is used a for loop could be used? And if recursion is usually slower what is the technical reason for ever using it over for loop iteration?

如果它总是可以的递归转换成一个for循环是有拇指方式的规则办呢？

And if it is always possible to convert an recursion into a for loop is there a rule of thumb way to do it?

推荐答案

递归通常要慢得多，因为所有函数调用必须存储在堆栈，以允许返回给调用者的功能。在许多情况下，存储器必须分配和复制到实施范围隔离

Recursion is usually much slower because all function calls must be stored in a stack to allow the return back to the caller functions. In many cases, memory has to be allocated and copied to implement scope isolation.

某些优化，例如尾巴调用优化时，使递归更快，但并不总是可能的，并且不执行在所有的语言。

Some optimizations, like tail call optimization, make recursions faster but aren't always possible, and aren't implemented in all languages.

使用递归的主要原因是

• ，它是在许多情况下，更直观的，当它模仿我们的问题
的办法
• 在一些数据结构，如树木更容易使用递归探索（或需要堆叠在任何情况下）

当然，每一个递归的可以的建模作为一种循环：这就是CPU将会最终做。和递归本身，更直接地，意味着把在堆叠的函数调用和范围。但是，改变你的递归算法，以一个循环人们可能需要大量的工作，使你的code少维护：为每一个优化的，它应该只当一些分析或证据表明，它是必要的尝试

Of course every recursion can be modeled as a kind of loop : that's what the CPU will ultimately do. And the recursion itself, more directly, means putting the function calls and scopes in a stack. But changing your recursive algorithm to a looping one might need a lot of work and make your code less maintainable : as for every optimization, it should only be attempted when some profiling or evidence showed it to be necessary.

这篇关于递归迭代对比的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！