递归调用中的执行顺序

Question

当返回命令有两个递归调用时，例如 return fib(n-1) + fib(n-2);，这两个调用是同时执行的，还是fib(n-1)先执行的fib(n-2)？fib(n-1)通过使用记忆化，时间复杂度降低到 O(n)，但是只有在执行之前fib(n-2)（然后使用存储的值）才有可能吗？*public int fib(int n)是一种使用递归计算第 N 个斐波那契数的方法。

Answer 1

Java保证表达式中子表达式的求值顺序是从左到右。

Java 编程语言保证运算符的操作数以特定的求值顺序出现，即从左到右。

这意味着fib(n-1)将在 之前进行评估fib(n-2)。

但是评估顺序并没有改变这里记忆的复杂性，无论哪种方式它仍然是 O(n) 。当 Java 评估它时，fib(n-1)将通过 完成所有备忘录值n-1，包括 的值fib(n-2)。调用fib(n-2)不做任何工作；它只是引用已经计算出的值fib(n-1)。

如果您颠倒了代码中的顺序：

fib(n-2) + fib(n-1)

Thenfib(n-2)将首先被调用，这将通过 完成所有备忘录值n-2。然后调用fib(n-1)将使用现有的记忆值来“完成工作”，通过 完成所有值fib(n-1)。

无论哪种方式，在评估这些表达式之后，所有通过的值都n-1被记忆，具有 O(n) 的（最坏情况）时间复杂度（和空间复杂度）。也可能这是调用的结果fib(n)，它会额外记住 的值n。