6.6 La ricorsione

Il linguaggio C consente l’uso di funzioni ricorsive. Una funzione ricorsiva è una funzione che richiama sé stessa (ricorsione diretta) o richiama una funzione che a sua volta la richiama (ricorsione indiretta). Affinché il procedimento abbia fine è necessario che siano verificate le due seguenti proprietà:

1. Debbono esistere dei parametri (valori base) per cui la funzione non richiami sé stessa

2. Ogni volta che la funzione richiama sé stessa i parametri devono essere più vicini ai valori base

L’uso di tali funzioni è di utilità per la codifica di algoritmi che sono definiti ricorsivamente. Un esempio classico di algoritmo ricorsivo è quello che definisce il fattoriale di un numero.

Il fattoriale del numero n intero positivo (cioè n!) è definito:

• uguale a n*(n-1)! se n ¹ 0

• uguale a 1 se n = 0

In altri termini è vera la seguente uguaglianza: n! = n*(n-1)*(n-2)*...2*1. La prima definizione data è di tipo ricorsivo: il fattoriale di un numero viene calcolato come prodotto del numero stesso per il fattoriale del numero che lo precede. Affinché il procedimento sia finito si assume in pratica la posizione: 0! = 1.

/* Fattoriale di un numero */

#include <stdio.h>

int calcFatt(int numero);	/*1*/

main(){ 
  int n,fat; 
  printf("\nCalcola il fattoriale di un numero"); 
  printf("\n\nIntrodurre il numero "); 
  scanf("%d",&n); 
  fat=calcFatt(n);	/*2*/ 
  printf("\n Fattoriale di %d = %d",n,fat); 
}

/* Calcola Fattoriale utilizzando la Ricorsione*/

int calcFatt(int numero){
  int f; 
  if (!numero)	/*3*/ 
    f=1; 
  else 
    f=numero*calcFatt(numero-1);	/*4*/ 
  return f;
}

Nella 1 viene definito il prototipo della funzione che calcola il fattoriale, funzione chiamata dal main nella riga 2. A tale funzione è passato per valore il numero di cui si vuole calcolare il fattoriale.

La struttura condizionale che inizia da 3, come si nota chiaramente, non fa altro che esprimere utilizzando le caratteristiche del linguaggio di programmazione, la definizione di fattoriale. La funzione chiama sé stessa (nella 4) passando come parametro il valore, decrementato di una unità, del parametro ricevuto e in questo modo ci si approssima, come richiesto dalle proprietà espresse precedentemente, al valore 0 (valore base). Tale ultimo valore, in dipendenza della verità della condizione espressa in 3, blocca il processo ricorsivo. La funzione calcFatt poteva, facendo riferimento alla seconda definizione data, essere scritta utilizzando una struttura ciclica:

/* 
   Calcola Fattoriale utilizzando una Struttura
   Ciclica
*/

int calcFatt(int numero){
  int i,f; 
  f=1; 
  for(i=numero;i>0;i--) 
    f *= i; 
  return f; 
}

Nella prima versione di calcFatt il ciclo è in pratica sostituito dalla chiamata ricorsiva; l’algoritmo risulta più leggibile, più vicino al nostro modo di concepire la risoluzione del problema.

La ricorsione può essere applicata a qualsiasi funzione che utilizzi assegnazioni, istruzioni if-else e while. A titolo di esempio si propone il programma per il calcolo della somma di una serie di numeri, terminanti con il valore nullo, scritto utilizzando una funzione ricorsiva al posto di una struttura ciclica:

/* 
   Somma una serie di numeri terminanti con 0
   utilizzando una funzione ricorsiva
*/

#include <stdio.h>

int prossimo(void);

main(){ 
  int somma;  
  somma = prossimo(); 
  printf("\nSomma = %d",somma); 
}

/* Funzione ricorsiva per il calcolo della somma */

int prossimo(void){
  int questo,somm; 
  printf("\nNumero da Sommare ="); 
  scanf("%d",&questo); 
  if (questo){	/*1*/ 
    somm = questo+prossimo(); 
    return somm; 
  }else 
    return 0; 
}

Anche in questo caso, nella definizione della funzione, esiste un valore base (questo==0) e la funzione, richiamando sé stessa si approssima a tale valore (se si immaginano tutti gli input in una coda di attesa, ogni volta che se ne preleva uno con la funzione scanf, ci si avvicina alla fine della coda).

L’uso della funzione ricorsiva in questo caso rende più evidente l’algoritmo utilizzato. La struttura che comincia dalla riga 1 si può infatti interpretare:

se questo numero preso in esame esiste (ha cioè un valore non nullo)
  somma questo numero con il prossimo
altrimenti
  concludi la somma
fine-se