C/Blocchi e funzioni/Ricorsività

Visivamente una funzione è ricorsiva se al suo interno compare un richiamo a se stessa.

È possibile scrivere una procedura ricorsiva quando :

• Si sta risolvendo un problema con un metodo induttivo.
• Si sta calcolando una funzione tramite la sua definizione induttiva

Le funzioni ricorsive vengono divise in due parti :

• Base della ricorsione
• Passo della ricorsione

Base della ricorsione

Soluzione del problema per la dimensione più piccola per cui è definito corrisponde solitamente alla soluzione immediata.

Esempio :

• Per il fattoriale il termine minimo è "0! = 1" quindi il primo controllo sarà se il numero è uguale a 0 restituisci il valore 1.

Passo della ricorsione

Soluzione del problema per una dimensione Nesima espressa in termini di soluzione del problema di dimensione più piccola.

Esempio :

• N! = N * (N - 1)!

Esempi

Fattoriale di un numero (versione non ricorsiva):

   int fatt (int N) {
      int F=1;
      for (; N>=1; N--)
         F *= N;
      return F;
   }

Fattoriale di un numero (versione ricorsiva):

 int fattr (int N) {
      if (N==0) return 1; /* BASE DELLA RICORSIONE*/
      return N * fattr(N-1); /* PASSO DELLA RICORSIONE*/
   }

 // lo stesso codice in versione piu' ridotta e criptica
 int fattr (int N) {
      return N ? N * fattr(N-1) : 1; 
   }

Algoritmo che genera la successione di Fibonacci:

   int fibor (int N) {
      if (N == 1 || N == 2) return 1; /* BASE DELLA RICORSIONE*/
      return fibor(N-1) + fibor(N-2); /* PASSO DELLA RICORSIONE*/
   }

Problemi dovuti a errori

Eventuali problemi dovuti a errori di scrittura di un algoritmo potrebbero causare uno Stack Overflow, cioè un utilizzo eccessivo della zona di memoria assegnata al programma per essere eseguito. Questo potrebbe provocare una chiusura prematura dell'applicazione.