Ricorsione
La ricorsione è un'importante tecnica di programmazione in base alla quale una funzione chiama se stessa. Un esempio è il calcolo di fattoriali. Il fattoriale di 0 è 1. Il fattoriale di n, un numero intero maggiore di 0, è dato dal prodotto di tutti i numeri interi compresi tra 1 ed n.
Utilizzo di una ricorsione
Il paragrafo seguente corrisponde a una funzione per il calcolo di un fattoriale definita in forma di testo:
"Se il numero è minore di zero, rifiutarlo. Se non è un numero intero, rifiutarlo. Se il numero è zero, il relativo fattoriale è 1. Se il numero è maggiore di zero, moltiplicarlo per il fattoriale del successivo numero più piccolo."
Per calcolare il fattoriale di numeri maggiori di zero, è necessario calcolare il fattoriale di almeno un altro numero. Per poter eseguire la funzione sul numero corrente, è prima necessario che la funzione esegua una chiamata a se stessa per ottenere il successivo numero più piccolo. Questo è un esempio di ricorsione.
La ricorsione e l'iterazione, o ciclo, sono strettamente correlate. Pertanto una funzione può restituire gli stessi risultati sia con la ricorsione che con l'iterazione. In genere un determinato calcolo si presterà a una tecnica o all'altra. È quindi sufficiente scegliere l'approccio più naturale o più congeniale.
Nonostante l'utilità della ricorsione, può accadere che la funzione ricorsiva creata non restituisca un risultato definito e che non sia in grado di raggiungere un endpoint. Tale ricorsione può causare l'esecuzione di un ciclo infinito da parte del computer. È sufficiente, ad esempio, omettere la prima regola, ovvero quella sui numeri negativi, dalla descrizione verbale del calcolo del fattoriale e provare a calcolare il fattoriale di un qualsiasi numero negativo. Questa operazione non riesce perché per calcolare, ad esempio, il fattoriale di -24, è necessario calcolare il fattoriale di -25. Per calcolare il fattoriale di -25, è necessario calcolare il fattoriale di -26 e così via. Questo processo, ovviamente, non raggiunge mai un punto finale.
Un altro problema connesso all'utilizzo della ricorsione è che le funzioni ricorsive sono in grado di utilizzare tutte le risorse disponibili, quali la memoria di sistema e lo spazio dello stack. Ogni volta che una funzione ricorsiva chiama se stessa, o un'altra funzione dalla quale poi è a sua volta chiamata, utilizza determinate risorse. Per quanto le risorse vengano liberate al termine della funzione ricorsiva, una funzione con troppi livelli di ricorsione potrebbe utilizzare tutte le risorse disponibili. Quando si verifica questa eventualità, viene generata un'eccezione.
Pertanto è importante progettare accuratamente le funzioni ricorsive. Se esiste anche la minima possibilità di ricorsione eccessiva o infinita, progettare la funzione in modo che conti il numero di chiamate a se stessa e impostare un limite per il numero di chiamate. Si può fare in modo che, qualora chiami se stessa un numero di volte maggiore di quello definito come limite, la funzione termini automaticamente. Il numero massimo ottimale di iterazioni dipende dalla funzione ricorsiva.
Di seguito è riportata la stessa funzione fattoriale scritta in codice JScript. Mediante un'annotazione di tipo si fa in modo che la funzione accetti solo tipi integer. Se viene passato un numero non valido, vale a dire un numero minore di zero, l'istruzione throw genererà un errore. In caso contrario, verrà utilizzata una funzione ricorsiva per calcolare il fattoriale. La funzione ricorsiva accetta due argomenti, uno per il fattoriale e uno per il contatore che tiene traccia del livello di ricorsione corrente. Se il contatore non raggiunge il livello massimo di ricorsione, verrà restituito il fattoriale del numero originale.
function factorialWork(aNumber : int, recursNumber : int ) : double {
// recursNumber keeps track of the number of iterations so far.
if (aNumber == 0) { // If the number is 0, its factorial is 1.
return 1.;
} else {
if(recursNumber > 100) {
throw("Too many levels of recursion.");
} else { // Otherwise, recurse again.
return (aNumber * factorialWork(aNumber - 1, recursNumber + 1));
}
}
}
function factorial(aNumber : int) : double {
// Use type annotation to only accept numbers coercible to integers.
// double is used for the return type to allow very large numbers to be returned.
if(aNumber < 0) {
throw("Cannot take the factorial of a negative number.");
} else { // Call the recursive function.
return factorialWork(aNumber, 0);
}
}
// Call the factorial function for two values.
print(factorial(5));
print(factorial(80));
L'output del programma è il seguente:
120
7.156945704626378e+118