递归:幕后花絮

Question

虽然众所周知递归是"一种自称的方法",但我倾向于想知道实际发生了什么.以经典的阶乘为例:

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

事实(5);

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

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

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

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

Answer 1

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

• 从堆栈分配该方法的帧.
• 该框架包含所有局部变量,参数,方法的返回值.
• 该帧放在当前方法框架的顶部,调用此方法.
• 当该方法返回时,与该方法相关的帧将从堆栈中弹出,并且调用方法将恢复运行,从前一个方法获取返回值(如果有).

您可以在此处了解有关帧的更多信息 - 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