Le funzioni ricorsive

Materie:	Tesina
Categoria:	Informatica
Voto:	2.5 (2)
Download:	638
Data:	30.09.2008
Numero di pagine:	9
Formato di file:	.doc (Microsoft Word)

Le funzioni ricorsive
Elena Bortoletto 4^H
27/11/2007

Indice
• Ricorsione e Iterazione……………………………………………………pag. 3
• Il fattoriale: ricorsivo per definizione…………….………………..pag. 4
• Permutazioni e Disposizioni…………………………………………….pag. 5
• Combinazioni………………………………………………………………….pag. 6
• La serie di Fibonacci………………………………………………………..pag. 7
• Ordinamento con il quicksort………………………………………….pag. 8
• Conclusioni……………………………………………………………………..pag. 8
Le funzioni ricorsive
Ricorsione e Iterazione
Per parlare di funzioni ricorsive e poterle spiegare è necessario innanzitutto distinguerle dalle funzioni iterative.
Le funzioni iterative sono strutture di controllo che ordinano all’elaboratore di eseguire una sequenza di istruzioni ripetutamente, in genere fino al verificarsi di particolari condizioni. Le iterazioni sono più comunemente conosciute con il nome di “cicli”. Le strutture cicliche o iterative più comuni sono il “while”, il “do…while” e il “for”.
Le funzioni ricorsive, alternative eleganti, sintetiche e più chiare delle iterative, sono funzioni che per svolgere il loro lavoro richiamano se stesse direttamente o indirettamente su un input diverso. Così ad ogni richiamo la profondità dell’elaborazione aumenta, finché ad un certo punto, arrivati quindi al passo base, quel passo oltre il quale non si può andare perché è l’unico che conosciamo essere certo, lo scopo viene raggiunto e la funzione ritorna, passo ricorsivo.
Le funzioni ricorsive sono sì il modo più veloce per risolvere i problemi, ma hanno anche degli aspetti negativi. Il primo su tutti è il metodo statico di allocazione, quel metodo che fa salvare alla funzione ricorsiva il suo stato nel momento in cui essa si richiama nello stack; e avendo visto che la ricorsione è molto veloce, anche l’occupazione di memoria avviene altrettanto velocemente. L’allocazione diviene statica perché la funzione che richiama se stessa non può buttare fuori dalla pila (stack) nessun valore in quanto ogni volta li richiama.
Fat(3)
Main

Fat(2)
Fat(3)
Main
Fat(1)
Fat(2)
Fat(3)
Main
Fat(0)
Fat(1)
Fat(2)
Fat(3)
Main
Come si vede, questa è un’esemplificazione di una pila riferita al fattoriale (di cui si parlerà più avanti). Quello che si nota è appunto l’allocazione in pila dei valori di Fat: Fat(3) non può uscire perché richiama Fat(2), che a sua volta richiama Fat(1). Questo, poi, richiamando Fat(0), arriva al passo base, che può essere calcolato in quanto si conosce il valore: Fat(0)=1, e di conseguenza tutti gli altri valori possono essere calcolati: Fat(1)=Fat(0)*1=1*1=1, ecc.
Quindi possiamo dire che le funzioni iterative utilizzano i cicli, mentre le ricorsive non lo fanno.

