在递归斐波那契程序中，为什么左子树在右子树之前被调用（类似于后序遍历）？

Question

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)？

Answer 1

这可以用 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.

在您的例子中，左操作数是对 fib(n-1) 的调用，因此将对其进行全面计算以计算最终值，然后才计算右操作数。

Answer 2

因为执行的第一部分首先被调用，例如，如果您这样做：

void dfs(int x) {
   dfs(x-1);
   dfs(x-2);
}

然后dfs(x-1)会先调用，所以dfs会再调用一次，dfs(x-1)会再调用一次，因为它是第一条指令，以此类推，直到最后一个dfs(x-1 ) 被调用然后程序继续 dfs(x-2).

希望对您有所帮助。

在递归斐波那契程序中，为什么左子树在右子树之前被调用（类似于后序遍历）？

In recursive fibonacci program why the left subtree is called before the right one(something like postorder traversal)?

java

recursion

fibonacci