递归：幕后花絮 [英] Recursion: Behind the Scenes

问题描述

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

While it is common knowledge that recursion is "a method that calls itself", I am inclined to wonder what is actually happening. Take the classic factorial example:

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

事实（5）;

我知道它有点像这样:(等号表示在为该值调用函数时发生了什么）

I understand that it goes a little something like this: (the equals sign indicates what's happening when the function is called for that value)

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

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

Why does recursion function like this? Which aspect of a computer makes it work through itself backwards like so? What's going on behind the scenes?

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

As a student I feel like the recursion we are taught is shallow and general. I want the excellent community here to help me understand it on the level of the machine itself. Thank you!

推荐答案

以下是每次调用方法时会发生什么的简要概述：

Here's is the brief overview of what happens, whenever you call a method:

• 该方法的框架是从堆栈中分配的。


• 框架包含所有局部变量，参数，返回值


• 该框架放在当前方法框架的顶部，调用此方法。


• 当方法返回时，与该方法相关的框架从堆栈弹出，调用方法恢复运行，从上一个方法获取返回值。

• A frame for that method is allocated from the stack.
• The frame contains, all the local variables, parameters, return values of the method.
• That frame is placed over the top of the frame of current method, that invokes this method.
• When the method returns, the frame related to that method is popped off the stack, and the calling method comes back into action, taking the return value if any from the previous method.

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

You can learn more about frames here - JVM Spec - Frames.

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

In case of recursion, same thing happens. Just for the time being, forget that you are dealing with recursion, and take each recursion call as a call to different method. So, in factorial case, the stack would grow like this:

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

这篇关于递归：幕后花絮的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！