computer science -什么是递归?什么时候使用它?

Translate

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

所以问题是:

  1. 什么是递归?
  2. 什么时候使用递归?
  3. 人们为什么不使用递归?
This question and all comments follow the "Attribution Required."

所有的回答

Translate

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

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

  1. 在上面雕刻出空间堆栈函数的参数和局部变量
  2. 函数的参数将复制到此新空间
  3. 控制跳至功能
  4. 该函数的代码运行
  5. 函数的结果被复制到返回值
  6. 将纸叠倒回其先前位置
  7. 控件跳回到调用该函数的位置

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

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

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

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

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

来源
Translate

递归的简单英语示例。

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.
来源
Sally Lee
Translate

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

struct Node {
    Node* next;
};

您想找出一个链表有多长,可以通过递归来做到这一点:

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

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

来源
Translate

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

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

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

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

因此,进行递归而不是迭代的全部原因应该是利用调用堆栈做一些聪明的事情。例如,如果您在同一循环中多次使用不同的参数调用函数,则这是一种完成方法分枝。一个典型的例子是谢尔宾斯基三角形.

enter image description here

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

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

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

其他常见用例可能包括遍历层次结构,例如网站爬网程序,目录比较等。

结论

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

来源
Translate

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

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

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

此功能的第一部分称为基本情况(或有时是Guard子句),这是阻止算法永久运行的原因。只要调用函数的值等于或小于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))));

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

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

来源
Victoria Lee
Translate

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

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

    return n * Factorial(n - 1);
}
来源
Norma Lee
Translate

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

例如,计算数字的阶乘X,可以将其表示为X times the factorial of X-1。因此,方法“递归”以找到X-1,然后乘以得到的结果X给出最终答案。当然,要找到阶乘X-1,它将首先计算的阶乘X-2, 等等。基本情况是X是0或1,在这种情况下它知道要返回1以来0! = 1! = 1.

来源
Eunice Lee
Translate

考虑一个旧的,众所周知的问题:

在数学中,最大公约数(gcd)…是两个或多个非零整数,是将数字除而无余的最大正整数。

gcd的定义非常简单:

gcd definition

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

用英语来说,此定义表示任何数字的最大公约数和零是那个数字,以及两个数字的最大公约数mn是...的最大公约数n剩下的除以m通过n.

如果您想知道为什么这样做,请参阅以下网址上的Wikipedia文章:欧几里得算法.

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

  1. gcd(10,8)
  2. gcd(10,10 mod 8)
  3. gcd(8,2)
  4. gcd(8,8 mod 2)
  5. gcd(2,0)
  6. 2

在第一步中,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。递归案例减少了问题,以求出简单的答案。

有了这些了解,您现在可以欣赏其中的其他算法维基百科有关递归的文章!

来源
Kama Lee
Translate
  1. 自我调用的功能
  2. 当一个函数可以(轻松)分解为一个简单的操作,再加上相同的函数就可以解决问题的较小部分。我应该说,这使其成为递归的良好候选者。
  3. 他们是这样!

典型的例子是阶乘,如下所示:

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

  return a*fact(a-1);
}

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

来源
Beau Lee
Translate

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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

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

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

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

我认为,因为这是一种有趣的技术,所以某些编码人员可能最终在没有实际理由的情况下经常使用它。这在某些圈子中给递归一个坏名字。

来源
Freda Lee
Translate

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

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

  • GNU代表GNU不是Unix
  • 的PHP代表PHP:超文本预处理器
  • YAML代表YAML不是标记语言
  • 葡萄酒代表酒不是模拟器
  • 签证代表签证国际服务协会

维基百科上的更多示例

来源
Dorothy Lee
Translate

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

人们避免递归的原因有很多:

  1. 与函数式编程相反,大多数人(包括我本人)在程序式或面向对象的编程方面都花了很多时间。对于这样的人,迭代方法(通常使用循环)感觉更自然。

  2. 我们当中经常在程序式或面向对象的程序设计上费心的人经常被告知要避免递归,因为它容易出错。

  3. 人们经常被告知递归很慢。从例程中反复调用和返回涉及大量堆栈推入和弹出,这比循环要慢。我认为某些语言比其他语言处理得更好,而那些语言很可能不是那些主要范式是过程性或面向对象的语言。

  4. 对于至少我使用过的两种编程语言,我记得听到有人建议不要使用递归,除非递归超过一定深度,因为递归并不那么深。

来源
May Lee
Translate

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

例如,采用阶乘:

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

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

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

因此,通常:

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)

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

希望这可以帮助...

来源
Odelia Lee
Translate

我喜欢这个定义:
在递归中,例程本身解决问题的一小部分,将问题分成较小的部分,然后调用自身来解决每个较小的部分。

