递归函数示例[闭合]

This illustration 使用英语,而不是实际的编程语言,但对于以非技术性的方式解释过程非常有用:

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.

为了 understand recursion ,必须先了解 recursion .

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

所以Fibonacci不是递归应用的好例子,而Hanoi是一个好例子。

所以大多数递归的好例子都是树遍历在不同的研究中。

例如: 图遍历-访问的节点不再被访问的要求有效地使图成为树(树是没有简单循环的连接图)

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

测试一个字符串作为回文怎么样?

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

当然,你可以更有效的循环。

写一个 recursive descent parser !

另外两个“常见的嫌疑犯”是 Quicksort 合并排序

从数学界来看 the Ackermann function :

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个 三。

这个 interpreter design pattern 是一个很好的例子,因为很多人没有发现递归。维基百科文章中列出的示例代码很好地说明了如何应用这一点。然而,仍然实现解释器模式的更基本的方法是 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的书明确列出了上述模式的一个例子。)

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

这里说的是在嵌套树(如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;
}

下面是一个来自文件系统世界的实用示例。此实用工具递归地计算指定目录下的文件数。(我不记得为什么,但我其实很久以前就需要这样的东西……)

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 doc &安培; source .

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

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

假设每分钟的标准人工成本,生产我们每种产品的成本是多少?

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

但实际上我们自己制造一些零件。我们用一个外壳,一个定子,一个转子,一个轴和轴承制造一个马达,它需要15分钟。

我们用冲压件和金属丝制造定子和转子。。。

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

我知道的最多毛的例子是克努特的 Man or Boy Test . 除了递归,它还使用了嵌套函数定义(闭包)、函数引用和常量/函数二元论(按名称调用)的Algol特性。

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

我在过去遇到的一些实际应用是:

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

2-操作可能包含其他容器控件(如面板或分组框)的容器控件

我个人最喜欢的是 Binary Search

编辑:同样,树遍历。例如,遍历文件夹文件结构。

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

我最喜欢的那种, Merge Sort

(最喜欢,因为我记得算法 和 在性能方面不是太差吗)

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

把绳子倒过来怎么样?

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

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

这是我不久前在这个网站上发布的递归生成菜单树的示例: Recursive Example

有什么事吗 processing lists ,例如:

• map(和andmap,ormap)
• 折叠(foldl,foldr)
• 滤波器
• 等。。。

曾几何时,也就在不久前,小学生们学会了使用Logo和Turtle图形的递归。 http://en.wikipedia.org/wiki/Turtle_graphics

递归对于通过穷举试验解决难题也很有用。有一种拼图叫做“填充”(Google-it),你会得到一个像纵横填字游戏一样的网格,单词,但是没有线索,没有数字方块。我曾经用递归为拼图发布者编写了一个程序来解决这些拼图,以确保已知的解决方案是唯一的。

递归函数对于处理 recursively defined datatypes :

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

等。

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

这比听起来更棘手,因为电子表格列不能正确处理“0”数字。例如,当从Z递增到A A时,如果将A-Z作为数字,则它将从9变为11或9变为00,而不是10(取决于A是1还是0)。甚至 Microsoft Support example 任何高于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