为什么以下递归程序会给出以下输出

Question

我试图从头开始理解 java 递归。我通过以下示例

public static void main(String[] args) {
  threeWays(1,4);
}

public static void threeWays(int id,int n) {
  if (n >= 0) {
    System.out.println(id + "=" + n);
    threeWays(id+1,n-1);
    threeWays(id+1,n-2);
  }
}

给出输出

1=4
2=3
3=2
4=1
5=0
4=0
3=1
4=0
2=2
3=1
4=0
3=0

我理解最多 5=0 但为什么程序运行超出这个范围？为什么 n 变为 -1 后它不停止？ 4=0从何而来？我什至不知道如何称呼这种现象，所以这个问题可能看起来很模糊。任何帮助将不胜感激。

Answer 1

threeWays(id+1,n-1); // when this returns,
threeWays(id+1,n-2); // ... the program still does this

您正在递归调用函数两次。因此，在第一次调用结束后，它稍微展开堆栈，然后进入第二次递归。

从第二次调用开始，它在每一层再次分支两次。

如果这令人困惑，可以在调试器中单步执行程序来说明。您可以在那里看到调用堆栈中的每个帧，包括局部变量以及它们现在所在的代码行。

为什么以下递归程序会给出以下输出

Why does the following recursive program give the following output

java

recursion

tail-recursion