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（2 ^N），但是等效的迭代解决方案很复杂O(N)。此外，还有一个“封闭形式”表达式，可以在O(N)浮点乘法中求值。