Un algoritmo è ricorsivo quando utilizza delle procedure ricorsive, cioè che al loro interno richiamano se stesse.

Le procedure ricorsive devono soddisfare delle condizioni che garantiscano la fine del procedimento:

• ogni chiamata successiva della procedura deve applicarsi ad un sottoinsieme dei dati di quella precedente o a valori minori;

• deve essere definita una condizione di terminazione delle ripetizioni (o di uscita), chiamata base della ricorsione.

Quando viene raggiunta la base della ricorsione vengono effettuati a ritroso tutti i calcoli rimasti in sospeso.

Una struttura ricorsiva può sempre essere descritta con un procedimento iterativo (che utilizza le strutture di controllo cicliche).

La ricorsione può essere semplice, se una procedura richiama se stessa direttamente, o indiretta (o mutua) se la procedura richiama un’altra procedura che a sua volta richiama la prima.