Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

要求我们推荐或查找工具、库或最喜欢的非现场资源的问题对于Stack Overflow来说是离题的，因为它们往往会吸引固执己见的答案和垃圾邮件。相反，描述问题以及迄今为止为解决该问题所做的工作。

Closed 9 years ago.

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

Answer 1

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

A child couldn t sleep, so her mother told a story about a little frog,
  who couldn t sleep, so the frog s mother told a story about a little bear,
     who couldn t sleep, so bear s mother told a story about a little weasel
       ...who fell asleep.
     ...and the little bear fell asleep;
  ...and the little frog fell asleep;
...and the child fell asleep.

Answer 2

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

Answer 3

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

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

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

For example: graph traversal - the requirement that visited node will never be visited again effectively makes graph a tree (a tree is a connected graph without simple cycles)

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

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);
}

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

Answer 5

编写递归下降语法分析器！

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＜sup＞65536＜/sup＞−3。

Answer 7

另外两个“常见嫌疑人”是快速排序和合并排序

Answer 8

解释器设计模式是一个很好的例子，因为很多人都不知道递归。维基百科文章中列出的示例代码很好地说明了如何应用递归。然而，仍然实现解释器模式的一个更基本的方法是嵌套列表的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 )

（是的，我知道如果你期望一个名为＜code＞Eval＜/code＞的函数，那么在上面的代码中发现解释器模式并不容易……但实际上，解释器模式并没有告诉我们这个函数被调用了什么，甚至没有告诉我们它做了什么，GoF的书明确列出了上面的模式作为所述模式的例子。）

Answer 9

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

也就是说，这里是一种在嵌套树（如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;
}

Answer 10

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

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

一个常见的现实世界示例是Commons IO库；请参阅API文档&；来源。

Answer 11

现实世界中的一个例子是“材料清单成本计算”问题。

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

考虑到每分钟的标准人工成本，我们每种产品的制造成本是多少？

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

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

我们用冲压件和电线制造定子和转子。。。

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

Answer 12

The hairiest example I know is Knuth s Man or Boy Test. As well as recursion it uses the Algol features of nested function definitions (closures), function references and constant/function dualism (call by name).

Answer 13

正如其他人已经说过的，很多规范递归的例子都是学术性的。

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

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

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

Answer 14

我个人最喜欢的是二进制搜索

编辑：还有树遍历。例如，向下遍历文件夹文件结构。

Answer 15

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

Answer 16

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

（最喜欢的是，因为我记得和的算法，它在性能方面还不错吗？）

Answer 17

Factorial
Traversing a tree in depth (in a filesystem, a game space, or any other case)

Answer 18

把绳子倒过来怎么样？

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

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

Answer 19

怎么样？处理列表，如：

map (and andmap, ormap)
fold (foldl, foldr)
filter
etc...

Answer 20

很久以前，也就是不久前，小学生们学习了使用Logo和Turtle Graphics的递归http://en.wikipedia.org/wiki/Turtle_graphics

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

Answer 21

递归函数非常适合使用递归定义的数据类型：

A natural number is zero or the successor of another natural number
A list is the empty list or another list with an element in front
A tree is a node with some data and zero or more other subtrees

等

Answer 22

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

这比听起来更棘手，因为电子表格列无法正确处理0位数。例如，如果在从Z递增到AA时将A-Z作为数字，则类似于从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

友情链接