Barninga Z
a- a+

Le funzioni: la ricorsione

La ricorsione

Abbiamo già accennato che la ricorsione è realizzata da una funzione che richiama se stessa: si tratta di una tecnica di programmazione che può fornire soluzioni eleganti ed efficienti a problemi che, talvolta, possono essere affrontati anche mediante la semplice iterazione. Ogni funzione, main() compresa, può richiamare se stessa, ma è evidente che deve essere strutturata in maniera opportuna: non esistono, peraltro, strumenti appositi; occorre progettare attentamente l'algortimo.

Un esempio di problema risolvibile sia iterativamente che ricorsivamente è il calcolo del fattoriale di un numero. Il fattoriale di un numero intero positivo n (simbolo n!) è espresso come una serie di moltiplicazioni ripetute a partire da

n * (n - 1)

 

Il risultato di ogni moltiplicazione è quindi moltiplicato per un fattore di una unità inferiore rispetto a quello del moltiplicatore dell'operazione precedente. La formula di calcolo del fattoriale di n è pertanto:

n! = n * (n - 1) * (n - 2) * ... * 2 * 1

 

Inoltre, per definizione, 1! = 1 e 0! = 1. Raggruppando tutti i fattori che, nella formula precedente, precedono n, si osserva che

(n - 1)! = (n - 1) * (n - 2) * ... * 2 * 1

 

e pertanto il fattoriale di un numero intero può essere anche espresso come il prodotto del medesimo per il fattoriale dell'intero che lo precede:

n! = n * (n - 1)!

 

I due esempi che seguono implementano il calcolo del fattoriale con due approcci radicalmente differenti: delle due definizioni, o meglio "rappresentazioni" di n! date poco sopra, la soluzione iterativa è fondata sulla prima, mentre la ricorsione traduce in concreto la seconda.

Un ciclo in grado di calcolare il fattoriale di un intero è il seguente:

    int n;
    long nfatt;
    ....
    for(nfatt = 1L; n > 1; n--)
        nfatt *= n;

 

Al termine delle iterazioni nfatt vale n!.

Vediamo ora la soluzione ricorsiva:

long fattoriale(long n)
{
    return((n < 2) ? 1 : n * fattoriale(n - 1));
}

 

La funzione fattoriale() restituisce 1 se il parametro ricevuto è minore di 2 (cioè vale 01), mentre in caso contrario il valore restituito è il prodotto di n per il fattoriale di n­1, cioè n!: si noti che fattoriale() calcola il valore da restituire chiamando se stessa e "passandosi" quale parametro il parametro appena ricevuto, ma diminuito di uno.

Il termine "passandosi" è una semplificazione: in realtà fattoriale() non passa il parametro a se stessa, ma ad una ulteriore istanza di sé. Che significa? Nell'esecuzione del programma ogni chiamata a fattoriale() utilizza in memoria, per i dati[16], una differente area di lavoro, in quanto anche questo meccanismo utilizza lo stack per operare. Se una funzione definisce variabili locali ed effettua una ricorsione, la nuova istanza alloca le proprie variabili locali, senza conoscere l'esistenza di quelle dell'istanza ricorrente. E' evidente che se una istanza di una ricorsione potesse accedere a tutte le variabili, incluse quelle locali, definite in ogni altra istanza, la funzione non avrebbe un proprio spazio "riservato" in cui operare: ogni modifica a quasiasi variabile si rifletterebbe in tutte le istanze, e ciascuna di esse potrebbe quindi scompaginare il valore delle altre.

A volte, però, può essere utile che una istanza conosca qualcosa delle altre: ad esempio un contatore, che consenta di sapere in qualunque istanza quanto in profondità si sia spinta la ricorsione. Tale esigenza è soddisfatta dalle variabili static, in quanto esse sono locali alla funzione in cui sono definite, ma comuni a tutte le sue istanze. L'affermazione risulta del tutto comprensibile se si tiene conto che le variabili statiche sono accessibili solo alla funzione in cui sono definite, ma esistono e conservano il loro valore per tutta la durata del programma. Quando una funzione è chiamata per la prima volta ed assegna un valore ad una variabile statica, questa mantiene il proprio valore anche in una seconda istanza (e in tutte le successive) della stessa funzione; mentre delle variabili automatic è generata una nuova copia in ogni istanza, una variabile static è unica in tutte le istanze e poiché essa esiste e mantiene il proprio valore anche in uscita dalla funzione, ogni istanza può conoscere non solo il valore che tale variabile aveva nell'istanza precedente, ma anche nell'istanza successiva (ovviamente dopo il termine di questa).

