2

我很好奇递归在 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

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

4

2 回答 2

3

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

fib.fibo("start",3)

被调用，打印“开始：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)与上述相同的方式进行评估。

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

于 2012-05-26T19:29:17.133 回答
1

有什么问题？您在运行此代码时从左到右和从右到左更改（left1 内部有 right2）：

             start
    left1           right1 
left2  right2    left3  right3

你left1先打电话，然后left2。然后返回 left1，但不打印，然后调用right2. 然后返回两次，您start再次进入。之后你打电话right1，这将是类比。

所以你有：开始 - 左1 - 左2 - 右2 - 右1 - 左3 - 右3

于 2012-05-26T19:29:29.380 回答