計算第 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) 浮點乘法中進行求值。