Java Language Calcolo del numero dell'N ° Fibonacci


Esempio

Il seguente metodo calcola il numero Nth Fibonacci usando la ricorsione.

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

Il metodo implementa un caso base (n <= 2) e un caso ricorsivo (n> 2). Questo illustra l'uso della ricorsione per calcolare una relazione ricorsiva.

Tuttavia, sebbene questo esempio sia illustrativo, è anche inefficiente: ogni singola istanza del metodo chiamerà la funzione stessa due volte, portando ad una crescita esponenziale nel numero di volte in cui la funzione viene chiamata con l'aumentare di N. La funzione precedente è O (2 N ), ma una soluzione iterativa equivalente ha complessità O (N). Inoltre, esiste un'espressione "forma chiusa" che può essere valutata nelle moltiplicazioni in virgola mobile O (N).