递归或并发循环

Question

我读到了一些开发面试实践，特别是关于面试中问到的技术问题和测试的文章，我对“好吧，你用一个while循环解决了问题，现在你可以用递归来解决问题”，或者“每个人都可以用100行同时循环来解决这个问题，但是他们能用5行递归函数来解决这个问题吗？”等。

我的问题是，递归通常比if/while/for构造好吗？

老实说，我一直认为递归是不可取的，因为它仅限于堆栈内存，它比堆小得多，从性能角度看，执行大量的函数/方法调用也不是最优的，但我可能错了…

Answer 1

递归在本质上并不比循环更好或更糟--每个循环都有优缺点，甚至依赖于编程语言(和实现)。

从技术上讲，迭代循环在硬件级别更适合典型的计算机系统:在机器代码级别，循环只是一个测试和一个条件跳转，而递归(天真地实现)包括推堆栈帧、跳转、返回和从堆栈中弹出。OTOH，可以编写许多递归情况(特别是与迭代循环基本等价的情况)，这样可以避免堆栈推送/ pop；当递归函数调用是返回之前函数体中发生的最后一件事时，这是可能的，通常称为尾调用优化(或尾递归优化)。一个正确的尾调用优化递归函数主要相当于机器代码级别上的迭代循环。

另一个考虑是迭代循环需要破坏性的状态更新，这使得它们与纯(无副作用的)语言语义不兼容。这就是为什么像Haskell这样的纯语言根本没有循环结构的原因，而许多其他函数式编程语言要么完全没有它们，要么尽量避免它们。

然而，这些问题之所以在访谈中出现如此之多，是因为为了回答这些问题，你需要彻底理解许多重要的编程概念--变量、函数调用、范围，当然还有循环和递归-，而且你必须给表带来心理灵活性，使你能够从两个截然不同的角度来处理一个问题，并在同一概念的不同表现形式之间移动。

经验和研究表明，有能力理解变量、指针和递归的人和不理解变量、指针和递归的人之间是有区别的。编程中的几乎所有东西，包括框架、API、编程语言及其边缘案例，都可以通过学习和经验获得，但如果你不能发展对这三个核心概念的直觉，你就不适合做程序员。将一个简单的迭代循环转换为递归版本是筛选非程序员的最快捷的方法--即使是一个缺乏经验的程序员通常也可以在15分钟内完成，这是一个与语言无关的问题，因此候选人可以选择他们选择的语言，而不是在特性上蹒跚而行。

如果你在面试中遇到这样的问题，那是个好兆头:这意味着未来的雇主正在寻找那些会编程的人，而不是那些已经记住了编程工具手册的人。

Answer 2

那得看情况。

• 有些问题很容易被递归解决，例如快速排序
• 有些语言实际上不支持递归，例如早期FORTRAN
• 有些语言假定递归是循环的主要方法，例如哈斯克尔

还值得注意的是，对尾递归的支持使尾递归和迭代循环等效，也就是说，递归并不总是浪费堆栈。

此外，递归算法始终可以迭代地实现通过使用显式堆栈。

最后，我要指出的是，五行解决方案可能总是比100行解决方案好(假设它们实际上是等价的)。

Answer 3

在编程方面，对于“更好”的定义还没有达成一致，但我将其理解为“易于维护/读取”。

递归比迭代循环构造具有更强的表现力:我说这是因为while循环等价于尾递归函数，递归函数不必是尾递归函数。强大的构造通常是不好的，因为它们允许您做一些难以阅读的事情。然而，递归使您能够在不使用可变的情况下编写循环，在我看来，可更改性要比递归强大得多。

因此，从低表达能力到高表达能力，循环构造就像这样堆叠在一起：

• 使用不可变数据的尾递归函数，
• 使用不可变数据的递归函数，
• 当循环使用可变数据时，
• 使用可变数据的尾递归函数，
• 使用可变数据的递归函数，

理想情况下，您应该使用最不具表现力的结构。当然，如果您的语言不支持尾调用优化，那么这也会影响您对循环结构的选择。