递归函数的示例

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

1> ConroyP..：

---

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

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.

---

@Joachim Weasel永远是基础案例,老兄._你知道这个!_

---

这个答案让我想起了电影"Inception".

---

而且,这很美.

---

这很好看.

2> Ilya Ryzhenk..：

---

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

3> Kaerber..：

---

递归的经验法则是"使用递归,当且仅当在每次迭代时,您的任务分成两个或更多相似的任务".

所以Fibonacci不是递归应用的一个很好的例子,而河内是一个很好的例子.

因此,大多数递归的好例子都是不同问题中的树遍历.

例如:图遍历 - 访问节点永远不会再次访问的要求使图形成为树(树是没有简单循环的连通图)

分而治之的算法(快速排序,合并排序) - "除"后的部分构成子节点,"征服"从父节点到子节点的构成边.

---

第一句话+1

4> Kip..：

---

如何测试字符串作为回文？

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

当然,你可以更有效地使用循环.

---

为什么提供一个错误的递归示例并批评人们同一件事？

5> Martin Cote..：

---

写一个递归下降解析器!

6> agnul..：

---

另外几个"常见的嫌疑人"是Quicksort和MergeSort

7> Kip..：

---

从数学世界来看,有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)返回2 ⁶⁵⁵³⁶ - 3.

---

`if(m> 0 && n == 0)`它应该返回`Ackermann(m - 1,1)`而不是'Ackermann(m - 1,n)`(这是'Ackermann(m - 1,0)` ).至少根据您引用的维基百科.

---

你是@ monkey_05_06吧.我5岁的错字已得到纠正.

8> Konrad Rudol..：

---

在解释设计模式是一个相当不错的例子,因为很多人不当场递归.维基百科文章中列出的示例代码很好地说明了如何应用它.但是,仍然实现解释器模式的更基本的方法是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书籍列出上述作为所述模式的一个例子.)

9> FlySwat..：

---

在我看来,递归很有必要,但大多数可以使用递归的解决方案也可以使用迭代来完成,迭代效率要高得多.

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

---

"并且迭代效率更高" - 这种一揽子陈述几乎总是错误的(又一个;-)).使用尾递归和性能与迭代相同.

10> Jonik..：

---

这是一个来自文件系统世界的实用例子.此实用程序递归计算指定目录下的文件.(我不记得为什么,但我很久以前就需要这样的东西...)

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

11> joel.neely..：

---

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

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

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

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

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

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

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