Java Language Calcul du nombre N ° Fibonacci


Exemple

La méthode suivante calcule le Nième nombre de Fibonacci en utilisant la récursivité.

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

La méthode implémente un cas de base (n <= 2) et un cas récursif (n> 2). Ceci illustre l'utilisation de la récursivité pour calculer une relation récursive.

Cependant, bien que cet exemple soit illustratif, il est également inefficace: chaque instance de la méthode appelle la fonction elle-même deux fois, ce qui entraîne une croissance exponentielle du nombre de fois que la fonction est appelée lorsque N augmente. La fonction ci-dessus est O (2 N ), mais une solution itérative équivalente a la complexité O (N). En outre, il existe une expression "forme fermée" qui peut être évaluée en multiplications à virgule flottante O (N).