Dav*_*vid 1 java recursion memoization dynamic-programming
当返回命令有两个递归调用（例如 ）时
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 个斐波那契数的方法。
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)
然后fib(n-2)将首先被调用，这将通过 完成所有备忘录值n-2。然后，对 的调用fib(n-1)将使用现有的记忆值来“完成工作”，即通过 完成所有值fib(n-1)。
无论哪种方式，在计算这些表达式之后，所有值n-1都会被记忆，（最坏情况）时间复杂度（和空间复杂度）为 O(n)。也可能这是调用 的结果fib(n)，这会另外记住 的值n。