java - 递归方法的调用顺序

Question

我很好奇递归在 jvm 中是如何工作的。请遵循示例。首先计算给定数字的阶乘。

public class Factorial {

public int factorial(int n) {
    System.out.println("Factorial: " + n);
    if ( n < 2) {
        return 1;
    } 

    return n * factorial(n - 1);
}

执行以下测试

    @Test
public void test_factorial() {
    Factorial fact = new Factorial();
    System.out.println(fact.factorial(3));
}

显示

3
2
1

很明显，方法调用被放入堆栈中，执行到 n == 1 然后返回。 现在，我尝试计算斐波那契数。

public int fibo(String name, int n) {
    System.out.println("fibo: " + name +  " " + n);
    if (n < 2 ) {
        return n;
    }
    return fibo ("left", n - 1) + fibo ("right", n - 2);
}

执行测试

@Test
public void test_fibonacci() {
    Fibo fibo = new Fibo();

    assertEquals(8, fibo.fibo("start",6));

}

打印下面的内容

fibo: start 6
fibo: left 5
fibo: left 4
fibo: left 3
fibo: left 2
fibo: left 1
fibo: right 0
fibo: right 1
fibo: right 2
fibo: left 1
fibo: right 0
fibo: right 3
fibo: left 2
fibo: left 1
fibo: right 0
fibo: right 1
fibo: right 4
fibo: left 3
fibo: left 2
fibo: left 1
fibo: right 0
fibo: right 1
fibo: right 2
fibo: left 1
fibo: right 0

我的问题是这个例子中调用方法并将其放入堆栈的规则是什么？

Answer 1

在 Java 中，语句是从左到右计算的。以下是较小输入上斐波那契函数的简单分割:

fib.fibo("start",3)

被调用，打印“start: 3”。它尝试评估

(1) fibo("left", 2) + fibo("right", 1)

由于评估是 LTR，这意味着

(2) fibo("left", 2)

首先进行评估。我们创建一个新的堆栈帧，语句 (1) 正在等待它的返回。调用 (2) 打印“left: 2”并尝试评估

(3) fibo("left", 1) + fibo("right", 0)

再说一次，LTR 评估意味着我们评估

(4) fibo("left", 1)

首先。同样，新的堆栈帧 (3) 等待 (4) 的响应。调用 (4) 打印“left: 1”并返回 1。堆栈帧弹出，(3) 现在继续其计算，调用

(5) fibo("right", 0)

这会打印“right: 0”并返回 0。(2) 现在能够完成其计算并返回 1+0 = 1。语句 (1) 最终完成计算 fibo("left", 2 ) 并且可以继续以与上面相同的方式评估 fibo("right",1)。

我希望这有助于一些人澄清!