java - Java中的评估顺序

Question

所以我有这个斐波那契数列的代码:

int fibonacci(int i, int[] memo) {
   if (i == 0 || i == 1) return i;

   if (memo[i] == 0) {
      memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
   }

   return(memo[i]);
}

我的问题是:fibonacci(i-1, memo) 总是在 fibonacci(i-2, memo) 之前求值，对吗？

Answer 1

正确，从从左到右。

首先，您将使用左边的参数fibonacci(i - 1, memo) 完全遍历递归，然后，当它再次向上移动递归树时，每次都会计算右边的参数，再次使用完整的递归树。

快速搜索会得到这张说明该过程的图片:

请注意，许多值通常会计算多次。您当前的方法试图通过在数组 memo 中缓存结果来优化这一点。