18: Funzioni ricorsive

Nelle guide precedenti abbiamo visto cosa sono le funzioni, come si invocano e come si effettua il passaggio dei loro parametri. Oggi tratteremo di un argomento fondamentale per i linguaggi di alto livello: la ricorsività.

Anzitutto definiamo cosa vuol dire “ricorsione”. In parole semplici, la ricorsione è il meccanismo di programmazione in cui una funzione effettua una chiamata di se stessa: le funzioni che eseguono una ricorsione prendono il nome di funzioni ricorsive. Inoltre, se due funzioni si chiamano l’un l’altra vengono dette funzioni mutualmente ricorsive.

Facciamo ora un esempio di un programma che utilizza funzioni ricorsive:


#include <stdio.h>

int x,y;

int fattoriale (int n)

{

if (n<=1) return 1; // se n=0 o n=1, ritorno 1

else return n*fattoriale(n-1);

}

int main ()

{  printf ("Inserisci il numero di cui vuoi calcolare il fattoriale \n");

scanf ("%d", &x);

y=fattoriale(x);

printf ("\n Il risultato è: %d",y);

} 

Il programma chiede all’utente qual è il numero di cui vuole calcolare il fattoriale. Spero che tutti sappiano cosa sia il fattoriale, altrimenti cliccate qui. Dopo, esegue la funzione fattoriale: mettiamo caso che noi abbiamo inserito il numero 3 (x=n=3), la funzione esegue l’else n*fattoriale(n-1), ovvero 3*fattoriale(3-1); richiama quindi la funzione fattoriale un’altra volta, stavolta con n=2  (perché è 3-1) e fa 2*fattoriale(1); ancora allora richiama la funzione fattoriale con n=1 (perché 2-1) che questa volta esegue l’if che ritorna 1. Abbiamo allora y=3*2*1=6, scaturito dall’espressione y=fattoriale(3)=3*fattoriale(2)=3*2*fattoriale(1)=3*2*1. Il risultato viene poi stampato a video.

Ma se chiamo le stessa funzione più volte, i dati (variabili/parametri) di ognuna non si sovrappongono nella pila di memoria? No. Ogni chiamata di funzione alloca sullo stack (in frame diversi) le variabili e i parametri passati: viene associata un’area dati a ogni esecuzione!

Questa nozione costituisce una novità rispetto alla regola che avevamo adottato finora: in tutti i casi precedenti e in tutti i programmi degli articoli scorsi abbiamo detto che, prima di eseguire un programma, deve essere nota la quantità di memoria necessaria per eseguirlo(memoria statica); siccome alla ricorsione serve un’area dati per ogni chiamata di funzione, questa non può essere nota a priori, ma viene aggiornata durante l’esecuzione: parliamo quindi di allocazione dinamica della memoria.

In C, la funzione presente nella libreria standard per l’allocazione della memoria è la malloc. Il suo prototipo è:

 void *malloc(size_t size); 

dove size è lo spazio di memoria in byte allocato. Se l’operazione ha successo, viene restituito un puntatore al blocco di memoria, mentre in caso contrario verrà restituito un puntatore NULL. Siccome la memoria allocata tramite malloc è persistente, rimane lì fino alla fine del programma o fino a che non la si dealloca esplicitamente attraverso la funzione free:

 void free (void *pointer); 

che rilascia il blocco di memoria indicato da pointer.

Esempio:

 int *puntatore= (int*) malloc (4*sizeof(int)); //alloca un array di 4 elementi di dimensione int

free (puntatore); // libero la memoria

A cosa serve la ricorsione? Come si può notare, può servire a risolvere un problema complesso, o comunque ripetitivo/iterativo, in poche righe di codice. Tuttavia, in generale, la ricorsione è poco efficiente perché richiede tempo per la gestione dello stack e consuma molta memoria.

Dubbi, perplessità? Chiedete pure!

Please follow and like us: