什么是递归？

Question

可能是重复问题：
递归函数的例子

我一直在研究编程中递归的概念（尽管我特别研究Java），以下是我最好理解的内容：

比如，现实生活中，当我们把两个镜子放在一起时，它们之间产生的图像就是递归的。

但我不明白编程中的这个算法？ 请给我一个简单的例子来理解递归？

- Ralph

---

请参阅https://dev59.com/62vXa4cB1Zd3GeqPJ4SM。 - CodingBarfield

https://www.google.com/search?q=recursion - mauris

递归编程（不管它是什么）很可能是基于递归编程的。 - user381105

好的，CodingBarfield和Oded。很有趣。但是你们的递归没有终止，所以在形式上是不正确的。认真点，让我们帮助原始发布者。 - O. Jones

@OllieJones - 你的回答在哪里？ - Oded

Answer 1

递归是一种编程技术，其中一个方法可以在计算过程中调用自身（有时可能会有多个方法 - 这些方法通常会相互循环调用）。

一个流行的例子是计算斐波那契数列：

public static long fib(int n) {
    if (n <= 1) return n;
    else return fib(n-1) + fib(n-2);
}

两个基本组成部分是基本情况（例如示例中的n<=1）和递归情况。

在创建递归算法时，您需要考虑基本情况以及如何使用递归情况来达到基本情况（否则会出现无限递归并使堆栈崩溃）。

- Oded

---

但是不良的使用习惯可能会导致 StackOverFlowError :-) - Luis Pena

Answer 2

基本上，当一个函数满足以下两点时，它就是递归的：

1. 函数有一个简单的基本情况（base case），而且
2. 所有其他情况都有规则，可以缩小到基本情况。

例如，计算阶乘：

public static long factorial(int i)
{
    // This is the base case
    if(i == 0)
    {
         return 1;
    }
    else
    {
        // This reduces the problem to something closer to the base case
        return i * factorial(i - 1);
    }
}

- Chris Forrence

---

递归函数严格来说不需要有基本情况。在许多语言中（例如Lisp），无限递归是实现无限循环的常见（有时是唯一）技术。当然，无限循环对于大多数具有不确定运行时间的实际程序（例如服务器）非常有用。 - slebetman

我认为这个问题是基本级别的递归，所以我假设线性递归。 - Chris Forrence

@slebetman，我不认为繁忙等待对于大多数具有不确定运行时间的实际程序（例如服务器）是“有用的”。 - Puce

@GlaciesofPacis 你在例子中忽略了递归... - Puce

@Puce：无限循环并不等同于忙等待。所有实际的服务器都是使用无限循环和阻塞函数编写的（无论是I/O还是像socket或poll这样的多路复用函数）。唯一的例外是在具有隐式事件循环的语言中，例如Tcl和JavaScript。但在这种情况下，你仍然需要在解释器级别实现无限事件循环。 - slebetman

Answer 3

有些计算问题可以这样描述，即将问题分解成更小的子问题。使用与主问题相同的方法来解决更小的子问题。如果较小的子问题只是大问题的一个较小案例，则可以进一步分解。

最终，问题变得很小，可以在不进一步分解的情况下解决。这被称为基本情况。通过解决基本情况，您可以构建解决更大问题的解决方案。

假设您想要找到a^b，其中a和b是正整数。您可以看出，这与a * a^(b-1)相同。也就是说，a^(b-1)是原始问题的一个较小问题，但仍需要使用与原始问题相同的技术来解决。要解决a^(b-1)，您可以看到它是a * a^(b-2)。

等等。

最终，你会得到a * a * a * ... * a^(b-b)。而且我们知道b-b = 0，a⁰ = 1。因此，我们不必计算最后一位，因为我们已经知道答案。最终，a^b = a * a * a * ... * 1。

所以2⁴ = 2 * 2³ = 2 * 2 * 2² = 2 * 2 * 2 * 2¹ = 2 * 2 * 2 * 2 * 2⁰ = 2 * 2 * 2 * 2 * 1。

要编写此程序，您首先处理基本情况，然后使用递归来处理其他所有内容。

   pow(a, b){
       if(b == 0){
          return 1;
       }else{

          return a * pow(a, b - 1);
       }
   }

需要注意的是，这只是递归的基本概念。你在各种答案中看到的斐波那契数列问题等示例非常低效。你可以使用动态规划技术构建更高效的程序，其中递归是解决问题的机制之一。

- Vincent Ramdhanie

Answer 4

递归编程是一种基于数学归纳法思想的技术，其中方法或函数重复调用自身。因此，可以按以下方式实现阶乘函数：

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

    return n * fact(n-1);
}

请注意，为了确保递归终止，你应该处理一个基本情况，即对于某些已知的简单输入，你应该有一个定义好的常量输出，而且你应该确保在每次迭代中使函数的参数更简单（在上面的例子中通过将 n 减 1）。

- Edd

Answer 5

递归

一个方法可以调用自身，这就是递归。经常使用方法的递归实现，因为它们会导致紧凑优雅的代码，比不使用递归的相应实现更容易理解。

递归编程技巧知道三个重要的规则（经验）：

1. 基本情况：递归有一个基本情况。始终第一条语句是条件性的，并且有一个“返回”。
2. 子问题：递归调用解决某种意义上较小的子问题，使其收敛于基本情况。
3. 无重叠：递归调用不应处理重叠的子问题。

从性能的角度来看，非递归解决方案更快，通常需要更少的内存。（例如二分查找）
但是，有些任务如此复杂，只有递归解决方案才能得到（更或多或少可理解的）代码。

递归二分查找的示例：

public static int binSearch(int[] a, int key) {
   return binSearch0(a, key, 0, a.length - 1);
}

public static int binSearch0(int[] a, int key, int from, int to) {
    if (from > to) return -1;
    // looks strange but (from + to) / 2 can oveflow
    // (java bug which was active more than 10 years)
    int mid = from + (to - from) / 2;
    if (key < a[mid]) 
        return binSearch0(a, key, from, mid - 1);
    else if (key < a[mid]) 
        return binSearch0(a, key, mid + 1, to);
    else return mid;
 }

在这个例子中，您可以看到所有三个规则（基本、子、非重叠）。请注意，递归函数通常有一个起始函数，在这个例子中是“binSearch”，而“binSearch0”是递归函数。

- AlexWien

Answer 6

非常简单的“递归”代码。

处理列表的顶部项目。从列表中删除它并调用处理列表顶部项目的代码。

树根具有一定长度，并在每2/3个根处分裂成单独的根。分裂的块再次在每2/3个根处分裂成单独的根。分裂块的分裂块再次分裂..等等。

- CodingBarfield