-2

虽然众所周知递归是“一种调用自身的方法”，但我倾向于想知道实际发生了什么。以经典的阶乘示例：

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

事实（5）；

我知道它有点像这样：（等号表示为该值调用函数时发生的情况）

http://postimg.org/image/4yjalakcb/

为什么递归会这样？计算机的哪个方面使它像这样通过自身向后工作？幕后发生了什么？

作为一名学生，我觉得我们所学的递归是肤浅而笼统的。我希望这里的优秀社区能够帮助我在机器本身的层面上理解它。谢谢！

4

4 回答 4

7

以下是调用方法时发生的情况的简要概述：

  • 该方法的框架是从堆栈中分配的。
  • 框架包含方法的所有局部变量、参数、返回值。
  • 该框架放置在调用此方法的当前方法的框架的顶部。
  • 当方法返回时，与该方法相关的帧从堆栈中弹出，调用方法返回操作，并从前一个方法中获取返回值（如果有）。

您可以在此处了解有关框架的更多信息 - JVM Spec-Frames。

在递归的情况下，也会发生同样的事情。暂时忘记您正在处理递归，并将每个递归调用视为对不同方法的调用。因此，factorial以防万一，堆栈会像这样增长：

fact(5)
  5 * fact(4)
    4 * fact(3)
      3 * fact(2)
        2 * fact(1) 
          1 * fact(0)  // Base case reached. Stack starts unwinding.
        2 * 1 * 1
      3 * 2 * 1 * 1
    4 * 3 * 2 * 1 * 1
  5 * 4 * 3 * 2 * 1 * 1  == Final result
于 2013-08-05T21:13:12.577 回答
2

如果您跟踪函数调用，您将看到它是如何工作的。

例如

fact(3)将返回3 * fact(2)。所以java会调用fact(2).

fact(2)将返回2 * fact(1)。所以java会调用fact(1).

fact(1)将返回1 * fact(0)。所以java会调用fact(0).

fact(0)将返回1。

然后fact(1)会返回1 * 1 = 1。

然后fact(2)会返回2 * 1 = 2。

然后fact(3)会返回3 * 2 = 6。

Java 调用递归方法就像调用任何其他方法一样。

于 2013-08-05T21:11:13.680 回答
0

您可能听说过一种叫做“堆栈” 的东西，它用于存储方法状态。

我相信它还存储调用行，以便函数可以返回到它的调用者

所以假设你调用了一个递归函数

 - int $input = 5
 - stack.Push L
 - GOTO FOO
 - Label L

您的递归函数（没有基本情况）可能类似于以下内容

 - Label FOO
 - int in = $input 
 - input = in - 1
 - stack.Push in
 - stack.Push L2
 - goto FOO
 - Label L2
 - in = stack.Pop in
 - output *= in
 - goto stack.POP
于 2013-08-05T21:22:29.333 回答
0

也许以下内容可以帮助您理解。计算机并不关心他是否调用了它只是计算的相同函数。一旦你理解了递归是什么以及为什么它适用于许多事物，比如列表、自然数等，这些事物本身就是按结构递归的，就没有什么神奇的了。

  1. 定义：0的阶乘是1
  2. 定义：大于 0 的数 n 的阶乘是该数与其前一个数的阶乘的乘积。

因此

5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 5*4*3*2*1*1 = 120

所以，如果你听说过归纳证明，它是这样的：

  1. 我们为基本案例证明了一些属性。
  2. 我们证明，如果属性对 n 为真，那么它对 n 的后继也为真。
  3. 我们得出结论，这是该属性适用于基本情况和所有后续情况的证明。

示例：通过归纳证明偶数的平方是 4 的倍数！

  1. 0的平方是0，是4的倍数。
  2. 设 n 为偶数，其平方 n² 是 4 的倍数。则(2+n)*(2+n)= 4+2n+2n+n²。这是 4 的倍数，因为 n² 根据我们的假设，4 是 1，2n+2n = 4n也是 4 的倍数，而 4 的倍数之和根据分配律是 4 的倍数：4a + 4b = 4(a+b)
  3. QED 该属性适用于 0（我们的基本情况）和 (2+n)，前提是它适用于 n。因此它适用于 2、4、6、8 .... 和所有其他偶数。

（更简单的证明是观察(2a)²= 4*a*a，它是 4 的倍数。）

编写递归程序与通过归纳进行证明非常相似：

  1. 我们为基本情况编写计算。
  2. 对于非基本情况，我们知道如何计算结果（例如，我们知道n! = n * (n-1)!，所以我们把它写下来，因为我们需要的函数就是我们刚刚写的那个！
  3. 我们可以得出结论，我们的程序将为基本情况和基本情况的任何后继计算正确的值。如果678!仍然没有计算出正确的答案，那么它与我们使用的数据类型int不太适合大数字的事实有关（或者，换句话说，计算所有 moulo 2^32）并且在此外，软件坚持将可用数字的一半解释为负数。

这样做的原因与计算机硬件或编程语言无关：正如我之前所说，它是手头项目（列表、树、集合、自然数）的递归结构的结果。

新手常犯的错误是忽略基本情况并迷失在复杂性中。我总是建议从基本情况开始，一旦你有了这个，你可以假设这个函数存在，并且可以在更复杂的情况下使用它。

于 2013-08-05T22:24:57.770 回答