在递归斐波纳契程序中，为什么左子树在右子树之前被调用（类似于后序遍历）？(In recursive fibonacci program why the left subtree is called b

在递归斐波纳契程序中，为什么左子树在右子树之前被调用（类似于后序遍历）？(In recursive fibonacci program why the left subtree is called before the right one(something like postorder traversal)?) package fibonacci; public class Fib { static int fib(int n) { System.out.println("fib(" + n + ") called"); if(n<=1) { return n; } int temp = fib(n-1) + fib(n-2); System.out.println("returning to fib(" + n +")" ); return temp; } public static void main(String[] args) { System.out.println("fib(5): " + fib(5)); } }

---

输出：

fib（5）叫 fib（4）叫 fib（3）叫 fib（2）叫 fib（1）叫 fib（0）叫 回到fib（2） fib（1）叫 回到fib（3） fib（2）叫 fib（1）叫 fib（0）叫 回到fib（2） 回到fib（4） fib（3）叫 fib（2）叫 fib（1）叫 fib（0）叫 回到fib（2） fib（1）叫 回到fib（3） 回到fib（5） fib（5）：5

PS：为什么在fib（n-2）之前调用fib（n-1）？

package fibonacci; public class Fib { static int fib(int n) { System.out.println("fib(" + n + ") called"); if(n<=1) { return n; } int temp = fib(n-1) + fib(n-2); System.out.println("returning to fib(" + n +")" ); return temp; } public static void main(String[] args) { System.out.println("fib(5): " + fib(5)); } }

---

Output:

fib(5) called fib(4) called fib(3) called fib(2) called fib(1) called fib(0) called returning to fib(2) fib(1) called returning to fib(3) fib(2) called fib(1) called fib(0) called returning to fib(2) returning to fib(4) fib(3) called fib(2) called fib(1) called fib(0) called returning to fib(2) fib(1) called returning to fib(3) returning to fib(5) fib(5): 5

PS: Why fib(n-1) is called before fib(n-2)?

最满意答案

这可以通过以下JLS部分来解释 -

Java编程语言保证运算符的操作数似乎以特定的评估顺序进行评估，即从左到右。

在您的情况下，左操作数是对fib(n-1)的调用，因此将对其进行全面计算以计算最终值，然后才会评估正确的操作。

This can be explained by the following section of JLS -

The Java programming language guarantees that the operands of operators appear to be evaluated in a specific evaluation order, namely, from left to right.

In your case, the left operand is the call to fib(n-1), so it will be fully evaluated to compute final value, and only then the right operation will be evaluated.