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.