递归函数的例子

Question

有人可以提供关于递归函数的编程示例吗？除了像斐波那契数列和汉诺塔这样的常见示例之外，还有什么有趣的内容呢？

- Codeslayer

---

请查看我对这个问题的评论：https://dev59.com/ZXVC5IYBdhLWcg3w-mZO - DutGRIFF

Answer 1

这幅插图是英文的，并非实际的编程语言，但对于以非技术方式解释过程很有用：

一个孩子无法入睡，于是她的母亲讲了一个关于一只小青蛙的故事，
  小青蛙也无法入睡，于是青蛙的母亲讲了一个关于一只小熊的故事，
    小熊也无法入睡，于是熊的母亲讲了一个关于一只小黄鼠狼的故事，
      ……然后小黄鼠狼就睡着了。
    ……然后小熊也睡着了；
  ……然后小青蛙也睡着了；
……于是孩子也睡着了。

- PConroy

---

是啊，但结束条件/基本情况在哪里呢？;-) - Joachim Sauer

@Joachim Weasel永远是基础情况，伙计。你知道的！ - Andres Jaan Tack

好的，这很美。 - Andres Jaan Tack

你很少看到缩进的英语。 :-) - svick

这个回答让我想起了电影《盗梦空间》。 - user731914

乌龟。一直都是乌龟。 - Aaron McDaid

Answer 2

为了理解 递归, 首先必须理解递归。

- Ilya Ryzhenkov

Answer 3

"The rule of thumb for recursion is, '仅当在每次迭代中，您的任务分成两个或更多类似的任务时，才使用递归'。因此，斐波那契数列不是递归应用的好例子，而汉诺塔则是一个好例子。所以，大多数递归的好例子都是树遍历的不同形式。例如：图的遍历——要求访问过的节点永远不会再次访问，有效地使图成为一棵树（树是没有简单环路的连通图）；分治算法（快速排序、合并排序）——“分”后的部分构成子节点，“征服”构成从父节点到子节点的边。"

- Kaerber

---

+1 对于第一句话。我将尽力完成您的翻译要求。 - lukas.pukenis

+1 for the first sentence - Jack_of_All_Trades

我不理解第一句话，但后面的部分加一分。 - ctrl-alt-delor

阐述第一句话为什么如此关键。想象相反的情况。如果任务不能分成多个路径，那么你只能使用迭代。谷歌斐波那契数列的迭代和递归版本。迭代版本更快、更节省内存，并且不会溢出堆栈。因此，只有当你需要/获益足够大以超越使用递归的额外缺点时，才会使用递归。 - Katastic Voyage

Answer 4

如何测试一个字符串是否为回文？

bool isPalindrome(char* s, int len)
{
  if(len < 2)
    return TRUE;
  else
    return s[0] == s[len-1] && isPalindrome(&s[1], len-2);
}

当然，你可以使用循环更有效地完成这个任务。

- Kip

---

为什么要提供一个错误的递归示例，并因此批评别人？ - Kaerber

@Kaerber 我并没有批评任何人。我在Yuval的回答（以及我的回答）中指出，这些示例最好使用循环完成。 - Kip

@Kip @Kaerber，如果我们使用编译时评估的话也不一定是坏事…… ;-)constexpr bool compileTimeIsPalindrome(const char* s, int len) { return len < 2 ? true : s[0] == s[len-1] && compileTimeIsPalindrome(&s[1], len-2); } - learnvst

Answer 5

编写一个递归下降解析器！

- Martin Cote

Answer 6

来自数学领域的，有阿克曼函数：

Ackermann(m, n)
{
  if(m==0)
    return n+1;
  else if(m>0 && n==0)
    return Ackermann(m-1, 1);
  else if(m>0 && n>0)
    return Ackermann(m-1, Ackermann(m, n-1));
  else
    throw exception; //not defined for negative m or n
}

这个函数总是会结束，但它即使对于非常小的输入也会产生极其巨大的结果。例如，Ackermann(4, 2)返回的结果是2⁶⁵⁵³⁶ − 3。

- Kip

---

如果 (m > 0 && n == 0)，则应该返回 Ackermann(m - 1, 1)，而不是 Ackermann(m - 1, n)（也就是 Ackermann(m - 1, 0)）。根据您所引用的维基百科。 - monkey0506

@monkey_05_06，你说得对。我的五年级打字错误已经被更正了。 - Kip

嘿，他们得到了我们的最好成果。 ;) 只是为了记录而澄清。 - monkey0506

Answer 7

另外另外两个“老熟人”是 快速排序 和合并排序（MergeSort）

