递归或while循环

#1 楼

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

从技术上讲，迭代循环在硬件级别上更适合典型的计算机系统：在机器代码级别，循环只是测试和有条件的跳转，而递归（天真地实现）涉及推入堆栈帧，跳转，返回以及从堆栈弹出。 OTOH，可以编写许多递归情况（尤其是那些等同于迭代循环的情况），从而可以避免堆栈推入/弹出操作；当递归函数调用是返回之前在函数主体中发生的最后一件事情时，这是可能的，并且通常称为尾部调用优化（或尾部递归优化）。正确的尾部调用优化的递归函数通常等效于机器代码级别的迭代循环。

另一个要考虑的是，迭代循环需要破坏性的状态更新，这使得它们与纯（side-自由效果）的语言语义。这就是为什么像Haskell这样的纯语言根本没有循环构造的原因，而许多其他函数式编程语言要么完全缺少循环构造，要么尽可能避免使用它们。

出现这些问题的原因但是，在面试中之所以如此，是因为要回答这些问题，您需要对许多重要的编程概念（变量，函数调用，作用域，当然还有循环和递归）有透彻的了解，并且必须带给他们灵活性该表使您可以从两个根本不同的角度来解决问题，并在同一概念的不同表现形式之间移动。

经验和研究表明，有能力理解变量，指针和递归的人与没有理解变量，指针和递归的人之间存在着界限。可以通过学习和经验来获取编程中几乎所有其他内容，包括框架，API，编程语言及其优势，但是如果您无法对这三个核心概念有直觉，则不适合成为程序员。将简单的迭代循环转换为递归版本是滤除非程序员的最快方法-即使是经验不足的程序员通常也可以在15分钟内完成，这是一个与语言无关的问题，因此应聘者可以选择

如果在面试中遇到这样的问题，那是一个好兆头：这意味着准雇主正在寻找可以编程的人，而不是人记住了编程工具手册的人。

#2 楼

这取决于。


某些问题非常适合递归解决方案，例如quicksort

某些语言并不真正支持递归，例如早期的FORTRANs

某些语言将递归作为循环的主要手段，例如Haskell


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

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

最后，我要指出的是，五行解决方案总是比一百行解决方案更好（假设它们实际上是等效的）。

#3 楼

在编程方面，“更好”的定义尚未达成共识，但我将其表示为“更易于维护/读取”。

递归比迭代循环结构具有更多的表达能力：我说这是因为while循环等效于尾部递归函数，而递归函数不必是尾部递归。强大的构造通常是一件坏事，因为它们使您能够执行难以阅读的事情。但是，递归使您无需使用可变性就可以编写循环，而我认为可变性比递归要强大得多。

因此，从低表达能力到高表达能力，循环构造像这样堆积：


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

理想情况下，您将使用可以表达最少的构造。当然，如果您的语言不支持尾部调用优化，那么这也可能会影响您对循环结构的选择。

#4 楼

递归通常不太明显。不那么明显很难维护。

如果在主流中编写for(i=0;i<ITER_LIMIT;i++){somefunction(i);}，则可以很清楚地看到正在编写一个循环。如果您编写somefunction(ITER_LIMIT);，您并不会很清楚会发生什么。只看到内容：somefunction(int x)调用somefunction(x-1)告诉您，实际上这是一个使用迭代的循环。另外，您不能轻易将break;的转义条件放在迭代的一半位置，您必须添加将一直传递的条件，或者引发异常。 （并且异常还会增加复杂性...）

本质上，如果在迭代和递归之间是显而易见的选择，请执行直观的操作。如果迭代能够轻松完成工作，那么从长远来看，保存2行几乎不值得头痛。

当然，如果要节省98行，那完全是另一回事了。

在某些情况下，递归完全适合，而且并非罕见。遍历树结构，多重链接的网络，可以包含其自身类型的结构，多维锯齿形数组，从本质上讲，它既不是简单的向量也不是固定维数的数组。如果遍历已知的直线路径，则进行迭代。如果您陷入未知，请递归。

本质上，如果每个级别从自身内部多次调用somefunction(x-1)，则无需进行迭代。

...编写迭代函数对于最好通过递归完成的任务是可能的，但并不令人满意。无论在哪里使用int，都需要stack<int>之类的东西。我做了一次，更多的是作为练习，而不是出于实际目的。我可以向您保证，一旦您遇到这样的任务，您将不会像您所表达的那样产生疑问。

#5 楼

通常，这通常是无法回答的，因为存在其他因素，这些因素在实践中在案例之间广泛不平等，在用例中彼此不平等。以下是其中的一些压力。



简短，优雅的代码通常优于长而复杂的代码。
但是，如果您的开发人员基础是不熟悉递归并且不愿意/无法学习。
如果在实践中需要深度嵌套的调用并且您不能使用尾部递归（或者您的环境无法优化尾部递归），则递归对于效率可能是不利的。 ）。
如果您不能正确地缓存中间结果，则递归在很多情况下也是不好的。例如，如果不缓存，使用树递归计算斐波纳契数的常见示例的性能将非常糟糕。如果您进行缓存，那么它简单，快速，优雅且完全很棒。
递归不适用于某些情况，就像在其他情况下一样好，而在其他情况下则绝对必要。通过漫长的业务规则链进行操作通常根本无法通过递归来实现。通过递归可以有效地遍历数据流。如果不进行递归，显式或隐式的迭代，遍历多维动态数据结构（例如，迷宫，对象树...）几乎是不可能的。请注意，在这些情况下，显式递归比隐式要好得多-没有什么比读取代码更痛苦的了，因为有人在语言中实现了自己的即席，不完整，错误的堆栈，只是为了避免可怕的R字。

#6 楼

递归是关于重复调用函数，循环是关于重复跳转到内存中。

还应该提到堆栈溢出-http://en.wikipedia.org/wiki/Stack_overflow

#7 楼

它实际上取决于便利性或要求：

如果您使用Python编程语言，则它支持递归，但是默认情况下，递归深度是有限制的（1000）。如果超过限制，我们将收到错误或异常消息。可以更改该限制，但是如果这样做，我们可能会遇到该语言的异常情况。

此时（调用次数大于递归深度），我们需要使用循环构造。我的意思是，如果堆栈大小不够，我们必须更喜欢循环结构。

#8 楼

使用策略设计模式。


递归是干净的
循环（可以说）高效

取决于您的负载（和/或其他条件） ，选择一个。