递归与非递归 [英] Recursive vs non-recursive

问题描述

可能的重复:
递归和迭代

递归函数和非递归函数有什么区别?确切地说是斐波那契.

What is the difference between a recursive and a non-recursive function? Fibonacci to be exact.

我在寻找与时间和记忆相关的答案.

I looking for answers that relate towards the time and memory.

推荐答案

递归"仅仅意味着函数调用自身.这可能是有意的，也可能不是(无意的递归会导致许多崩溃).

"Recursive" simply means that a function calls itself. This may or may not be intentional (unintentional recursion is responsible for lots of crashes).

有意递归，即一个函数执行部分操作，然后调用自己执行剩余部分，通常是一种有用的编程范式，但需要一定程度的理解/经验/技能来了解它".

Intentional recursion, where a function performs part of an operation, then calls itself to perform the remaining part, is often a useful programming paradigm, but requires some degree of comprehension/experience/skill to "get your head around it".

基本上，递归可用于替换迭代"(循环)并替换伴随的数组分配(使用函数体的局部变量).但并非每个迭代或使用数组的函数都可以有效地转换为其等效的递归函数.

Basically, recursion can be used to replace "iteration" (loops) and to replace accompanying array allocations (with variables local to the function body). But not every iterative or array-using function can be effectively converted to its recursive equivalent.

如果这个问题适合递归，人们通常可以编写一个递归版本，它的执行效率与非递归版本大致相当……可能会更好或更糟，具体取决于效率如何调用机制与语言/编译器中的循环和数组索引进行比较.在存储方面，递归很少有效率更高，但它受益于不必为手头的特定问题预先分配(并预先知道分配的大小).

If the problem is suitable for recursion, one can often write a recursive version that is about equivalent in execution efficiency to the non-recursive version ... maybe slightly better or worse depending on how efficient the call mechanism is compared to looping and array indexing in the language/compiler. In terms of storage, recursion is rarely more efficient, but it benefits from not having to pre-allocate (and pre-know the size of the allocation) for the particular problem at hand.

大多数情况下递归更好(实际上是)，因为它使实现更简单且不易出错，并且错误是迄今为止最大的计算成本.(当然，如果操作不当也会花费大量时间.)

Mostly recursion is better (when it actually is) because it makes an implementation much simpler and less error-prone, and errors are by far the biggest cost in computing. (But of course improperly done it can cost you big time as well.)

当递归很好时，它非常好.当递归不好时，它非常糟糕.

When recursion is good it's very good. When recursion is bad it's very bad.

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