La successione di Fibonacci in JavaScript

La successione di Fibonacci è una delle sequenze numeriche più famose e affascinanti nel campo della matematica. Ogni numero nella sequenza è la somma dei due numeri che lo precedono. La sequenza inizia con 0 e 1, e da lì procede all'infinito. È una grande esemplificazione di come i pattern matematici si manifestano in natura e viene studiata non solo in matematica, ma anche in informatica, ingegneria, e arte. In questa pagina, discuteremo come generare la successione di Fibonacci in JavaScript.

Introduzione alla successione di Fibonacci

La successione di Fibonacci inizia con i primi due numeri, 0 e 1. I successivi numeri sono calcolati sommando sempre i due numeri precedenti. Quindi, la sequenza inizia come segue:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Questo comportamento continua all'infinito, generando una sequenza che ha applicazioni in matematica, scienze naturali, informatica e molti altri campi.
Matematicamente, la sequenza è definita come: F(n) = F(n - 1) + F(n - 2) con valori iniziali F(0) = 0 e F(1) = 1.

Ci sono diversi modi per implementare la successione di Fibonacci in JavaScript. Discuteremo due approcci principali: iterativo e ricorsivo.

Successione di Fibonacci in JavaScript con metodo iterativo

Il metodo iterativo è più efficiente in quanto evita le chiamate ricorsive e calcola i numeri di Fibonacci in modo sequenziale.

function fibonacciIterativo(n) {
		let numeri = [0, 1];
		for (let i = 2; i <= n; i++) {
			numeri[i] = numeri[i - 1] + numeri[i - 2];
		}
		return numeri[n];
}

console.log(fibonacciIterativo(10)); // Output: 55

Questo approccio è più efficiente e scalabile per numeri grandi poiché calcola i numeri di Fibonacci in modo sequenziale senza duplicare i calcoli.

Metodo ricorsivo per la successione di Fibonacci

Il metodo ricorsivo è il modo più intuitivo di calcolare la successione di Fibonacci, ma può diventare inefficiente per grandi numeri a causa della ricorsione e della duplicazione dei calcoli.

function fibonacciRicorsivo(n) {
	if (n <= 1) {
		return n;
	} else {
		return fibonacciRicorsivo(n - 1) + fibonacciRicorsivo(n - 2);
	}
}

const numeroDesiderato = 10;
const risultatoRicorsivo = fibonacciRicorsivo(numeroDesiderato);
console.log(`Il numero di Fibonacci alla posizione ${numeroDesiderato} è ${risultatoRicorsivo}`);

Questo approccio è facile da capire ma può essere lento per numeri grandi a causa del crescente numero di chiamate ricorsive.

Ottimizzazione con memorizzazione

La memorizzazione è una tecnica per migliorare le prestazioni di funzioni ricorsive, memorizzando i risultati di chiamate di funzione costose e riutilizzando tali risultati in chiamate future. Possiamo applicare la memorizzazione alla funzione ricorsiva di Fibonacci per renderla più efficiente.

function fibonacciRicorsivoConMemo(n, memo = {}) {
	if (n in memo) return memo[n];
	if (n < 2) return n;
	
	memo[n] = fibonacciRicorsivoConMemo(n - 1, memo) + fibonacciRicorsivoConMemo(n - 2, memo);
	return memo[n];
}

console.log(fibonacciRicorsivoConMemo(10)); // Output: 55

Complessità delle varie implementazioni

La differenza di efficienza tra l'approccio iterativo e quello ricorsivo è significativa, soprattutto per numeri grandi. L'approccio iterativo ha una complessità temporale lineare (O(n)), mentre l'approccio ricorsivo semplice ha una complessità esponenziale (O(2n)) senza memorizzazione. Con la memorizzazione, la complessità del metodo ricorsivo si riduce a O(n), rendendolo simile al metodo iterativo, per quanto riguarda l'efficienza.

Stampa della successione di Fibonacci in JavaScript

Spesso, potrebbe essere utile interagire con l'utente per determinare quanti numeri della successione di Fibonacci visualizzare. Questo aggiunge un livello di interattività al programma e consente all'utente di controllare l'output. In JavaScript, possiamo ottenere l'input dell'utente tramite prompt e poi utilizzare questo input per determinare quanti numeri della successione visualizzare.

function stampaFibonacci(lunghezzaSequenza) {
	let primo = 0, secondo = 1, successivo;
	for (let i = 0; i < lunghezzaSequenza; i++) {
		if(i <= 1) {
			successivo = i;
		} else {
			successivo = primo + secondo;
			primo = secondo;
			secondo = successivo;
		}
		console.log(successivo);
	}
}

let lunghezzaSequenza = prompt("Quanti numeri della successione di Fibonacci vuoi visualizzare?");
lunghezzaSequenza = parseInt(lunghezzaSequenza); // Converte l'input in un numero intero

if (!isNaN(lunghezzaSequenza) && lunghezzaSequenza > 0) {
	stampaFibonacci(lunghezzaSequenza);
}