递归与循环

Question

我遇到了一个问题，递归和循环都似乎是自然的解决方案。在这种情况下，是否有约定俗成或“首选方法”？（显然下面的示例并不完全简单）

递归

Item Search(string desired, Scope scope) {
    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    return scope.Parent ? Search(desired, scope.Parent) : null;
}

循环

Item Search(string desired, Scope scope) {
    for(Scope cur = scope; cur != null; cur = cur.Parent)
        foreach(Item item in cur.items)
            if(item.name == desired)
                return item;

    return null;
}

- zildjohn01

---

递归解决方案似乎不正确。“scope.Parent”没有产生布尔表达式，并且根据您的迭代解决方案，看起来您想表达的是“scope.Parent != null”。是这样吗？ - John Feminella

没错。我试图保持简洁，使用隐式转换为布尔值。 - zildjohn01

可能是递归还是迭代？的重复问题。 - nawfal

正如至少一个答案所指出的，递归和迭代在理论上是相互可转换的。语言和编译器在各种构造的语义和性能特征上有所不同。此外，语言社区在其风格偏好上也存在差异。如上所述，这个问题充其量仅基于个人观点而定。 - Christian Conkle

这里有一个很好的比较：https://www.geeksforgeeks.org/difference-between-recursion-and-iteration/ - Asif

Answer 1

当我面对以下情况时，我更倾向于使用递归解决方案：

• 递归的实现比迭代解决方案要简单得多，通常是因为它以迭代方法无法利用的问题结构方面作为突破口。

• 我可以合理地保证递归的深度不会导致堆栈溢出，假设我们正在使用实现递归的语言。

这里似乎不符合第1个条件。迭代解决方案与递归解决方案的复杂度相差不大，因此我会坚持使用迭代方法。

- John Feminella

---

也许可以在堆栈深度是一个问题的情况下添加有关尾递归的附加说明（我知道它不适用于Java）？ - Amir Afghani

我要说，在递归函数中忘记添加终止条件实际上更容易导致无限循环，因此这比起迭代方法（尤其是for循环）来说要容易一些。对于迭代方法，终止条件实际上是必须的。唯一可能导致迭代for进入无限循环的情况是在该循环中进行递减操作时应该进行递增操作或者为该情况提供了错误的比较运算符。 - c0dezer019

Answer 2

如果性能很重要，就对两者进行基准测试，并基于理性选择。如果不重要，则基于复杂度选择，关注可能的堆栈溢出问题。

有一条指导方针来自经典书籍《程序设计风格》（作者Kernighan和Plauger），即算法应该遵循数据结构。也就是说，递归结构通常使用递归算法处理更清晰。

- RBerteig

Answer 3

递归用于表达一种自然递归算法的形式，这种算法通过解决更小的子问题来构建答案，而这些子问题又是由答案更小的子问题构成的，以此类推。例如，计算阶乘。

在非函数式编程语言中，迭代方法几乎总是比递归方法更快、更有效，因此使用递归的原因是为了清晰易懂，而不是为了速度。如果递归实现的可读性比迭代实现还要差，那么请尽量避免使用它。

在这种特殊情况下，我认为迭代实现更清晰明了。

- Tyler McHenry

---

在一个循环中，每个迭代都是一个“刷新”的作用域，上一个迭代中的所有变量都被删除了（迭代i-1的变量无法从迭代i中访问，因为在从迭代i-1过渡到迭代i时，来自i-1的变量已被删除）。在递归函数中，每次新迭代都在上一次迭代的子作用域中运行（迭代i-1的变量在迭代1期间仍然存在，只是它们存在于不同的作用域中）。这描述了过程式语言，但有些函数式语言实际上进行优化，使递归更加高效。 - charmoniumQ

Answer 4

我看了很多答案，甚至接受了答案，但是从未看到正确的答案，一直在想为什么...

长话短说：

如果可以使用循环来生成相同的单元，请始终避免递归！

递归是如何工作的？

• 用于单个函数调用的堆栈内存中分配了帧。

• 帧包含对实际方法的引用。

• 如果方法具有对象，则将对象放入堆内存中，并且帧将包含对堆内存中该对象的引用。

• 对于每个单独的方法调用执行这些步骤！

风险：

• 当堆栈没有内存可放置新递归方法时，将发生堆栈溢出。

• 当堆没有内存可放置递归存储的对象时，将发生OutOfMemory。

循环是如何工作的？

• 所有先前的步骤都相同，除了循环内重复代码的执行不会消耗任何进一步的数据（如果已经被消耗）。

风险：

• 在 while 循环中，当您的条件永远不存在时存在单个风险...

