35

任何人都可以建议说明递归函数的编程示例吗？有常见的老马，如斐波那契系列和河内塔，但除它们之外的任何东西都会很有趣。

4

22 回答 22

126

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

一个孩子睡不着，所以她妈妈讲了一个小青蛙的故事，
  谁睡不着，所以青蛙的妈妈讲了一个小熊的故事，
     谁睡不着，所以熊妈妈讲了一个小黄鼠狼的故事
       ……谁睡着了。
     ……小熊睡着了；
  ……小青蛙睡着了；
……孩子睡着了。
于 2008-09-24T12:20:54.080 回答
36

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

于 2008-09-24T20:44:23.057 回答
22

递归的经验法则是，“使用递归，当且仅当在每次迭代中您的任务分成两个或更多类似的任务”。

所以斐波那契不是递归应用的好例子，而河内是一个很好的例子。

因此，大多数递归的好例子都是不同讨论中的树遍历。

例如：图遍历 - 访问过的节点永远不会被再次访问的要求有效地使图成为树（树是没有简单循环的连接图）

分治算法（快速排序、合并排序）——“分”之后的部分构成子节点，“征服”构成从父节点到子节点的边。

于 2013-02-27T11:21:46.437 回答
17

测试一个字符串是否为回文怎么样？

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

当然，您可以使用循环更有效地做到这一点。

于 2008-09-24T13:42:32.387 回答
13

编写递归下降解析器！

于 2008-09-24T12:19:38.170 回答
11

在数学世界中，有阿克曼函数：

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 65536 − 3。

于 2008-09-24T13:36:49.840 回答
10

另一对“通常的嫌疑人”是Quicksort和 MergeSort

于 2008-09-24T12:23:41.140 回答
6

解释器设计模式是一个很好的例子，因为很多人没有发现递归。维基百科文章中列出的示例代码很好地说明了如何应用它。但是，仍然实现解释器模式的更基本的方法是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……但实际上，解释器模式并没有告诉我们函数被调用的内容，甚至没有明确地告诉我们函数的作用和 GoF 书将上述内容列为所述模式的示例。）

于 2008-09-24T12:57:55.097 回答
6

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

这里说的是在嵌套树（例如 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;
}
于 2008-09-24T13:50:36.907 回答
6

这是来自文件系统世界的一个实用示例。此实用程序递归地计算指定目录下的文件。（我不记得为什么，但实际上我很久以前就需要这样的东西......）

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实例可以表示普通文件或目录。此实用程序将目录排除在计数之外。）

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

于 2010-05-04T13:17:48.283 回答
5

一个真实的例子是“物料清单成本”问题。

假设我们有一家制造最终产品的制造公司。每个产品都可以通过其部件列表和组装这些部件所需的时间来描述。例如，我们用外壳、电机、卡盘、开关和电线制造手持电钻，只需 5 分钟。

给定每分钟的标准人工成本，制造我们每件产品的成本是多少？

哦，顺便说一句，有些零件（例如电源线）是购买的，所以我们直接知道它们的成本。

但实际上我们自己制造了一些零件。我们用一个外壳、一个定子、一个转子、一个轴和轴承制造了一个电机，这需要 15 分钟。

我们用冲压件和线材制造定子和转子，...

因此，确定成品的成本实际上相当于遍历代表我们流程中所有整体到零件列表关系的树。用递归算法很好地表达了这一点。它当然也可以迭代地完成，但核心思想与自己做的簿记混在一起，所以不清楚发生了什么。

于 2009-02-03T13:49:13.043 回答
2

我知道的最毛茸茸的例子是 Knuth's Man or Boy Test。除了递归之外，它还使用嵌套函数定义（闭包）、函数引用和常量/函数二元论（按名称调用）的 Algol 特性。

于 2008-09-24T12:49:04.870 回答
2

正如其他人已经说过的那样，许多规范递归示例都是学术性的。

我过去遇到的一些实际用途是：

1 - 导航树结构，例如文件系统或注册表

2 - 操作可能包含其他容器控件（如 Panels 或 GroupBoxes）的容器控件

于 2008-10-03T14:38:23.297 回答
1

我个人最喜欢的是二分搜索

编辑：另外，树遍历。例如，遍历文件夹文件结构。

于 2008-09-24T12:18:28.563 回答
1

Guido van Rossum 的《实现图》在 Python 中有一些递归函数来查找图中两个节点之间的路径。

于 2008-09-24T12:20:05.937 回答
1

我最喜欢的排序，合并排序

（最喜欢的，因为我能记住算法，而且在性能方面还不错）

于 2008-09-24T12:20:54.330 回答
0
  • 阶乘
  • 深入遍历树（在文件系统、游戏空间或任何其他情况下）
于 2008-09-24T12:18:55.393 回答
0

反转字符串怎么样？

void rev(string s) {
  if (!s.empty()) {
    rev(s[1..s.length]);
  }
  print(s[0]);
}

理解这一点有助于理解递归。

于 2008-09-24T12:22:40.080 回答
0

处理列表的任何东西怎么样，例如：

  • 地图（和andmap，ormap）
  • 折叠（折叠，折叠）
  • 筛选
  • ETC...
于 2008-09-24T12:25:14.413 回答
0

曾几何时，不久前，小学生使用 Logo 和 Turtle Graphics 学习递归。http://en.wikipedia.org/wiki/Turtle_graphics

递归也非常适合通过详尽的试验来解决难题。有一种叫做“填充”（Google it）的谜题，你会得到一个像填字游戏一样的网格，还有单词，但没有线索，没有编号的方块。我曾经为一个谜题发布者编写了一个使用递归的程序来解决谜题，以确保已知的解决方案是唯一的。

于 2008-10-02T21:22:21.330 回答
0

递归函数非常适合处理递归定义的数据类型：

  • 自然数为零或另一个自然数的后继
  • 列表是空列表或前面有元素的另一个列表
  • 树是具有一些数据和零个或多个其他子树的节点

等等。

于 2008-10-03T14:33:02.763 回答
-1

将电子表格列索引转换为列名。

这比听起来更棘手，因为电子表格列不能正确处理“0”数字。例如，如果在从 Z 递增到 AA 时将 AZ 作为数字，这就像从 9 到 11 或从 9 到 00 而不是 10（取决于 A 是 1 还是 0）。即使是Microsoft 支持示例，对于高于 AAA 的任何内容都出错了！

递归解决方案之所以有效，是因为您可以在那些新数字边界上进行递归。此实现在 VB.Net 中，并将第一列 ('A') 视为索引 1。

Function ColumnName(ByVal index As Integer) As String
    Static chars() As Char = {"A"c, "B"c, "C"c, "D"c, "E"c, "F"c, "G"c, "H"c, "I"c, "J"c, "K"c, "L"c, "M"c, "N"c, "O"c, "P"c, "Q"c, "R"c, "S"c, "T"c, "U"c, "V"c, "W"c, "X"c, "Y"c, "Z"c}

    index -= 1 'adjust index so it matches 0-indexed array rather than 1-indexed column'

    Dim quotient As Integer = index \ 26 'normal / operator rounds. \ does integer division'
    If quotient > 0 Then
        Return ColumnName(quotient) & chars(index Mod 26)
    Else
        Return chars(index Mod 26)
    End If
End Function
于 2008-09-24T16:19:33.757 回答