Le variabili globali, infine, sono accessibili a tutte le istanze ma, a differenza di quelle statiche, lo sono anche alle altre funzioni: in fondo non si tratta di una novità.

Si noti che la funzione fattoriale() deve essere chiamata una sola volta per ottenere il risultato ricercato:

    printf("10! = %ld
" ,fattoriale(10));

 

Non serve alcuna iterazione, perché la ricorsione implementata internamente dalla funzione è sufficiente al calcolo del risultato.

Vediamo un altro esempio: la funzione scanDirectory() ricerca un file nell'albero delle directory, percorrendo tutte le sottodirectory di quella specificata come punto di partenza:

/*******************************************************

    SCANDIR.C - Barninga Z! - 1994

    void cdecl scanDirectory(char *path,char *file);

    char *path;   path di partenza per la ricerca del file. 
Deve terminare con una backslash ("").
    char *file;   nome del file da ricercare in 
path ed in tutte le sue subdir. Puo' contenere le 
wildcards "?" e "*".

    Visualizza i pathnames (a partire dal punto 
indicato da path) dei files trovati.

    Compilato con Borland C++ 3.1:

    bcc -c -mx scandir.c

    dove x specifica il modello di 
memoria e puo' essere: t, s, m, c, l, h.

*********************************************/
#include 
#include 
#include 
#include 

#define ALL_ATTR   (FA_ARCH+FA_HIDDEN+FA_SYSTEM+FA_RDONLY)
// cerca ogni tipo di file

void cdecl scanDirectory(char *path,char *file)
{
    struct ffblk ff;

// Considera tutto quello che c'e' nella directory (*.*)

    strcat(path,"*.*");

// Qui inizia il loop di scansione della 
//directory in cerca di eventuali subdir.
// In pratica ricerca tutti i tipi di file 
//compresi quelli il cui attributo indica
// che si tratta di una directory.

    if(!findfirst(path,&ff,FA_DIREC+ALL_ATTR)) {  
// cerca le subdir
        do {

// Se il file trovato e' proprio una directory, 
// e non e' "." o ".." (cioe' la
// directory stessa o la directory di cui essa e' 
// subdir) allora viene concatenato
// il nome della dir trovata al pathname di lavoro...

            if((ff.ff_attrib & FA_DIREC) && 
(*ff.ff_name != '.')) {
                strcpy(strrchr(path,'')+1,ff.ff_name);
                strcat(path,"");

// ...e si effettua la ricorsione: scanDirectory() 
// richiama se stessa passando alla
// nuova istanza il nuovo path in cui ricercare 
// le directory. Cio' si spiega col
// fatto che per ogni directory l'elaborazione da 
// effettuare e' sempre la stessa;
// l'unica differenza e' che ci si addentra di un 
// livello nell'albero gerarchico del
// disco.

                scanDirectory(path,file);
            }
        } while(!findnext(&ff));      
// procede finche' trova files o subdirs
    }

// Quando tutti gli elementi della directory 
// sono stati scanditi ci troviamo nella
// subdir piu' "profonda" e si puo' cominciare 
// a considerare i files: viene
// concatenato il template di file al path 
// attuale e si inizia un secondo ciclo
// findfirst()/findnext().

    strcpy(strrchr(path,'')+1,file);
    if(!findfirst(path,&ff,ALL_ATTR)) {   
// cerca i files
        do {

// Per ogni file trovato e' visualizzato il 
// pathname a partire da quello di origine.

            strcpy(strrchr(path,'')+1,ff.ff_name);
            printf("%s
" ,path);
        } while(!findnext(&ff));      
// procede finche' trova files
    }

// Quando anche i files della directory 
// sono stati analizati tutti, scanDirectory()
// elimina dalla stringa il nome 
// dell'ultimo file trovato...

    *(strrchr(path,'')) = NULL;

// ...e quello dell'ultima directory scandita: 
// i "risale" cosi' di un livello
// nell'albero.

    *(strrchr(path,'')+1) = NULL;

// A questo punto, se l'attuale istanza 
// di scanDirectory() e' una ricorsione (siamo
// cioe' in una subdirectory) l'esecuzione 
// del programma prosegue con la precedente
// istanza di scanDirectory(): sono cercate 
// altre subdirectory, e, in assenza di
// queste, i files; se invece la presente 
// istanza di scanDirectory() e' la prima
// invocata (non c'e' stata ricorsione o 
// sono gia' state analizzate tutte le subdir
// nonche' la directory di partenza), 
// allora il controllo e' restituito alla
// funzione chiamante originaria: il lavoro 
// di ricerca e' terminato.

}

La funzione scanDirectory() riceve due parametri: il primo è una stringa che rappresenta il "punto di partenza" , cioè la directory all'interno della quale ricercare il file; la ricerca è estesa a tutte le subdirectory in essa presenti. Il secondo parametro è una stringa esprimente il nome (e la estensione) del file da individuare e può contenere le wildcard "*" e "?" , che sono risolte dal servizio DOS sottostante alle funzioni di libreria findfirst() e findnext(). Quando, nel "territorio di caccia" , è individuato un file il cui nome soddisfa il template fornito dal secondo parametro, ne viene visualizzato il pathname completo (a partire dalla directory di origine). La scanDirectory() può essere sperimentata con l'aiuto di una semplice main() che riceva dalla riga di comando il path di partenza ed il template di file:

#include 
#include 
#include 

void main(int argc,char ** argv);
void scanDirectory(char *path,char *file);

void main(int argc,char **argv)
{
    char path[MAXPATH];

    if(argc != 3)
        printf("Specificare un path di 
partenza e un template di file
");
    else {
        strcpy(path,argv[1]);  
// copia il path di partenza nel buffer...
        strupr(path);  
// ...e lo converte tutto in maiuscole
        if(path[strlen(path)-1] != '')     
// se non c'e' una backslash in fondo...
            strcat(path,"");   // ...la aggiunge
        scanDirectory(path,argv[2]);
    }
}

 

Per inciso, la funzione di libreria findfirst() può essere utilizzata per finalità diverse dalla scansione di una directory.

Il punto debole dell'approccio ricorsivo alla definizione di un algoritmo consiste in un utilizzo dello stack più pesante rispetto alla soluzione iterativa: ogni variabile locale definita in una funzione ricorsiva è duplicata nello stack per ogni istanza attiva. E' perciò necessario, onde evitare disastrosi problemi in fase di esecuzione[17], contenere il numero delle variabili locali (soprattutto se "ingombranti"), o richiedere al compilatore la generazione di uno stack di maggiori dimensioni[18]. E' decisamente sconsigliabile definire array nelle funzioni ricorsive: ad essi può essere sostituito un puntatore, assai più parco in termini di stack, gestito mediante l'allocazione dinamica della memoria. Anche l'allocazione dinamica può influenzare lo spazio disponibile nello stack: uno sguardo all'organizzazione di stack e heap nei diversi modelli di memoria servirà a chiarire le idee.

Inoltre, per ragioni di efficienza, è a volte opportuno dichiarare esplicitamente near le funzioni ricorsive, infatti esse possono essere eseguite più e più volte (come tutte le funzioni all'interno di un ciclo, ma nel caso della ricorsione è la funzione che chiama se stessa): una chiamata near è più veloce e impegna meno stack di una chiamata far. Dichiarare esplicitamente near le funzioni ricorsive assicura che sia generata una chiamata near anche quando il modello di memoria utilizzato in compilazione preveda per default chiamate far. Lo svantaggio di questo approccio è che una funzione dichiarata near può essere chiamata esclusivamente da quelle funzioni il cui codice eseguibile sia compreso nel medesimo segmento[19]: è un aspetto da valutare attentamente in fase di scrittura del codice, dal momento che se non si è sicuri di poter soddisfare tale condizione occorre rinunciare alla dichiarazione near.




Ti potrebbe interessare anche

commenta la notizia

C'è 1 commento
Sara
Hai dubbi su questo articolo?