C++ 迭代和递归有什么区别？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19794739/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the difference between iteration and recursion?
提问by Iordanis
What is the difference between iterationand recursionand why/when is one better:
是什么区别iteration和recursion为什么/时，是一个更好的：
while (true) {
// Iterating
}
And
和
private void recursion() {
if (true)
recursion(); // Recursing
return;
}
I see a lot of recursiveimplementation while it could be easily done in a simple loop.
我看到了很多recursive实现，而它可以在一个简单的循环中轻松完成。
回答by Iordanis
There are two main differences between Recursion and an Iterative Version of the same algorithm.
递归和同一算法的迭代版本之间有两个主要区别。
First of all, some times it is almost better to understand a recursive algorithm than an iterative one (At least if you are experienced programmer) So it does increase expressivity and in some cases readability (It might also lead to the exact opposite in other cases)
首先，有时候理解递归算法比理解迭代算法要好（至少如果你是有经验的程序员）所以它确实增加了表达能力，在某些情况下可读性（在其他情况下也可能导致完全相反的结果） )
Expresivity is a huge deal on programming languages and be able to write the same code in 5 lines instead of 20 is a huge deal.
表达能力对编程语言来说意义重大，并且能够在 5 行而不是 20 行中编写相同的代码是一件很重要的事情。
On the downside, it decreases the performance of your code. Recursive functions have to keep the function records in memory and jump from one memory address to another to be invoked to pass parameters and return values. That makes them very bad performance wise.
不利的一面是，它会降低代码的性能。递归函数必须将函数记录保存在内存中，并从一个内存地址跳转到另一个被调用以传递参数和返回值。这使他们的表现非常糟糕。
Sum Up:
总结：
Iterative Algorithms = Fast Performance but hard to write (sometimes hard to read too)
迭代算法 = 快速性能但难以编写（有时也难以阅读）
Recursive Algorithms = Fast to write but Bad performance wise (Sometimes easier to understand too)
递归算法 = 编写速度快但性能不佳（有时也更容易理解）
Take this example:
拿这个例子：
public static long fib(long n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
vs
对比
if ((n == 1) || (n == 2)) {
return 1;
} else {
long prev = 1, current = 1, next = 0;
for (long i = 3; i <= n; i++) {
next = prev + current;
prev = current;
current = next;
}
return next;
}
Source:
来源：
http://www.csd.uwo.ca/Courses/CS1027a/code/FibonacciDemo.java
http://www.csd.uwo.ca/Courses/CS1027a/code/FibonacciDemo.java
回答by mohit verma
The main difference between recursion and iteration is memory usage.
递归和迭代之间的主要区别是内存使用。
For every recursive call needs space on the stack frame resulting in memory overhead.
对于每个递归调用都需要堆栈帧上的空间，从而导致内存开销。
Let me give you an example. Imagine in one case you forgot to write the base case for your recursive function resulting in endless recursive calls and in other case you wrote an infinite loop.
让我给你举个例子。想象一下，在一种情况下，您忘记为递归函数编写基本情况，导致无休止的递归调用，而在另一种情况下，您编写了一个无限循环。
Since every recursive function assigns new memory space, in first case your code will give a stack overflow exception but in second case it will keep running forever.
由于每个递归函数都分配新的内存空间，在第一种情况下，您的代码将给出堆栈溢出异常，但在第二种情况下，它将永远运行。
So it better to make your iterative code more understandable than using Recursion.
所以最好让你的迭代代码比使用递归更容易理解。
回答by clcto
They are different ways to do the same thing. All recursive implementations can be done with a (or multiple) loop(s) and vise versa. It is more about the logic behind it, a way to think about it. Factorial, although not the best example, is n * (n-1)!so it makes sense to use it recursively.
它们是做同一件事的不同方式。所有递归实现都可以用一个（或多个）循环来完成，反之亦然。它更多的是关于它背后的逻辑，一种思考它的方式。阶乘虽然不是最好的例子，n * (n-1)!但递归使用它是有意义的。
回答by AndreiM
In theory, you can always swap between iteration and recursion. However, at least in case of C/C++/C#/Java, the compiler offers you some support which might make the solution more elegant, especially when you don't know the number of loops before.
理论上，您始终可以在迭代和递归之间切换。但是，至少在 C/C++/C#/Java 的情况下，编译器为您提供了一些支持，这可能会使解决方案更加优雅，尤其是当您之前不知道循环次数时。
The best example is listing all the files inside a folder and it's descendants. If there are several subfolders containg subfolders, normaly in iteration mode you need a stack to save all folders you need to analyze. In case of recursive approach, the stack is already provided by the compiler, and the solution is more elegant.
最好的例子是列出文件夹中的所有文件及其后代。如果有多个子文件夹包含子文件夹，通常在迭代模式下，您需要一个堆栈来保存您需要分析的所有文件夹。在递归方式的情况下，堆栈已经由编译器提供，解决方案更加优雅。
回答by Roman
Recursion and iteration are different ways to think about a solution. It would be dificult to explain in depth the difference in full scope. In your sample code, you aleady showed the difference. Recursive function is the one that calls itself, while iterative is the one that loops through some block of code. Here are some articles to help you understand them better: Recursion wiki
递归和迭代是思考解决方案的不同方式。很难在整个范围内深入解释这种差异。在您的示例代码中，您已经展示了差异。递归函数是调用自身的函数，而迭代函数是循环遍历某个代码块的函数。这里有一些文章可以帮助你更好地理解它们： 递归维基
回答by Montaldo
They can be used interchangeable to solve different problems. In essence you can write recursive functions iteratively and vise versa.
它们可以互换使用以解决不同的问题。本质上，您可以迭代地编写递归函数，反之亦然。
Iteration may increase the performance of your program. Whereas recursion may give a more intuitive and elegant result. You can choose either which to your preference!
迭代可能会提高程序的性能。而递归可能会给出更直观和优雅的结果。您可以根据自己的喜好选择任何一个！
回答by CopyAndPaste
Recursive functions work through the process of calling themselves until a condition is met whereas iteration uses a looping control structure (for example while, do while, for) in order to repeat a section of code until a certain condition is met.
递归函数通过调用自身的过程工作，直到满足条件，而迭代使用循环控制结构（例如，while、do while、for）以重复一段代码，直到满足特定条件。
Recursive example:
递归示例：
int rec_func(int u, int k) {
if (k == 0)
return u;
return rec_func(u * k, k - 1);
}
Iteration example:
迭代示例：
int ite_func(int u, int k) {
while (k != 0) {
u = u * k;
k = k - 1;
}
return u;
}
The only real difference IMO between them is compilation differences.
它们之间唯一真正的 IMO 区别是编译差异。
回答by Yasir
Differences between recursion and iteration
递归和迭代的区别
Recursion
递归
- Recursive function – is a function that is partially defined by itself
- Recursion uses selection structure
- Infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on some condition (base case)
- Recursion terminates when a base case is recognized
- Recursion is usually slower than iteration due to overhead of maintaining stack
- Recursion uses more memory than iteration
- Infinite recursion can crash the system
- Recursion makes code smaller
- 递归函数——是一个部分由它自己定义的函数
- 递归使用选择结构
- 如果递归步骤没有以收敛于某些条件（基本情况）的方式减少问题，则会发生无限递归
- 当识别出基本情况时递归终止
- 由于维护堆栈的开销，递归通常比迭代慢
- 递归比迭代使用更多的内存
- 无限递归会使系统崩溃
- 递归使代码更小
Iteration
迭代
- Iterative Instructions – are loop based repetitions of a process
- Iteration uses repetition structure
- An infinite loop occurs with iteration if the loop condition test never becomes false
- Iteration terminates when the loop condition fails
- Iteration does not use the stack so it's faster than recursion
- Iteration consumes less memory
- Infinite looping uses CPU cycles repeatedly
- Iteration makes code longer
- 迭代指令 – 是基于循环的过程重复
- 迭代使用重复结构
- 如果循环条件测试永远不会变为假，则迭代会发生无限循环
- 当循环条件失败时迭代终止
- 迭代不使用堆栈所以它比递归快
- 迭代消耗更少的内存
- 无限循环反复使用 CPU 周期
- 迭代使代码更长
Data taken from here.
数据取自这里。