好吧，如果您天真地执行while(true)，那就不会导致任何崩溃或其他问题，它只是不会退出循环 :)

测试：

在您的软件中执行以下操作：

private Integer someFunction(){

return someFunction();
}

你将在一秒钟内遇到StackOverFlow异常，可能还会遇到OutOfMemory异常

执行第二步：

while(true){

}

软件将会冻结，但不会崩溃：

最后 - for 循环 :

总是使用 for 循环，因为这种循环方式会迫使你给出循环的终止点，当然你可能会非常愤怒，想方设法让 for 循环永远不停止，但我建议你始终使用循环而不是递归，以便更好地管理内存和提高软件的生产力，这是目前的一个巨大问题。

参考资料:

基于堆栈的内存分配

- Android Developer

Answer 5

如果你正在使用一种函数式语言（看起来并不是这样），那么请使用递归。如果不是，请使用循环，因为其他人更容易理解它在项目中的作用。当然，有些任务（比如递归搜索一个目录）更适合使用递归而不是循环。

此外，如果代码无法进行尾递归优化，循环更加安全。

- Ed Swangren

Answer 6

使用循环。这样更容易阅读和理解 (阅读代码总比编写代码难得多)，而且通常会更快。

- Emil H

---

某些问题不容易通过迭代解决。https://dev59.com/bXRB5IYBdhLWcg3wUVxd#55509199 - Danyal Sandeelo

Answer 7

可以证明所有尾递归算法都可以展开成循环，反之亦然。一般来说，对于程序员来说，递归算法的递归实现比循环实现更易于理解，也更容易调试。而且一般情况下，循环实现的实际性能会更快，因为循环中的分支/跳转通常比推送和弹出堆栈帧更快。

就我个人而言，在除了最需要性能的情况下，我更喜欢使用递归实现尾递归算法。

- Not Sure

Answer 8

我更喜欢使用循环，因为：

• 递归容易出错
• 所有代码都保留在一个函数/方法中
• 节约内存和速度

我使用栈（后进先出的结构）使循环工作。

在Java中，可以使用Deque接口来实现栈。

// Get all the writable folders under one folder
// java-like pseudocode
void searchWritableDirs(Folder rootFolder){
    List<Folder> response = new List<Folder>(); // Results
    Deque<Folder> folderDeque = new Deque<Folder>(); // Stack with elements to inspect
    folderDeque.add(rootFolder);
    while( ! folderDeque.isEmpty()){
        Folder actual = folder.pop(); // Get last element
        if (actual.isWritable()) response.add(actual); // Add to response
        for(Folder actualSubfolder: actual.getSubFolder()) { 
            // Here we iterate subfolders, with this recursion is not needed
            folderDeque.push(actualSubfolder);
        } 
    } 
    log("Folders " + response.size());
 }

比起其他技术，这项技术更简单、更紧凑。

// Get all the writable folders under one folder
// java-like pseudocode
void searchWritableDirs(Folder rootFolder){
    List<Folder> response = new List<Folder>(); // Results
    rec_searchWritableDirs(actualSubFolder,response);
    log("Folders " + response.size());
}

private void rec_searchWritableDirs(Folder actual,List<Folder> response) {
   if (actual.isWritable()) response.add(actual); // Add to response
   for(Folder actualSubfolder: actual.getSubFolder()) {
       // Here we iterate subfolders, recursion is needed
       rec_searchWritableDirs(actualSubFolder,response);
   }                
}

后者代码量较少，但有两个函数并且阅读难度更大，在我看来。

- user898384

---

这里似乎存在一个问题，因为你正在for循环中修改集合actualSubFolder。 - Surya Pratap

某些问题无法通过迭代解决。https://dev59.com/bXRB5IYBdhLWcg3wUVxd#55509199 - Danyal Sandeelo

Answer 9

我认为递归版本更易理解，但需要加上注释：

Item Search(string desired, Scope scope) {
    // search local items
    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    // also search parent
    return scope.Parent ? Search(desired, scope.Parent) : null;
}

这个版本要容易理解得多。尝试在循环版本上写一个好的评论，你就会明白。

- ypnos

---

如果您需要针对该版本进行评论，但不需要针对循环进行评论，那么我认为这表明在这种情况下应该优先选择循环。 - Ed S.

不，我个人认为循环需要更多的注释。如果考虑到注释，可读性比较就更容易了。对于普通懒惰程序员来说，两个版本都不够“自解释”。 - ypnos

如果递归更易读的原因是注释，那么我们就错过了递归的整个美感和简洁性... - Avi Shukron

Answer 10

我认为递归更加自然，但如果你的编译器没有进行尾调用优化并且你的树/列表太深而超出了堆栈大小，可能会被迫使用循环。

- Svante