似乎经常出现在邮件列表和在线讨论中的主题之一是获得计算机科学学位的优点(或者缺乏优点)。反对派似乎反复提出的一个论点是，他们已经编码了多年，并且从未使用过递归。

所以问题是：

• 什么是递归？
• 什么时候使用递归？
• 人们为什么不使用递归？

解决方案

回答

• 调用自身的函数
• 当一个函数可以(轻松)分解为一个简单的操作，再加上相同的函数就可以解决问题的较小部分。我应该说，这使其成为递归的良好候选者。
• 他们是这样！

典型的例子是阶乘，如下所示：

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

通常，递归不一定很快(函数调用开销往往很高，因为递归函数通常很小，请参见上文)，并且可能会遇到一些问题(堆栈溢出有人吗？)。有人说，在不平凡的情况下，他们往往很难做到"正确"，但我并不真的同意。在某些情况下，递归最有意义，并且是编写特定函数的最优雅，最清晰的方法。应该注意的是，某些语言更喜欢递归解决方案并对其进行更多优化(LISP浮现在脑海)。

回答

递归函数是一个自行调用的函数。我发现使用它的最常见原因是遍历树结构。例如，如果我有一个带复选框的TreeView(请考虑安装新程序，"选择要安装的功能"页面)，则可能需要一个"全部选中"按钮，该按钮应如下所示(伪代码)：

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

因此，我们可以看到checkRecursively首先检查传递该节点的节点，然后为该节点的每个子节点调用自身。

我们确实需要对递归小心一点。如果进入无限递归循环，则会出现堆栈溢出异常:)

我想不出人们在适当的时候不应该使用它的原因。在某些情况下有用，而在其他情况下则无用。

我认为，因为这是一种有趣的技术，所以某些编码人员可能最终在没有实际理由的情况下比他们应有的使用频率更高。这在某些圈子中给递归一个坏名字。

回答

递归是一种基于分而治之的思想来解决问题的方法。
基本思想是将原始问题分解为自身的较小(更容易解决)的实例，再求解这些较小的实例(通常通过再次使用相同的算法)，然后将它们重新组合为最终解决方案。

典型的例子是生成n阶乘的例程。 n的阶乘通过将1和n之间的所有数字相乘来计算。 Clook中的迭代解决方案如下所示：

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

迭代解决方案不足为奇，对于熟悉C＃的任何人都应该有意义。

通过认识到第n个阶乘为n * Fact(n-1)来找到递归解。或者换一种说法，如果我们知道特定的阶乘数，则可以计算下一个。这是C＃中的递归解决方案：

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

此功能的第一部分称为基本案例(有时称为保护子句)，它是阻止算法永久运行的原因。只要调用函数的值等于或者小于1，它就返回值1. 第二部分更有趣，称为"递归步骤"。在这里，我们使用稍有修改的参数调用相同的方法(将其递减1)，然后将结果与n的副本相乘。

初次遇到时可能会造成混淆，因此检查运行时的工作方式很有启发性。假设我们调用FactRec(5)。我们进入了例程，没有被基本案例所接受，所以我们最终像这样：

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

如果我们使用参数4重新输入该方法，那么我们不会再次被Guard子句阻止，因此最终结果是：

// In FactRec(4)
return 4 * FactRec(3);

如果将这个返回值代入上面的返回值，我们得到

// In FactRec(5)
return 5 * (4 * FactRec(3));

这应该为我们提供最终解决方案的线索，因此我们将快速跟踪并显示下一个步骤：

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

当触发基本情况时，将发生最终替换。至此，我们有了一个简单的代数公式来求解，该公式首先直接等于阶乘的定义。

请注意，对方法的每次调用都会导致触发基本情况或者对参数更接近基本情况的同一方法进行调用(通常称为递归调用)。如果不是这种情况，则该方法将永远运行。

回答

我创建了一个递归函数来连接字符串列表，并在它们之间使用分隔符。我主要使用它来创建SQL表达式，方法是将字段列表传递为"项"，并使用"逗号+空格"作为分隔符。这是函数(它使用一些Borland Builder本机数据类型，但可以进行调整以适合任何其他环境)：

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

