Funzioni ricorsive con JavaScript

11 Ott

Out Of Date Warning

Questo post è stato pubblicato più di 2 anni fa (il 11 ottobre 2011). Le idee vanno avanti velocemente, le prospettive cambiano quindi i contenuti potrebbero non essere aggiornati. Ti prego di tenere in considerazione questo, e di verificare le informazioni tecniche presenti nell'articolo prima di farne affidamento per i tuoi scopi.

Per ricorsione si intende semplicemente il richiamare una funzione all’interno della definizione di se stessa, o in altre parole, una funzione è definita ricorsivamente quando nella sua definizione appare un riferimento
(chiamata) a se stessa. Ad ogni richiamo aumenta la "profondità" dell’elaborazione fino al raggiungimento dello scopo, momento in cui la funzione ritorna.

Molti linguaggi di programmazione offrono la possibilità di definire funzioni o procedure ricorsive; JavaScript naturalmente è uno di questi. Facciamo un esempio tanto per schiarirci le idee,  vediamo una banale funzione (non ricorsiva) per il calcolo della somma di due numeri:

Vediamo ora lo stesso esempio attraverso una funzione ricorsiva:

Questo semplice esempio mostra chiaramente cosa si intende per funzione ricorsiva, in pratica il parametro b viene usato come variabile di controllo per stabilire quando la funzione deve ritornare, ad ogni chiamata di se stessa il parametro b viene diminuito ed il parametro a aumentato di una unità.

Ricorsione tra funzioni anomime

Ma cosa succede quando utilizziamo delle funzioni anonime? Come facciamo a richiamare la funzione all’interno di se stessa? La possibilità di usare funzioni anonime in JavaScript è un’arma fondamentale per la scrittura di codice intelligente, l’utilizzo di tale tipo di funzione è  molto comune oltre che dannatamente comodo, pensiamo alla dichiarazione di una nuova funzione come attributo di una chiamata di funzione o assegnata come proprietà di un’altro oggetto (non dimentichiamoci che lo funzioni in JavaScript sono oggetti di prima classe).
Rivediamo il nostro esempio di funzione somma, questo volta utilizzando una funzione anonima (non ricorsiva), assegnata alla proprietà di un oggetto:

E se volessimo utilizzare la ricorsione? Una tecnica potrebbe essere quella di usare il contesto di funzione (this), oppure un’altra soluzione potrebbe essere quella di dare un nome alle funzioni anonime. Questo potrebbe sembrare a prima vista piuttosto contraddittorio, ma funziona bene. Consideriamo questo esempio:

Tuttavia la soluzione più naturale è sicuramente un’altra e cioè sfruttare la proprietà callee dell’oggetto arguments.
Per chi non lo sapesse l’oggetto arguments è una sorta di array definito soltanto nel corpo di una funzione. Gli elementi dell’array rappresentano gli argomenti della funzione, l’elemento 0 è il primo argomento, l’elemento 1 il secondo argomento e così via. Tutti i valori passati come argomenti diventano elementi di questo speciale array, la cui proprietà lenght rappresenta il numero degli argomenti.
Tornando alla proprietà callee essa si riferisce alla funzione che è attualmente in esecuzione. Permette quindi ad una funzione anonima di riferirsi a se stessa.
Essendo una proprietà dell’oggetto arguments, è definita soltanto nel corpo di una funzione.
Con questa conoscenza in mano, ecco che utilizzare la ricorsione all’interno delle funzioni anonime diventa un gioco da ragazzi:

Conclusioni

Gli algoritmi ricorsivi sono spesso molto comodi e veloci da scrivere, facendoci risparmiare una certa quantità di codice e rendendo semplici compiti apparentemente complessi (non lo è il nostro esempio, che è stato posto solo a fini didattici), tuttavia c’è sempre un prezzo da pagare. La ricorsione tende a sfruttare una grande quantità di memoria (ogni volta che una funzione chiama se stessa occorre allocare memoria per lo script).
Bisogna essere consci di questo e nel caso ricorrere a forme di programmazione più sicure.

Lascia un commento