递归与迭代 [英] 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 最终要做的事情.递归本身，更直接，意味着将函数调用和作用域放在一个堆栈中.但是，将递归算法更改为循环算法可能需要大量工作，并且会使代码的可维护性降低:至于每次优化，只有在某些分析或证据表明有必要时才应尝试.

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屋！