我这样称呼它：

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

假设我们有一个名为" fields"的数组，其中包含以下数据：" albumName"，" releaseDate"，" labelId"。然后调用该函数：

ArrangeString(fields, 0, ", ");

随着函数开始工作，变量"结果"将接收数组位置0的值，即" albumName"。

然后，它检查所处理的位置是否是最后一个。如果不是，那么它将结果与分隔符和一个函数的结果连接起来，哦，天哪，这是相同的函数。但是这一次，将其检出，它会自己调用该位置加1.

ArrangeString(fields, 1, ", ");

它不断重复，创建一个LIFO堆，直到到达要处理的位置是IS的最后一个点为止，因此该函数仅返回列表中该位置上的项目，不再进行连接。然后将桩向后连接。

知道了？如果没有，我还有另一种解释的方式。 ：o)

回答

递归最适合我所谓的"分形问题"，在这种情况下，我们要处理的是由较小的版本组成的大型项目，每个版本都是较小的版本，依此类推。如果我们不得不遍历或者搜索诸如树或者嵌套的相同结构之类的东西，那么我们可能会遇到一个问题，该问题可能是递归的一个不错的选择。

人们出于多种原因而避免递归：

• 与函数式编程相反，大多数人(包括我本人)在过程式或者面向对象的编程方面都花了很多时间。对于这样的人，迭代方法(通常使用循环)感觉更自然。
• 我们当中经常在程序式或者面向对象的程序设计上费劲的人经常被告知要避免递归，因为它容易出错。
• 人们经常被告知递归很慢。从例程中反复调用和返回会涉及大量堆栈推入和弹出操作，这比循环要慢。我认为有些语言比其他语言处理得更好，而那些语言很可能不是那些主要范式是过程性或者面向对象的语言。
• 对于至少我使用过的两种编程语言，我记得听到有人建议不要使用递归，如果递归超出一定深度，因为它的堆栈并不那么深。

回答

这是一个简单的示例：一个集合中有多少个元素。 (有更好的计数方法，但这是一个很好的简单递归示例。)

首先，我们需要两个规则：

• 如果集合为空，则集合中的项目数为零(duh！)。
• 如果集合不为空，则计数为1加上删除一个项目后集合中的项目数。

假设我们有一个这样的集合：[x x x]。让我们计算一下有多少个项目。

• 该集合为[x x x]，该值不为空，因此我们应用规则2. 项目数为1加[x x]中的项目数(即我们删除了一个项目)。
• 该集合为[x x]，因此我们再次应用规则2：[x]中的一个+项数。
• 集合为[x]，仍与规则2匹配：[+]中的一个+项数。
• 现在集合为[]，它与规则1匹配：计数为零！
• 现在我们知道步骤4(0)的答案，我们可以解决步骤3(1 + 0)
• 同样，既然我们知道步骤3(1)的答案，我们就可以解决步骤2(1 +1)
• 最后，现在我们知道步骤2(2)的答案了，我们可以求解步骤1(1 + 2)，并在[x x x]中得到3的项数。万岁！

我们可以这样表示：

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

应用递归解决方案时，通常至少有2条规则：

• 在此基础上，简单的案例说明了当我们"用完"所有数据时会发生什么。这通常是"如果要处理的数据不足，答案是X"的某种变体。
• 递归规则，该规则指出如果我们仍然有数据会发生什么情况。这通常是一种规则，说"做一些事情以使数据集更小，然后将规则重新应用于较小的数据集"。

如果将以上代码转换为伪代码，则会得到：

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

我相信还有很多更有用的示例(例如，遍历一棵树)。

回答

我使用递归。这与拥有CS学位有什么关系(顺便说一句，我不是)

我发现的常见用途：

• 网站地图-从文件根目录开始通过文件系统递归
• 蜘蛛-在网站上爬行以查找电子邮件地址，链接等。
• ？

回答

Mario，我不明白我们为什么在该示例中使用递归。为什么不简单地遍历每个条目？像这样的东西：

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

