Per risolvere algoritmicamente un problema, si dispone di diversi tipi di ciclo (loop in inglese): «Per» (for in inglese), «Finché» (while), «Ripeti fino a quando» (repeat until). Purtroppo, queste diverse strutture non sono sempre così facili da mettere in pratica. La condizione di uscita dal ciclo dipende spesso da parametri modificati durante l’esecuzione; dimostrare che finirà per essere vera non è semplice. Per gli appassionati della programmazione funzionale, la questione non si pone nemmeno: rifiutano i cicli; se non si usano variabili, perché mai iterare?
Il rimedio a tutti questi mali è la ricorsione.
Un algoritmo è ricorsivo se chiama sé stesso. Attenzione: non tutti i linguaggi informatici lo consentono. L’esempio classico di ricorsione è il calcolo del fattoriale: il fattoriale di un numero intero n (indicato con n!) è uguale a n moltiplicato per il fattoriale di n – 1. Poiché bisogna pur fermarsi a un certo punto, si pone il fattoriale di 1 uguale a 1. Da questo esempio si vede che, nello scrivere una procedura ricorsiva, occorre rispettare due regole: serve una condizione di terminazione (qui n = 1) e bisogna riapplicare la procedura a un «insieme strettamente più piccolo» (qui n – 1 è effettivamente strettamente minore di n). Per essere del tutto concreti, ecco lo pseudocodice della nostra procedura.
Eseguiamo l’algoritmo per n = 3.