我也喜欢Steve McConnells在Code Complete中对递归的讨论,他在其中批评了计算机科学中有关递归的示例。

不要对阶乘或斐波那契数使用递归

计算机科学教科书的一个问题是它们提供了一些愚蠢的递归示例。典型示例是计算阶乘或计算斐波纳契数列。递归是一个功能强大的工具,在任何一种情况下使用它都非常愚蠢。如果为我工作的程序员使用递归来计算阶乘,那么我会雇用其他人。

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

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

来源
Translate

1.)方法可以递归调用;直接:

void f() {
   ... f() ... 
}

或间接地:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.)何时使用递归

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.)人们仅在编写迭代代码非常复杂时才使用递归。例如,可以使树遍历技术(例如预排序,后排序)既可以迭代也可以递归。但通常由于其简单性,我们使用递归。

来源
Translate

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

首先,我们需要两个规则:

  1. 如果集合为空,则集合中的项目数为零(duh!)。
  2. 如果集合不为空,则计数为1加上删除一个项目后集合中的项目数。

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

  1. 该集合为[xxx],不为空,因此我们应用规则2。项目数为1加[xx]中的项目数(即,我们删除了一个项目)。
  2. 该集合为[xx],因此我们再次应用规则2:[x]中的一个+项数。
  3. 集合为[x],仍与规则2匹配:[+]中的+ 1个项目。
  4. 现在集合为[],与规则1匹配:计数为零!
  5. 现在我们知道步骤4(0)的答案,我们可以解决步骤3(1 + 0)
  6. 同样,现在我们知道步骤3(1)的答案,我们可以解决步骤2(1 +1)
  7. 最后,现在我们知道步骤2(2)的答案了,我们可以求解步骤1(1 + 2),并在[xxx]中获得项目计数,即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)

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

来源
Bblythe Lee
Translate

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

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

来源
Wordsworth Lee
Translate

示例:楼梯的递归定义为:楼梯包含:-单个步骤和一个楼梯(递归)-或仅单个步骤(终止)

来源
Corey Lee
Translate

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

来源
Alvin Lee
Translate

用简单的英语来说:假设您可以做三件事:

  1. 拿一个苹果
  2. 写下理货标记
  3. 计数标记

桌子上,您面前有很多苹果,您想知道有多少个苹果。

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

重复相同的事情直到完成为止的过程称为递归。

希望这是您正在寻找的“普通英语”答案!

来源
Daniel Lee
Translate

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

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

A 二叉搜索树是递归的一个很好的编程示例。该结构是递归的,每个节点包含一个节点的2个实例。在二叉搜索树上工作的函数也是递归的。

来源
Gloria Lee
Translate

这是一个古老的问题,但是我想从后勤的角度(即不是从算法正确性或性能的角度)添加一个答案。

我使用Java进行工作,而Java不支持嵌套函数。这样,如果我想进行递归操作,则可能必须定义一个外部函数(仅由于我的代码违反了Java的官僚规则而存在),或者我可能必须完全重构代码(我真的很讨厌这样做)。

因此,我经常避免递归,而改用堆栈操作,因为递归本身本质上是一个堆栈操作。

来源
Ben Lee
Translate

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

来源
Nina Lee
Translate

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

来源
Pearl Lee
Translate

“如果我有锤子,那就让一切看起来都像钉子。”

递归是解决问题的策略巨大问题,每一步都用同一把锤子“将两件小事变成一件大事”。

假设您的办公桌上满是乱七八糟的1024张纸。您如何使用递归方法从一团糟中整理出整齐干净的纸叠?

  1. 划分:将所有工作表展开,这样每个“堆栈”中只有一张工作表。
  2. 征服:
    1. 四处走动,将每张纸放在另一张纸上。您现在有2叠。
    2. 四处走动,将每个2堆栈放在另一个2堆栈的顶部。您现在有4叠。
    3. 四处走动,将每个4堆栈放在另一个4堆栈的顶部。您现在有8叠。
    4. ...不断...
    5. 您现在有一叠1024张纸!

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

来源
King Lee
Translate

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

来源
Vicky Lee
Translate

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

假设您有三位经理-杰克,约翰和摩根。杰克管理着2位程序员,约翰-3位,摩根-5位。您要给每个经理300美元,并想知道这会花多少钱。答案很明显-但是,如果Morgan的2位员工也是经理,该怎么办?

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

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

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

来源
Betty Lee
Translate

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

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

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

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
来源
Roy Lee
Translate

任何算法都表现出结构的数据类型上的递归,如果基本上由一个开关语句组成,则该数据类型的每种情况都具有一种情况。

例如,当您处理一种类型时

  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

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

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

 integer = 0 | succ(integer)

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

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

众所周知的阶乘函数就是这种形式最简单的例子。

来源
Shirley Lee
Translate

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

来源