上面的方法会更快，更简单。无需使用递归代替简单的循环。我认为这些示例就是为什么递归会带来不好的说唱。甚至典范阶乘函数示例也可以通过循环更好地实现。

回答

递归解决问题：什么都不做，就完成了。
要对一个未解决的问题进行递归：下一步，然后对其余的递归。

回答

在该线程中有许多关于递归的很好的解释，这个答案是关于为什么不应该在大多数语言中使用它的原因。*在大多数主要的命令式语言实现中(即C，C ++，Basic，Python的每个主要实现) ，Ruby，Java和C＃)迭代远胜于递归。

要了解原因，请逐步完成上述语言用于调用函数的步骤：

• 在函数的参数和局部变量的堆栈上刻出了空格
• 函数的参数将复制到此新空间中
• 控制跳至功能
• 该函数的代码运行
• 函数的结果被复制到返回值
• 将纸叠倒回其先前位置
• 控件跳回到调用该函数的位置

完成所有这些步骤需要花费时间，通常比迭代循环要花费更多的时间。但是，真正的问题是在步骤1中。当许多程序启动时，它们会为其堆栈分配一个内存块，而当它们用完该内存时(通常但并非总是由于递归)，程序会由于堆栈溢出而崩溃。

因此，在这些语言中，递归速度较慢，因此很容易崩溃。虽然仍然有一些使用它的争论。通常，一旦我们知道如何阅读，则以递归方式编写的代码会更短，也更优雅。

语言实现者可以使用一种称为尾调用优化的技术，该技术可以消除某些类别的堆栈溢出。简而言之：如果函数的返回表达式只是函数调用的结果，那么我们无需在堆栈上添加新级别，则可以将当前级别重用于所调用的函数。遗憾的是，几乎没有命令式语言实现内置了尾部调用优化功能。

*我喜欢递归。我最喜欢的静态语言根本不使用循环，递归是重复执行操作的唯一方法。我只是不认为在没有针对此语言进行调整的语言中，递归通常不是一个好主意。

**顺便提一下，Mario，ArrangeString函数的典型名称是" join"，如果我们选择的语言还没有实现它，我会感到惊讶。

回答

我们想在具有树形结构的任何时候使用它。在读取XML时非常有用。

回答

实际上，阶乘的更好的递归解决方案应该是：

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

因为此版本是尾递归

回答

在最基本的计算机科学意义上，递归是一个自称的功能。假设我们有一个链表结构：

struct Node {
    Node* next;
};

我们想找出一个链表有多长，可以通过递归来做到这一点：

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(这当然也可以通过for循环来完成，但是对于概念的说明很有用)

回答

递归应用于编程时，基本上是从其自己的定义内部(本身内部)调用函数，并使用不同的参数来完成任务。

回答

递归指的是一种解决问题的方法，方法是解决问题的较小版本，然后使用该结果加上一些其他计算来为原始问题制定答案。通常，在解决较小版本的过程中，该方法将解决问题的较小版本，依此类推，直到达到无法解决的"基本情况"。