- agnul

Answer 8

这是一个来自文件系统领域的实用示例。该实用程序递归计算指定目录下的文件数。(我不记得为什么，但很久以前我确实需要这样的东西...)

public static int countFiles(File f) {
    if (f.isFile()){
        return 1;
    }

    // Count children & recurse into subdirs:
    int count = 0;
    File[] files = f.listFiles();
    for (File fileOrDir : files) {
        count += countFiles(fileOrDir);
    }
    return count;
}

（注意，在Java中，File实例既可以表示普通文件，也可以表示目录。此工具从计数中排除了目录。）

一个常见的现实世界的例子是来自Commons IO库的FileUtils.deleteDirectory()；请参阅API文档和源代码。

- Jonik

Answer 9

解释器模式是一个很好的例子，因为很多人没有发现递归。维基百科文章中列出的示例代码很好地说明了如何应用它。然而，一个更基本的方法仍然实现了解释器模式，那就是针对嵌套列表的ToString函数：

class List {
    public List(params object[] items) {
        foreach (object o in items)
            this.Add(o);
    }

    // Most of the implementation omitted …
    public override string ToString() {
        var ret = new StringBuilder();
        ret.Append("( ");
        foreach (object o in this) {
            ret.Append(o);
            ret.Append(" ");
        }
        ret.Append(")");
        return ret.ToString();
    }
}

var lst = new List(1, 2, new List(3, 4), new List(new List(5), 6), 7);
Console.WriteLine(lst);
// yields:
// ( 1 2 ( 3 4 ) ( ( 5 ) 6 ) 7 )

在上面的代码中，如果你期望一个名为 Eval 的函数，那么很难发现解释器模式……但是，实际上，解释器模式并没有告诉我们函数叫什么或者它到底做了什么，而且《设计模式》一书明确将上述内容作为该模式的示例。

- Konrad Rudolph

---

有趣的是，任何迭代都可以表示为fold，而fold又可以被解释（双关语）为一个具有仅两个命令element(e)和NIL的可参数化解释器，其中列表是程序。很酷，对吧？在这里找到了该解释：Functional Programming for Beginners - Rúnar Óli Bjarnason - Boston Area Scala Enthusiasts。 - Jörg W Mittag

嵌套列表实际上是一种快速、粗糙且低效的树形结构，难怪递归很适合它们。 - Kaerber

@Kaerber 我不理解那个评论的结论。我也同意它所提出的前提：嵌套列表就是树，没错。它们既不快速，也不脏乱，也不低效。它们只是一种实现通用树的一种方式，有时候（但诚实地说并不经常）是适当的。 - Konrad Rudolph

抱歉，我还没有仔细考虑过。嵌套列表实际上是树的高效（也是经典）实现之一。结论基于两个隐藏前提：1）递归的唯一好处是遍历树，2）树的字符串表示需要遍历它，并且声明了一个，3）嵌套列表是树。因此，该论点得出结论，实际上，递归对于嵌套列表的toString函数是合适/高效的。 - Kaerber

Answer 10

在我看来，递归是很好掌握的，但是大多数可以使用递归完成的解决方案也可以使用迭代完成，而且迭代效率更高。

话虽如此，这里有一种递归方式可以在嵌套树（比如ASP.NET或Winforms）中查找控件：

public Control FindControl(Control startControl, string id)
{
      if (startControl.Id == id)
           return startControl

      if (startControl.Children.Count > 0)
      {
           foreach (Control c in startControl.Children)
           {
                return FindControl(c, id);
           }
      }
      return null;
}

- Jonathan Holland

---

“而且迭代远比递归更有效率”——这样的笼统说法几乎总是错误的（又是一个例子）。如果使用尾递归，性能与迭代相当。 - Konrad Rudolph

函数式编程的支持者似乎更喜欢尽可能使用递归，并将尾递归等同于迭代作为借口。然而在现实世界中，递归是有代价的。 - Marcus Downing

Stephen，我想我们都写过那个函数超过一次了 :)Konrad，即使是尾递归，也会增加将函数参数推送到堆栈的成本。 - FlySwat

Jon，即使在函数中封装了偶数迭代，“将函数参数推送到堆栈的成本增加了一次”。那么。此外，还有函数调用内联，这也适用于尾递归函数。 - Konrad Rudolph

当您的代码中有几个类似的分支时，迭代效率要低得多。为了举一个好的例子，请尝试将您自己的示例重写为循环形式。这是可能的，但绝对不是微不足道的，并且很难正确实现。 - Kaerber