什么是递归,什么时候应该使用它？

Question

在邮件列表和在线讨论中经常出现的主题之一是进行计算机科学学位的优点(或缺乏).似乎一次又一次地为负面派对提出的论点是,他们已编码了若干年,他们从未使用过递归.

所以问题是:

1. 什么是递归？
2. 我什么时候使用递归？
3. 为什么人们不使用递归？

Answer 1

这个帖子中有许多关于递归的好解释,这个答案是为什么你不应该在大多数语言中使用它.*在大多数主要命令式语言实现中(即C,C++,Basic,Python的每个主要实现) ,Ruby,Java和C#)迭代比递归更受欢迎.

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

1. 在函数的参数和局部变量的堆栈上刻出了空格
2. 函数的参数被复制到这个新空间中
3. 控制跳转到该功能
4. 函数的代码运行
5. 函数的结果被复制到返回值中
6. 堆栈重绕到其先前的位置
7. 控制跳回到调用函数的位置

完成所有这些步骤需要花费时间,通常比迭代循环所花费的时间多一些.但是,真正的问题在于步骤#1.当许多程序启动时,它们为它们的堆栈分配一块内存,当它们耗尽该内存时(通常但不总是由于递归),程序因堆栈溢出而崩溃.

因此,在这些语言中,递归速度较慢,并且使您容易崩溃.尽管如此,仍然有一些使用它的论据.一般来说,一旦你知道如何阅读它,递归编写的代码就会更短,更优雅.

语言实现者可以使用一种称为尾调用优化的技术,它可以消除某些类的堆栈溢出.简洁地说:如果函数的返回表达式只是函数调用的结果,那么您不需要在堆栈中添加新的级别,您可以将当前的级别重用于被调用的函数.遗憾的是,很少有命令式语言实现内置了尾部调用优化.

*我喜欢递归. 我最喜欢的静态语言根本不使用循环,递归是重复执行某些操作的唯一方法.我不认为递归通常是一种不适合它的语言的好主意.

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

Answer 2

递归的简单英语示例.

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.

Answer 3

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

struct Node {
    Node* next;
};

并且您想知道链接列表可以使用递归执行此操作的时间长度:

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

(这当然可以用for循环来完成,但是作为概念的说明是有用的)

Answer 4

每当一个函数调用自身,创建一个循环,然后就是递归.与任何东西一样,有很好的用途和递归的不良用途.

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

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

然而,这是一个蹩脚,几乎毫无意义的例子,因为它可以很容易地被更高效的迭代所取代.毕竟,递归会受到函数调用开销的影响,在上面的示例中,与函数本身内部的操作相比,这可能是实质性的.

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

您可以使用递归简单地绘制其中一个,其中调用堆栈在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);
    }
}

如果您尝试使用迭代执行相同的操作,我认为您会发现需要更多代码才能完成.

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

结论

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

Answer 5

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

规范示例是生成n阶段的例程.通过将1和n之间的所有数相乘来计算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))));

当基本案例被触发时,最终替换发生.在这一点上,我们有一个简单的算法公式来解决,它首先等同于Factorials的定义.

值得注意的是,对方法的每次调用都会导致触发基本情况或调用相同方法,其中参数更接近基本情况(通常称为递归调用).如果不是这种情况,那么该方法将永远运行.

Answer 6

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

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

    return n * Factorial(n - 1);
}

Answer 7

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

例如,要计算数字的阶乘X,可以将其表示为X times the factorial of X-1.因此,该方法"递归"以找到因子X-1,然后将得到的任何东西相乘X以给出最终答案.当然,要找到阶乘X-1,它将首先计算阶乘X-2,等等.当基础案例将X是0或1,在这种情况下,它知道返回1自从0! = 1! = 1.

Answer 8

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

在数学中,两个或多个非零整数的最大公约数(gcd)是最大的正整数,它将数字除以没有余数.

gcd的定义非常简单:

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

在英语中,这个定义表示任何数字的最大公约数和0是该数字,并且两个数m和n的最大公约数是n的最大公约数和m除以n后的余数.

如果您想知道为什么会这样,请参阅有关欧几里德算法的维基百科文章.

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

1. gcd(10,8)
2. gcd(10,10 mod 8)
3. gcd(8,2)
4. gcd(8,8模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.递归案例减少了问题,以便得到简单的答案.

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

Answer 9

1. 一个自称的函数
2. 当一个函数可以(轻松)分解为一个简单的操作加上相同功能的一些较小部分的问题.我应该说,相反,这使它成为递归的一个很好的候选者.
3. 他们是这样!

典型的例子是看起来像的阶乘:

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

  return a*fact(a-1);
}

一般来说,递归不一定很快(函数调用开销往往很高,因为递归函数往往很小,见上文)并且可能遇到一些问题(堆栈溢出任何人？).有人说他们往往很难在非平凡的情况下"正确",但我并没有真正接受这一点.在某些情况下,递归最有意义,是编写特定函数的最优雅和最清晰的方式.值得注意的是,有些语言更倾向于使用递归解决方案并对其进行更优化(LISP会浮现在脑海中).

Answer 10

递归函数是一个自我调用的函数.我发现使用它的最常见原因是遍历树结构.例如,如果我有一个带复选框的TreeView(想想安装一个新程序,"选择要安装的功能"页面),我可能想要一个"全部检查"按钮,就像这样(伪代码):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

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

你需要对递归有点小心.如果进入无限递归循环,您将获得Stack Overflow异常:)

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

我认为,因为这是一种有趣的技术,一些编码员可能最终会比他们应该更频繁地使用它,没有真正的理由.这在某些圈子中给递归一个坏名字.

Answer 11

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

考虑递归首字母缩略词作为一个简单的例子:

• GNU代表GNU的非Unix
• PHP代表PHP:Hypertext Preprocessor
• YAML代表YAML不是标记语言
• 葡萄酒代表葡萄酒不是模仿者
• VISA代表Visa国际服务协会

维基百科上有更多例子