把它写成递归，或者作为练习，可能会很有趣。

但是，如果要在生产中使用该代码，则需要考虑堆栈溢出的可能性。

尾递归优化可以消除堆栈溢出，但是您是否想要经历这样的麻烦，并且您需要知道您可以指望它在您的环境中进行优化。

每次算法递归，数据大小或n减少了多少?

If you are reducing the size of data or n by half every time you recurse, then in general you don't need to worry about stack overflow. Say, if it needs to be 4,000 level deep or 10,000 level deep for the program to stack overflow, then your data size need to be roughly 24000 for your program to stack overflow. To put that into perspective, a biggest storage device recently can hold 261 bytes, and if you have 261 of such devices, you are only dealing with 2122 data size. If you are looking at all the atoms in the universe, it is estimated that it may be less than 284. If you need to deal with all the data in the universe and their states for every millisecond since the birth of the universe estimated to be 14 billion years ago, it may only be 2153. So if your program can handle 24000 units of data or n, you can handle all data in the universe and the program will not stack overflow. If you don't need to deal with numbers that are as big as 24000 (a 4000-bit integer), then in general you don't need to worry about stack overflow.

但是，如果每次递归时都将数据或n的大小减小一个常数，那么当n仅变为20000时，就会遇到堆栈溢出。也就是说，当n为1000时，程序运行良好，你认为程序很好，然后在未来的某个时候，当n为5000或20000时，程序堆栈溢出。

所以如果你有堆栈溢出的可能，试着让它成为一个迭代的解决方案。

递归比迭代的任何可能定义都更简单(因此也更基本)。你可以只用一对组合子定义一个图灵完备系统(是的，在这样的系统中，甚至递归本身也是一个衍生概念)。Lambda演算是一个同样强大的基本系统，具有递归函数。但是如果你想正确地定义一个迭代，你需要更多的原语来开始。

至于代码——不，递归代码实际上比纯迭代代码更容易理解和维护，因为大多数数据结构都是递归的。当然，为了正确使用它，至少需要一种支持高阶函数和闭包的语言，以简洁的方式获得所有标准的组合子和迭代器。当然，在c++中，复杂的递归解决方案可能看起来有点丑，除非你是fc++的铁杆用户。

我认为在(非尾)递归中，每当函数被调用时，分配一个新的堆栈等都会受到性能影响(当然取决于语言)。

递归有一个缺点，使用递归编写的算法的空间复杂度为O(n)。 而迭代方法的空间复杂度为O(1)。这是使用迭代而不是递归的优点。 那我们为什么要用递归呢?

见下文。

有时使用递归编写算法更容易，而使用迭代编写相同的算法略难。在这种情况下，如果您选择遵循迭代方法，您将不得不自己处理堆栈。

递归可能会更昂贵，这取决于递归函数是否是尾部递归(最后一行是递归调用)。尾递归应该被编译器识别，并优化为迭代的对应部分(同时保持代码中简洁、清晰的实现)。

我将以最有意义的方式编写算法，并且对那些不得不在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)来说是最清楚的。如果你遇到了性能问题，那就分析你的代码，然后，只有在那之后，你才能通过迭代实现来进行优化。您可能需要研究一下内存和动态编程。

把它写成递归，或者作为练习，可能会很有趣。

但是，如果要在生产中使用该代码，则需要考虑堆栈溢出的可能性。

尾递归优化可以消除堆栈溢出，但是您是否想要经历这样的麻烦，并且您需要知道您可以指望它在您的环境中进行优化。

每次算法递归，数据大小或n减少了多少?

If you are reducing the size of data or n by half every time you recurse, then in general you don't need to worry about stack overflow. Say, if it needs to be 4,000 level deep or 10,000 level deep for the program to stack overflow, then your data size need to be roughly 24000 for your program to stack overflow. To put that into perspective, a biggest storage device recently can hold 261 bytes, and if you have 261 of such devices, you are only dealing with 2122 data size. If you are looking at all the atoms in the universe, it is estimated that it may be less than 284. If you need to deal with all the data in the universe and their states for every millisecond since the birth of the universe estimated to be 14 billion years ago, it may only be 2153. So if your program can handle 24000 units of data or n, you can handle all data in the universe and the program will not stack overflow. If you don't need to deal with numbers that are as big as 24000 (a 4000-bit integer), then in general you don't need to worry about stack overflow.

但是，如果每次递归时都将数据或n的大小减小一个常数，那么当n仅变为20000时，就会遇到堆栈溢出。也就是说，当n为1000时，程序运行良好，你认为程序很好，然后在未来的某个时候，当n为5000或20000时，程序堆栈溢出。

所以如果你有堆栈溢出的可能，试着让它成为一个迭代的解决方案。