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

Question

什么是递归，什么时候应该使用它？似乎经常出现在邮件列表和在线讨论中的一个主题是，攻读计算机科学学位的优点(或不足)。一个似乎一次又一次出现在否定方的论点是，他们已经编码了一些年，而且从来没有使用过递归。所以问题是：什么是递归？我什么时候使用递归？为什么人们不使用递归呢？

Answer 1

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

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

1. 空间被雕刻在

   堆栈

   函数的参数和局部变量
2. 函数的参数被复制到这个新空间
3. 控件跳转到函数。

4. 函数的代码运行

5. 函数的结果被复制到返回值中
6. 堆栈被重绕到以前的位置。
7. 控件跳回调用函数的位置。

执行所有这些步骤都需要时间，通常比遍历循环所需的时间稍长一些。然而，真正的问题在于步骤1。当许多程序启动时，它们为堆栈分配一小块内存，当它们耗尽内存时(通常，但并不总是由于递归)，程序会因为堆栈溢出.

因此，在这些语言中，递归更慢，它使您容易崩溃。尽管如此，仍然有一些关于使用它的争论。一般来说，递归编写的代码一旦知道如何读取，就会更短、更优雅。

语言实现者可以使用一种叫做尾叫优化可以消除某些类型的堆栈溢出。简单地说：如果一个函数的返回表达式只是函数调用的结果，那么您不需要在堆栈中添加一个新的级别，您可以为被调用的函数重用当前的级别。遗憾的是，很少有命令式语言实现内置了尾叫优化。

* 我喜欢递归。我最喜欢的静态语言根本不使用循环，递归是重复执行某些事情的唯一方法。我只是不认为递归在没有调优的语言中是个好主意。

*顺便说一句，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循环来完成，但作为概念的说明很有用)