Il fattoriale: ricorsivo per definizione
Come prima accennato, il calcolo del fattoriale è un perfetto esempio di funzione ricorsiva in quanto è il prodotto dei numeri di ogni predecessore di n, ovvero n!=n*(n-1). Esempio: 4!=4*3*2*1.
Il passo base della funzione ricorsiva del fattoriale è:
{ if (n==0) || (n==1) fact=1;
Il passo ricorsivo, invece, è:
else fact=n*fact(n-1); return fact; }
Ma vediamo l’algoritmo completo:
/*calcolo del fattoriale con una funzione ricorsiva*/
#include
#include
fat(int);
main()
{ int n;
printf (“calcolo di n! \n\n”);
printf (“inserisci n: \t”);
scanf (“%d”, &n);
printf (“il fattoriale di: %d ha valore: %d\n, n, fat(n));
}
fat (int n)
{ if (n==0)
return (1);
else
return (n*fat(n-1));
system (“pause”);
}
Leggendo l’algoritmo capiamo che fat dovrà ricevere in ingresso il numero intero su cui operare e dovrà poi restituirne il fattoriale. Per restituire il fattoriale utilizza return(n*fat(n-1)). Il compilatore si ferma, e cioè trova il fattoriale, solo quando la condizione di fine ciclo, n==0 viene soddisfatta e fa tornare al programma il valore 1. E tornando al discorso delle pile, la zona di memoria riservata alle chiamate viene gestita con questa logica, quella delle pile per l’appunto; così a ogni invocazione di fat, il sistema alloca uno spazio di memoria libero in testa alla pila riservato al suo parametro formale n. quando termina il ciclo delle chiamate, ogni “ambiente” precedentemente aperto si chiude e passa a quello precedente il valore calcolato.
Un accorgimento per rendere più funzionale questo algoritmo è quello di usare un “long int” al posto dell’int normale nella dichiarazione e nella definizione:
long int fat(long int);
long int fat(long int n);
di conseguenza bisogna modificare il printf del programma principale in modo che indichi il formato in cui si desidera la visualizzazione (%ld) di fat:
printf (“il fattoriale di: %d ha valore: %ld\n, n, fat(n));
In questo modo il long int, che ha dimensione doppia dell’int, evita la possibilità di ottenere risultati di n troppo bassi.
Permutazioni e Disposizioni
Le funzioni ricorsive vengo molto utilizzate anche nell’ambito del calcolo combinatorio, ovvero la branca della matematica che studia i modi per raggruppare e/o ordinare secondo date regole gli elementi di un insieme finito di oggetti; in particolare il calcolo combinatorio si interessa soprattutto di contare tali modi, ovvero le configurazioni.
Ad ogni modo, si definiscono permutazioni semplici di n oggetti distinti, tutti quei gruppi che si possono formare in modo che ognuno di questi contenga gli n oggetti considerati ma che differisca dagli altri gruppi solo e soltanto per l’ordine in cui compaiono gli oggetti stessi. Per esempio, dati due oggetti che chiamiamo e1, e2 le permutazioni possibili sono solo due; se gli oggetti sono tre,e1, e2, e3, le permutazioni saranno sei; ma se gli oggetti aumentano ancora, come nel caso di quattro, la questione si complica: le permutazioni di quattro oggetti distinti sono 24; questo risultato, come anche gli altri, è dato dalla formula: Pn = n!, che significa: il numero di permutazioni P di n oggetti è dato da n fattoriale (n!). E quindi se il numero di permutazioni di n oggetti è uguale al fattoriale di n, per determinarlo si può benissimo usare l’algoritmo precedente, utilizzando però un double.
Un caso particolare, se così si può chiamare, delle permutazioni semplici sono le disposizioni semplici. Dati n oggetti distinti e detto k un numero intero positivo minore o uguale a n, le disposizioni semplici di questi n oggetti vengono definite come i gruppi che si possono formare in modo che ogni gruppo contenga soltanto k oggetti, e che differisca dagli altri o per qualche oggetto, oppure per l’ordine con cui gli oggetti sono disposti. La formula usata per il calcolo delle disposizioni è:
Dn,k = n*(n-1)*(n-2)*…*(n-k+2)*(n-k+1)
Quindi se n=4 e k=1, le disposizioni di questi oggetti saranno dunque i gruppi che contengono un solo oggetto e quindi quattro: D4,1 = 4.
Se, invece, n=4 e k=2 (= gli oggetti vengono presi 2 a 2) le disposizioni semplici sono 12: D4,2 = 4*3.
La procedura ricorsiva per il calcolo delle disposizioni semplici è quella evidenziata nell’algoritmo che segue:
/* calcolo delle disposizioni semplici di n oggetti presi k a k*/
#include
#include
int dispo (int, int, int);
main()
{ int n, k;
printf (“disposizioni semplici di k su n oggetti \n”);
printf (“inserisci n: \t”);
scanf (“%d”, &n);
printf (“inserisci k: \t”);
scanf (“%d”, &k);
printf (“le disposizioni semplici di %d su %d sono: %d\n”, k, n, dispo (k, n, n)); }
int dispo (int k, int n, int m)
{ if (n==m-k)
return (1);
else
return (n*dispo (k, n-1, m)); }
Come si può vedere abbiamo dovuto inserire un ulteriore valore n alla prima invocazione di “dispo” (dispo(k, n, n)) oltre al nostro n iniziale; questo serve affinché il secondo n da noi inserito possa diventare il parametro formale m che ci serve per far conoscere alla funzione il numero totale degli oggetti e, di rimando, per poter effettuare il controllo n=m-k, dato che ogni volta che richiamiamo il parametro formale, n viene decrementato di una unità rispetto al precedente.
Un ultima considerazione per quanto riguarda le disposizioni semplici: la disposizione di n elementi presi n a n è n! :
Dn,n = n! e nel caso in cui abbiamo n=4 e k=4: D4,4 = 24.
È per questo che si dice che il calcolo delle disposizioni è simile a quello del fattoriale.
Combinazioni
Le combinazioni semplici di n oggetti distinti, presi k a k, con k sempre minore o uguale a n, sono tutti i gruppi di k oggetti che si possono formare con gli n oggetti dati, in modo tale che i gruppi differiscano tra loro almeno per un oggetto. La formula utilizzata per il calcolo delle combinazioni è:
Cn,k = Dn,k /k! Che significa: il numero di combinazioni di n oggetti presi k a k è uguale al numero di disposizioni di n oggetti presi k a k, diviso k fattoriale. Il calcolo delle combinazioni è, allora, il calcolo che racchiude in sé tutto quello che è stato detto fin’ora.
In C la funzione che calcola le combinazioni semplici è “comb”. Questa, per calcolare le disposizioni Dn,k , può richiamare dispo; mentre, per calcolare il fattoriale, richiama fat, passandogli sempre k come numero di elementi sui cui basarsi.
La procedura ricorsiva per il calcolo delle combinazioni è quella evidenziata nell’algoritmo che segue:
/*calcolo delle combinazioni semplici di n oggetti presi k a k*/
#include
#include
int comb(int, int);
int dispo (int, int, int);
int fat (int);
main()
{
int n, k;
printf (“combinazioni semplici di k su n oggetti \n”);
printf (“inserire n: \t”);
scanf ( “%d”, &n);
printf (“inserire k: \t”);
scanf (“%d”, &k);
printf (“le combinazioni semplici di %d su %d sono: %d\n”, k, n, comb(k, n));
}
comb (int k, int n)
{
return (dispo (k, n, n)/fat (k));
}
int dispo (int k, int n, int m)
{ if (n==m-k)
return (1);
else
return (n*dispo (k, n-1, m));
}
fat (int n)
{
if (n==0)
return (1);
else
return (n*fat (n-1));
}
La serie di Fibonacci
Fibonacci Leonardo, matematico pisano, dopo aver assimilato, durante numerosi viaggi, le conoscenze matematiche degli arabi, introdusse la “serie di Fibonacci”, utilizzata inizialmente da lui per risolvere alcuni indovinelli. In questa serie, ogni termine è ottenuto sommando i due che lo precedono:
F(n) = F(n-1) + F(n-2) dove n è un numero intero maggiore o uguale a 2.
Ecco, ora, come si ottengono i numeri di Fibonacci.
F(0) = 0
F(1) = 1
F(2) = F(2-1) + F(2-2) = F(1) + F(0) = 1+0 = 1
F(3) = F(3-1) + F(3-2) = F(2) + F(1) = 1+1 = 2
F(4) = F(4-1) + F(4-2) = F(3) + F(2) = 2+1 = 3
F(5) = F(5-1) + F(5-2) = F(4) + F(3) = 3+2 = 5
F(6) = F(6-1) + F(6-2) = F(5) + F(4) = 5+3 = 8
F(7) = F(7-1) + F(7-2) = F(6) + F(5) = 8+5 = 13
E così via…
Ogni volta, come si può vedere, F richiama la F precedente. È evidente, allora, il carattere ricorsivo di questa serie numerica. Non solo. Infatti si potrebbe parlare di “ricorsione doppia” in quanto ogni chiamata di “fibo” genera due ulteriori chiamate ricorsive: una passando il parametro n-1 e l’altra n-2.
Nell’algoritmo useremo un long int per fibo in quanto, a lungo andare, i numeri diventano sempre maggiori e il solo int non sarebbe capace di sostenerli.
Nella parte ricorsiva (sempre quella evidenziata) è evidente perché il return è inserito tre volte: i primi due casi sono quelli noti (F(0)=0 e F(1)=1) e li prende in considerazione solo quando ad n diamo come valori 1 e 0 per l’appunto; l’altro caso, invece, considera tutti i possibili valori di n sempre a patto che n sia positivo ed intero!
Ecco, di seguito, in forma di algoritmo, ciò di cui abbiamo parlato fin’ora:
/* calcolo dei numeri di Fibonacci */
#include
#include
long int fibo (int);
main()
{
int n;
printf (“serie di Fibonacci f(0)=0 f(1)=1 f(n)=f(n-1)+f(n-2)”);
printf (“\n inserire n: \t”);
scanf (“%d”, &n);
printf (“Fibonacci di %d è: %d\n”, n, fibo(n));
}
long int fibo (int n)
{
if (n==0)
return (0);
else if (n==1)
return (1);
else
return (fibo(n-1)+fibo(n-2));
system (“pause”);
}
Ordinamento con il quicksort
Il quicksort è il più veloce metodo di ordinamento ed è anche una complessa procedura ricorsiva.
Come agisce il quicksort? La risposta è banale: come farebbe una qualsiasi persona per ordinare un insieme di oggetti. Il quicksort prima crea due grossi blocchi che inizia ad ordinare costruendone altri sempre più piccoli, per ritrovarsi alla fine con una sequenza completamente ordinata. Quest’algoritmo inizia col determinare un valore detto pivot che agisce da “perno” in quanto si comporta come valore medio: viene stimato con la media tra il primo elemento e l’ultimo della parte di vettore su cui si sta lavorando. Il pivot, allora, suddivide gli elementi del vettore in due parti: quella degli elementi più piccoli e quella degli elementi più grandi di se stesso. Raramente il pivot divide gli elementi in due parti uguali: cioè causa una minore efficienza dell’algoritmo, ma la funzionalità non cambia.
Al termine del ciclo do-while anche l’iterazione termina e inizia la ricorsione: la procedura richiama se stessa passando nuovi valori superiori e inferiori e analizzando blocchi sempre più piccoli del vettore:
if(sindes) quick(i, des);
Il quicksort può anche essere scritto interamente in forma non ricorsiva, ma questa sarebbe poi troppo laboriosa e di difficile lettura.
Conclusioni
Gli algoritmi ricorsivi sono veloci da scrivere, ma non sempre così efficienti. In moltissimi casi l'uso di un algoritmo equivalente ma non-ricorsivo permette una maggiore efficienza al prezzo di un po' di codice in più da scrivere. Inoltre non sempre le funzioni ricorsive sono una risposta efficiente. Consideriamo che ogni chiamata ricorsiva consuma memoria ed utilizza un salto ad una funzione. Ridisegnando la funzione come non-ricorsiva, si risparmia un salto e (forse) un po' di quella preziosa memoria. Sfortunatamente, non tutte le funzioni sono facilmente 'trasformabili' da ricorsive a non-ricorsive: in alcuni casi la funzione non può essere trasformata senza una completa riscrittura, e non sempre ne vale la pena.

2