计算第 N 个斐波纳契数

以下方法使用递归计算第 N 个 Fibonacci 数。

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) 浮点乘法中进行求值。