In informatica viene detto algoritmo ricorsivo un algoritmo espresso in termini di se stesso, ovvero in cui l’esecuzione dell’algoritmo su un insieme di dati comporta la semplificazione o suddivisione dell’insieme di dati e l’applicazione dello stesso algoritmo agli insiemi di dati semplificati. – Wikipedia.it

Una procedura ricorsiva è una procedura che direttamente, o indirettamente, richiama se stessa un determinato numero di volte. L’utilizzo di procedure ricorsive facilita il processo costruttivo di un algoritmo, infatti ne consente una rappresentazione più semplice e concisa, permettendo di porre l’accento sulla tecnica adottata per la risoluzione del problema e facilitando la fase di progettazione. Consideriamo ad esempio una funzione scritta in linguaggio C e incaricata del calcolo del fattoriale di un numero.

Ricordiamo che il fattoriale del numero n è dato dalla formula:
n! = \prod_{k=1}^nk = n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot2\cdot1

Ricordiamo anche l’esistenza della convezione:
0! = 1! = 1

Questa convenzione ci è molto utile, perché ci permette di costruire un caso base da usare all’interno della nostra procedura ricorsiva

Procedura calcFatt(n)
begin
  if n = 0
    return 1;
  else
    return (n * calcFatt(n - 1));
end

Una funzione ricorsiva si sviluppa in un caso base (righe 3 e 4) e in un caso ricorsivo (righe 5 e 6).

Osserviamo che la chiamata di una procedura B, da parte di una procedura A consiste essenzialmente in due operazioni:

  1. Passaggio dei parametri da A a B;
  2. Cessione del controllo da parte di A a B, così da permettere l’esecuzione del codice di B. Prima del “passaggio di consegne” viene salvato in memoria il “punto di ritorno di A“, ovvero l’istruzione che deve essere eseguita in A dopo la chiusura di B.

All’interno di B, se B è una procedura ricorsiva, dovrebbero essere previsti i seguenti casi:

  1. Un caso che porta alla terminazione di B e al successivo ritorno di un parametro ad A. Nel nostro esempio questo era il caso “n=0”;
  2. Un caso che porta alla chiamata di una nuova procedura B. Nel nostro esempio era il caso “n>0”.

L’ovvia conseguenza è che l’ultima procedura chiamata è anche la prima a terminare. Per questo motivo viene utilizzata una struttura dati a pila, per mantenere i dati di tutte le chiamate di procedura che non sono ancora state concluse.

Record di attivazione:
Chiamata di calcFatt
Record di attivazione:
Chiamata di calcFatt
Record di attivazione:
Chiamata di main

Nel nostro esempio supponiamo che la procedura main sia in corso d’esecuzione e che ad un certo punto essa richiami la procedura ricorsiva calcFatt. In questo scenario per prima cosa viene posto all’inizio della pila un nuovo “record di attivazione”, che identifica B, tale record contiene:

  • I puntatori ai parametri di A;
  • Lo spazio per le variabili di B;
  • L’indirizzo del “punto di ritorno” di A;
  • Un puntatore al valore di ritorno di B (se necessario).

Successivamente viene passato il controllo alla prima istruzione di B. Al termine dell’esecuzione di B, il controllo ritorno ad A, mediante i seguenti passi:

  • Se B è una funzione incaricata di restituire un valore, il valore di ritorno viene passato alla variabile di ritorno nel record di attivazione di A;
  • Il “punto di ritorno” di A viene ottenuto dal suo record;
  • Il record di B viene rimosso dalla pila.