Java计算第N个斐波那契数
示例
以下方法使用递归计算第N个斐波那契数。
public int fib(final int n) {
if (n > 2) {
return fib(n - 2) + fib(n - 1);
}
return 1;
}该方法实现了基本情况（n<=2）和递归情况（n>2）。这说明了使用递归计算递归关系。
但是，尽管此示例是说明性的，但效率也不高：该方法的每个单个实例将调用函数本身两次，从而导致随着N的增加，函数被调用的次数呈指数增长。上面的函数是O（2N），但是等效的迭代解决方案很复杂O(N)。此外，还有一个“封闭形式”表达式，可以在O(N)浮点乘法中求值。