例如，要计算数字" X"的阶乘，可以将其表示为" X乘以X-1"的阶乘。因此，方法"递归"以找到" X-1"的阶乘，然后将其乘以" X"得到最终答案。当然，要找到" X-1"的阶乘，首先要计算" X-2"的阶乘，依此类推。基本情况是" X"为0或者1时，在这种情况下，它知道从" 0"开始返回" 1"！ = 1！ = 1`。

回答

好吧，这是一个相当不错的定义。维基百科也有一个很好的定义。因此，我将为我们添加另一个(可能更糟)的定义。

人们提到"递归"时，通常是在谈论他们编写的函数，该函数会反复调用自身，直到完成其工作为止。遍历数据结构中的层次结构时，递归可能会有所帮助。

回答

我喜欢这个定义：

在递归中，例程本身解决问题的一小部分，将问题分成较小的部分，然后调用自身来解决每个较小的部分。

Don't use recursion for factorials or Fibonacci numbers
  
  One problem with
  computer-science textbooks is that
  they present silly examples of
  recursion. The typical examples are
  computing a factorial or computing a
  Fibonacci sequence. Recursion is a
  powerful tool, and it's really dumb to
  use it in either of those cases. If a
  programmer who worked for me used
  recursion to compute a factorial, I'd
  hire someone else.

我也喜欢史蒂夫·麦康奈尔(Steve McConnells)在Code Complete中对递归的讨论，他批评计算机科学有关递归的书籍中使用的示例。

我认为这是一个非常有趣的观点，并且可能是递归经常被误解的原因。

回答

编辑：
这不是Dav的回答，我发布此消息时没有看到该回复

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

回答

递归正在使用调用自身的函数解决问题。阶乘函数就是一个很好的例子。阶乘是一个数学问题，例如5阶乘是5 * 4 * 3 * 2 *1. 此函数用C表示正整数(未经测试可能存在错误)。

"如果我有锤子，那就让一切看起来都像钉子。"

例子

递归是解决大问题的一种解决问题的策略，在此过程中，每一步只需用相同的锤子"将两件小事变成一件大事"即可。

• 分度：将所有工作表展开，因此每个"堆栈"中只有一个工作表。
• 四处走动，将每个2堆栈放在另一个2堆栈的顶部。我们现在有4叠。
• 四处走动，将每个4堆栈放在另一个4堆栈的顶部。我们现在有8叠。
• ...不断...
• 我们现在有一叠1024张纸！

假设办公桌上满是乱七八糟的1024张纸。我们如何使用递归从混乱中整理出整齐干净的纸叠？

回答

请注意，除了对所有内容进行计数(这并非绝对必要)之外，这是非常直观的。实际上，我们可能不会一直走到1张纸叠，但是我们可以并且它仍然可以工作。重要的部分是锤子：用胳膊，我们可以始终将一个堆栈叠放在另一个堆栈上，以形成更大的堆栈，并且(在合理的情况下)两个堆栈的大小无关紧要。

递归是直接或者间接引用自身的表达式。

• GNU代表GNU的非Unix
• PHP代表PHP：超文本预处理程序
• YAML代表YAML不是标记语言
• WINE代表Wine不是模拟器
• VISA代表Visa国际服务协会

考虑将递归首字母缩写作为一个简单示例：

回答

维基百科上的更多示例

它是一种无限期地重复做事的方式，以便使用每个选项。

例如，如果我们想获取html页面上的所有链接，则将需要递归，因为当我们获取页面1上的所有链接时，我们将希望获取首页上每个链接上的所有链接。那么对于到新页面的每个链接，我们将需要这些链接，依此类推...换句话说，这是一个从自身内部调用自身的函数。

执行此操作时，我们需要一种方法来知道何时停止，否则我们将陷入无限循环，因此我们需要向函数添加整数参数以跟踪循环数。

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}

回答

在cyou中将有以下内容：

回答

递归是方法调用iself能够执行特定任务的过程。它减少了代码的冗余。大多数递归函数或者方法都必须具有条件才能中断对冲调用，即，如果满足条件，则阻止其自行调用，这会阻止创建无限循环。并非所有函数都适合递归使用。

用简单的英语来说，递归意味着一次又一次地重复输入。

在编程中，一个示例是在自身内部调用该函数。

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

回答

查看以下计算数字阶乘的示例：

嘿，对不起，如果我的观点与某人相同，我只是想用简单的英语解释递归。

假设我们有三位经理Hyman，约翰和摩根。
Hyman管理着2个程序员，约翰3和摩根5.
我们要给每位经理300美元，并想知道要花多少钱。
答案是显而易见的，但是如果Morgan的2位员工也是经理，该怎么办？

这里是递归。
我们从层次结构的顶部开始。夏季费用为0美元。
你从Hyman开始，
然后检查他是否有经理作为雇员。如果找到他们中的任何一个，请检查他们是否有经理作为员工，依此类推。每次我们找到经理时，都要在夏季费用中加300 $。
与Hyman谈完后，去找约翰，他的雇员，然后去摩根。

我们将永远不会知道，在获得答案之前，我们将经过多少个周期，尽管我们知道自己有多少经理人以及可以花费多少预算。

回答

递归是一棵树，有树枝和树叶，分别称为父母和孩子。
使用递归算法时，我们或者多或者少有意识地正在根据数据构建树。

• 拿一个苹果
• 写下理货标记
• 计数标记

用简单的英语：
假设我们可以做三件事：

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

桌子上，我们面前有很多苹果，我们想知道有多少个苹果。

重复执行相同的操作直到完成为止的过程称为递归。

回答

希望这是我们正在寻找的"普通英语"答案！

递归语句是我们在其中定义下一步操作的过程的过程，该过程将输入与我们已经完成的工作结合在一起。

factorial(6) = 6*5*4*3*2*1

例如，采用阶乘：

6 * factorial(5) = 6*(5*4*3*2*1).

但不难发现阶乘(6)也是：

factorial(n) = n*factorial(n-1)

因此，通常：

当然，关于递归的棘手问题是，如果我们想根据已经完成的工作来定义事物，则需要有一些起点。

在此示例中，我们只是通过定义factorial(1)= 1来做一个特例。

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

现在我们从下往上看：

由于我们定义了factorial(1)= 1，因此我们到达了"底部"。

一般来说，递归过程包括两个部分：

1)递归部分，它根据新输入和通过相同过程"已经完成"的内容来定义一些过程。 (即factorial(n)= n * factorial(n-1))

2)一个基本部分，它通过给它一定的开始位置来确保该过程不会永远重复(例如factorial(1)= 1)

刚开始时可能会有些困惑，但是只要看一堆示例，所有示例都应该结合在一起。如果我们想对这个概念有更深入的了解，请学习数学归纳法。另外，请注意，某些语言针对递归调用进行了优化，而另一些则没有。如果我们不小心的话，很容易制作出极其缓慢的递归函数，但是在大多数情况下，也有一些技巧可以使它们表现出色。

回答

希望这可以帮助...

每当一个函数调用自身，创建一个循环时，这就是递归。与任何东西一样，递归有好用和坏用。

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

最简单的示例是尾部递归，其中函数的最后一行是对自身的调用：

但是，这是一个la脚，几乎毫无意义的示例，因为可以轻松地用更有效的迭代代替它。毕竟，递归会受到函数调用开销的影响，在上面的示例中，与函数本身内部的操作相比，递归开销很大。

因此，进行递归而不是迭代的全部原因应该是利用调用堆栈来做一些聪明的事情。例如，如果我们在同一循环内使用不同的参数多次调用函数，则这是完成分支的一种方法。一个典型的例子是Sierpinski三角形。

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

我们可以使用递归非常简单地绘制其中之一，其中调用堆栈在3个方向上分支：

如果我们尝试对迭代执行相同的操作，我想我们会发现需要花费更多的代码来完成。

其他常见用例可能包括遍历层次结构，例如网站搜寻器，目录比较等

结论

回答

实际上，无论何时需要迭代分支，递归都是最有意义的。

回答

一个示例：楼梯的递归定义为：
楼梯包括：
一步和楼梯(递归)
或者仅一步(终止)

如果基本上由一个带有每个数据案例的案例的开关状态组成，则任何算法都将表现出对该数据类型的结构递归。

tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

例如，当我们处理一种类型时

function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

结构递归算法的形式为

这实际上是编写适用于数据结构的任何算法的最明显方法。

integer = 0 | succ(integer)

现在，当我们查看使用Peano公理定义的整数(自然数)时

function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

我们会看到整数的结构递归算法如下所示

回答

太著名的阶乘函数是关于
这种形式。

In mathematics, the greatest common divisor (gcd) … of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

考虑一个古老的，众所周知的问题：

gcd的定义非常简单：

其中mod是取模运算符(即整数除法后的余数)。

用英语定义，该数字表示任何数字和零的最大公约数是该数字，两个数字m和n的最大公约数是n的最大公约数，以及m除以n后的余数。

如果我们想知道为什么这样做，请参阅有关欧几里德算法的Wikipedia文章。

• gcd(10，8)
• gcd(10，10 mod 8)
• gcd(8，2)
• gcd(8，8 mod 2)
• gcd(2，0)
• 2个

让我们以gcd(10，8)为例进行计算。每一步都等于前一步：

在第一步中，8不等于零，因此该定义的第二部分适用。 10 mod 8 = 2，因为8一次乘以10，余数为2. 在步骤3，第二部分再次适用，但是这次8 mod 2 = 0，因为2除以8，没有余数。在步骤5，第二个参数为0，因此答案为2.

我们是否注意到gcd出现在等号的左右两侧？数学家会说此定义是递归的，因为我们要定义的表达式在其定义内出现。

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

递归定义往往很优雅。例如，列表总和的递归定义为

其中" head"是列表中的第一个元素，而" tail"是列表中的其余元素。请注意，sum最后出现在其定义内。

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

也许我们更希望列表中的最大值：

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

我们可以递归定义非负整数的乘法，以将其转换为一系列加法运算：

如果将乘法转换为一系列加法没有意义，请尝试扩展一些简单的示例以了解其工作原理。

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

合并排序有一个不错的递归定义：

如果我们知道要查找的内容，则到处都有递归定义。请注意所有这些定义如何具有非常简单的基本情况，例如gcd(m，0)= m。递归案例减少了问题，以求出简单的答案。

回答

有了这种了解，我们现在就可以欣赏Wikipedia递归文章中的其他算法！

回答

函数调用自身或者使用其自己的定义。

计算中的递归是一种用于根据单个函数(方法，过程或者块)调用的正常返回来计算结果或者副作用的技术。

根据定义，递归函数必须具有直接或者间接(通过其他函数)调用自身的能力，具体取决于退出条件或者不满足的条件。如果满足退出条件，则特定的调用将返回到其调用方。这种情况一直持续到返回初始调用为止，届时可获得所需的结果或者副作用。

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

例如，这是在Scala中执行Quicksort算法的功能(从Wikipedia条目中复制为Scala)

回答

在这种情况下，退出条件为空列表。

递归是一种根据自身定义函数，集合或者算法的技术。

n! = n(n-1)(n-2)(n-3)...........*3*2*1

例如

n! = n(n-1)!   for n>=1

现在可以将其递归定义为：-

回答

用编程的术语来说，当一个函数或者方法重复调用自己，直到满足某些特定条件时，此过程称为递归。但是必须有一个终止条件，并且函数或者方法不得进入无限循环。

• 基本案例，这是我们可以通过查看基本问题而解决的基本问题，以及
• 递归案例，从较小的部分(基本的或者其他的)中构建出更大的问题。

许多问题可以分为两种类型：

那么什么是递归函数？好的，那是我们直接或者间接根据自身定义的功能的地方。好吧，这听起来很荒谬，直到我们意识到对上述类型的问题是明智的：我们直接解决基本案例并通过使用递归调用解决嵌入其中的较小问题来处理递归案例。

struct Tree {
    int leaf;
    Tree *leftBranch;
    Tree *rightBranch;
};

需要递归(或者闻起来很像的东西)的真正经典示例是在处理树时。树的叶子是基本情况，而分支是递归情况。 (在伪C中。)

function printTreeInOrder(Tree *tree) {
    if (tree->leftBranch) {
        printTreeInOrder(tree->leftBranch);
    }
    print(tree->leaf);
    if (tree->rightBranch) {
        printTreeInOrder(tree->rightBranch);
    }
}

为了打印出来的最简单的方法是使用递归：

由于它非常清晰，因此很难看到它会起作用。 (非递归等效项要复杂得多，内部需要一个堆栈结构来管理要处理的事物列表。)好吧，假设当然没有人进行循环连接。

在数学上，显示递归已被驯服的技巧是着重于找到参数大小的度量。对于我们的树示例，最简单的度量标准是树在当前节点下方的最大深度。在叶子处，它为零。在只有下面的叶子的分支上，是一个，依此类推。然后，我们可以简单地显示出，为处理树而调用该函数的参数的大小严格按照顺序排列。从度量的角度来看，递归调用的参数总是比整体调用的参数"更少"。使用严格降低的基本指标，我们可以得到排序。

回答

无限递归也是可能的。这很麻烦，并且在许多语言中都无法正常工作，因为堆栈已耗尽。 (在确实起作用的地方，语言引擎必须确定该函数以某种方式不会返回，并因此能够优化堆栈的保持。通常棘手的东西；尾递归只是实现此目的最简单的方法)

递归是指我们有一个使用自身的操作。它可能会有一个停止点，否则它将永远持续下去。

假设我们要在字典中查找一个单词。我们可以使用名为"查找"的操作。

朋友说："我现在真的可以加一些布丁！"我们不知道他的意思，因此我们在字典中查找"勺子"，它的内容如下：

汤匙：名词末尾带有圆形勺的器皿。
汤匙：动词在某物上使用汤匙
勺子：动词从后面紧紧地拥抱

现在，由于我们真的对英语不太熟练，因此可以为我们指明正确的方向，但我们需要更多信息。因此，我们选择" utensil"和" cuddle"以查找更多信息。

拥抱：动词依ugg
器具：名词是一种工具，通常是一种饮食用具

嘿！你知道什么是依ugg，与布丁无关。我们还知道布丁是我们要吃的东西，所以现在很有意义。朋友一定想用勺子吃布丁。

好的，好的，这是一个非常la脚的示例，但是它说明了(可能很差)递归的两个主要部分。
1)它使用自己。在此示例中，直到真正理解一个单词，我们才真正有意义地查找它，这可能意味着查找更多的单词。这使我们指出了第二点，
2)它停在某个地方。它必须具有某种基本情况。否则，我们最终只会在字典中查找每个单词，这可能不太有用。我们的基本情况是，我们获得了足够的信息，可以在我们以前所做的和不了解的之间建立联系。

给出的传统示例是阶乘，其中5阶乘是1 * 2 * 3 * 4 * 5(即120)。基本情况将为0(或者1，视情况而定)。因此，对于任何整数n，请执行以下操作

n等于0吗？返回1
否则，返回n *(n-1的阶乘)

让我们以4的示例进行此操作(我们提前知道的是1 * 2 * 3 * 4 = 24)。

4的阶乘...是0吗？不，因此必须为4 * 3的阶乘
但是3的阶乘是多少？它是3 * 2的阶乘
2的阶乘为2 * 1的阶乘
1的阶乘为1 * 0的阶乘
并且我们知道阶乘为0！ :-D为1，即定义
1的阶乘是1 * 0的阶乘是1 ...所以1 * 1 = 1
2的阶乘是2 * 1的阶乘是1 ...所以2 * 1 = 2
3的阶乘是3 * 2的阶乘是2 ...所以3 * 2 = 6
4的阶乘(最终！)是4 * 3的阶乘，即6 ... 4 * 6是24

阶乘是"基本情况，并使用其自身"的简单情况。

回答

现在，请注意，在整个下降过程中，我们仍在处理4的阶乘...如果我们想要100的阶乘，则必须一直下降到0 ...这可能会有很多开销。同样，如果我们在字典中找到一个晦涩的单词，可能会查找其他单词并扫描上下文线索，直到找到我们熟悉的连接为止。递归方法可能需要很长时间才能完成。但是，只要正确使用并理解它们，它们就能使复杂的工作变得异常简单。

递归的最简单定义是"自引用"。自指的功能，即e。调用本身是递归的。要记住的最重要的一点是，递归函数必须具有"基本情况"，即e。一种条件，如果为true，则导致其不调用自身，从而终止递归。否则，我们将具有无限递归：

回答

递归http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her 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.

回答

递归的简单英语示例。

递归函数是包含对其自身的调用的函数。递归结构是包含自身实例的结构。我们可以将两者组合为递归类。递归项的关键部分是它包含一个自身的实例/调用。

考虑两个彼此面对的镜子。我们已经看到了它们产生的整洁的无限效果。每个反射都是反射镜的一个实例，该反射镜包含在另一个反射镜的实例等中。包含自身反射的反射镜是递归的。

段落数量不匹配