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

解决方案

我个人最喜欢的是Binary Search

编辑：此外，遍历树。例如，沿着文件夹文件结构走。

• 阶乘
• 深入遍历树(在文件系统，游戏空间或者任何其他情况下)

编写递归下降解析器！

由Guido van Rossum实现的图形在Python中具有一些递归函数，用于在图形中的两个节点之间查找路径。

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

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.

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

(最喜欢的是，因为我可以记住算法，并且在性能方面也不错)

反转字符串怎么样？

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

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

另外两个"常疑点"是Quicksort和MergeSort

这是我前不久在此网站上发布的示例，用于递归生成菜单树：递归示例

如何处理列表，例如：

• 映射(and andmap，ormap)
• 折叠(折页，折页)
• 筛选
• 等等...

我知道的最毛的例子是Knuth的"男人或者男孩测试"。
除递归外，它还使用嵌套函数定义(闭包)，函数引用和常量/函数二元论(按名称调用)的Algol功能。

解释器设计模式是一个很好的示例，因为许多人没有发现递归。 Wikipedia文章中列出的示例代码很好地说明了如何应用它。然而，仍然实现解释器模式的更基本的方法是嵌套列表的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这本书明确列出了上述内容作为上述模式的示例。)

在数学世界中，有Ackermann函数：

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)返回265536？ 3.

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

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

当然，我们可以通过循环更有效地执行此操作。

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

也就是说，这是在嵌套树(例如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;
}

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

这比听起来要棘手，因为电子表格列无法正确处理" 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

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

曾几何时，不久前，小学生使用徽标和海龟图形学习了递归。 http://en.wikipedia.org/wiki/Turtle_graphics

递归对于通过详尽的尝试解决难题也非常有用。有一种叫做"填充"(Google it)的难题，其中我们会得到一个像填字游戏的网格，而且这些单词没有线索，没有编号的正方形。我曾经用一个递归程序编写了一个难题发布者程序，以解决难题，以确保已知的解决方案是唯一的。

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

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

等等。

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

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

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

2操作可能包含其他容器控件的容器控件(例如Panel或者GroupBoxes)

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

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

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

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

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

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

因此，确定成品的成本实际上等于遍历表示我们流程中所有整体与零件清单关系的树。用递归算法很好地表达了这一点。当然也可以迭代完成，但是核心思想与"自己动手做"簿记混在一起，所以目前尚不清楚。

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

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文档和来源。