Ricorsione lineare e non lineare
Una ricorsione si definisce non lineare quando si ha più di una chiamata ricorsiva per blocco.
Per capire bene come opera una ricorsione non lineare si può tracciare un albero che mostra la successione delle chiamate o un albero che mostra la storia dello stack.
Una ricorsione si definisce lineare quando si ha al massimo una chiamata ricorsiva per blocco.
Ricorsione lineare e non lineare (segue)
Supponiamo di avere questo codice.
Ricorsione lineare e non lineare (segue)
Possiamo rappresentarlo mediante il grafico di figura.
Ricorsione lineare e non lineare (segue)
A sinistra è possibile leggere l'output generato dal codice riportato a destra.
Ricorsione lineare e non lineare (segue)
Rappresentiamo le chiamate alle varie function con il grafico di figura.
Ricorsione lineare e non lineare (segue)
Allegato: Mostra codice
L'albero delle chiamate può più sinteticamente essere rappresentato dall'albero di figura.
La successione di Fibonacci
Intorno all’anno 1170 a Pisa un commerciante di nome Bonaccio Pisano ebbe un figlio che chiamò Leonardo. Per motivi di lavoro si trasferì presto ad Algeri dove Leonardo crebbe, studiò e imparò l’arabo avendo dei precettori musulmani. Da costoro imparò la matematica indo-arabica, il sistema decimale con la notazione posizionale delle cifre e l’uso dello zero.
Leonardo Pisano scrisse il primo libro di matematica occidentale: il “Liber Abaci” introducendo le cifre arabe.
Affascinato dal mondo e dalla cultura araba dove ogni persona ha nel suo cognome anche il nome del padre aggiunse al suo nome di Leonardo il cognome Filius Bonacci trasformato per brevità in
Fibonacci.
“Liber Abaci”
La copia della prima pagina del Liber Abaci posseduta dalla Biblioteca Nazionale di Napoli.
Problema
Nel 1228 messer Leonardo Pisano detto Fibonacci si pose il seguente problema:
posta una coppia di conigli in un recinto supponiamo che questa coppia dopo due mesi generi un’altra coppia e successivamente ne generi una al mese. La seconda coppia a sua volta dopo altri due mesi ne genera un’altra e così via.
Dopo un anno, cioè dopo 12 mesi quante coppie di conigli ci saranno nel recinto?
La successione di Fibonacci
Alcuni casi strani
Girasole con 53 (FIB(10)) spirali antiorarie e 89 (FIB(11)) orarie
L'ape può raggiungere la cella n seguendo FIB(n+1) percorsi diversi
La funzione FIB(N)
La funzione FIB(N) che calcola i numeri di Fibonacci relativa ad un intero N obbedisce ad una regola molto semplice che si può descrivere in modo ricorsivo:
Se N=0 allora FIB(N)=0
Se N=1 allora FIB(N)=1
Se N>1 allora FIB(N)=FIB(N-1)+FIB(N-2)
La funzione FIB(N) si presta ad essere subito tradotta nel seguente codice:
int FIB(int N) {
if (N==0)
return 0;
else if (N==1)
return 1;
else
return FIB(N-1)+FIB(N-2);
}
Osserviamo che in una stessa riga di codice abbiamo due chiamate ricorsive (FIB(N-1)+FIB(N-2))
Ricorsione non lineare
Siamo di fronte ad una ricorsione non lineare quando nell’ambito di uno stesso processo ricorsivo si ha più di una chiamata ricorsiva.
Pur nella sua semplicità, l’algoritmo mostrato consuma molte risorse: per numeri grandi c’è il pericolo di uno stack overflow. Per mostrare questo aspetto, introduciamo una nuova variabile, chiama, che ci restituisca il numero di volte in cui la funzione richiama se stessa; tale variabile, passata per riferimento, viene aggiunta alla lista dei parametri formali.
int FIB(int N, int &chiama)
{
chiama++;
if (N==0)
return 0;
else if (N==1)
return 1;
else
return FIB(N-1, chiama)+FIB(N-2, chiama);
}
Albero delle chiamate ricorsive di FIB(3) e FIB(4)
Come precedentemente introdotto è possibile rappresentare l’evoluzione di un processo ricorsivo mostrando l’albero delle successive chiamate ricorsive.
Quest’albero è mostrato nel lucido che segue per FIB(4).
Nel lucido succesivo è mostrato l’albero per FIB(6) e una corrispondente rappresentazione dello stack relativo ai processi ricorsivi man mano aperti.
Albero delle chiamate ricorsive di FIB(3) e FIB(4) (segue)
int FIB(int N, int &chiama) {
chiama++;
if (N==0)
return 0;
else if (N==1)
return 1;
else
return FIB(N-1, chiama)+FIB(N-2,chiama);
}
Albero delle chiamate ricorsive di FIB(6)
int FIB(int N) {
if (N==0)
return 0;
else if (N==1)
return 1;
else
return FIB(N-1)+FIB(N-2);
}
Complessità dell’algoritmo per il calcolo dei numeri di Fibonacci
E’ stato dimostrato che per N abbastanza grande la complessità di F(N), cioè il numero di chiamate ricorsive, è circa O(1.61N).
La successione di Fibonacci ricorsiva
Il codice che segue mostra il calcolo della successione di Fibonacci per un preassegnato e il numero di chiamate ricorsive necessarie.
La successione di Fibonacci ricorsiva: Mostra codice
Definizioni Mostra codice
Output del codice precedente per diversi valori di N
Riduzione della complessità di calcolo
Per ridurre da O (1.61N) a O(N) la complessità di calcolo per i numeri di Fibonacci invece di chiamare ricorsivamente la procedura di calcolo per ogni nodo dell’albero dello stack depositiamo i risultati di ogni computazione in un array e li richiamiamo, senza più calcolarli ogni volta che ne abbiamo bisogno.
Detto FibNos l’array in cui si depositano i numeri parziali possiamo costruire una procedura ricorsiva alla seguente maniera:
caso base
Quando N=2 allora poni
FibNos[0] ← 0
FibNos[1] ← 1
FibNos[2] ← 1
CHIAMATA RICORSIVA
FibNos[N] ← FibNos[N-2] + FibNos[N-1]
Riduzione della complessità di calcolo (segue)
Di seguito mostriamo il codice, l’albero ricorsivo, e lo stack delle chiamate.
void FibVett(int N, double FibNos[])
{
if (N==2) {
FibNos[0] =0;
FibNos[1] =1;
FibNos[2] =1;
}
else
{
FibVett(N-1,FibNos);}
FibNos[N]=FibNos[N-2] + FibNos[N-1];}
Svantaggio
Siamo limitati dalla dimensione dell’array per determinare N massimo.
Altra soluzione
Un’altra soluzione sempre di complessità lineare sfrutta due variabili di appoggio ed è illustrata di seguito.
Mostra codice Mostra codiceLo stack ricorsivo di fibo(6)
double fibo(double N, double prec, double att, double i, double &chiama)
{ double temp;
if (i<N) {
temp=prec+att;
prec=att;
att=temp;
chiama++;
return fibo(N,prec,att,i+1,chiama); }
else
return att;
}
Allegato: Mostra codice
Esercizio 1
Detto Fn l’ennesimo numero di Fibonacci scrivere un programma che calcoli l’espressione:
A=Fn+1* Fn-1 – F2n
Mostrare i valori di A per N=1,2,3,4,5,6,7,8,9,10
Allegato: Mostra codice
Esercizio 2
1- Assegnato un intero N, calcolare il rapporto tra le coppie di numeri di Fibonacci F(n+1)/F(n) e per ogni coppia sottrarre a detto rapporto la radice positiva dell’equazione
x2-x-1=0.
2- Calcolare il MCD tra la somma dei numeri di Fibonacci
compresi tra 1 e 10 e quelli compresi tra 11 e 20
compresi tra 11 e 20 e quelli compresi tra 21 e 30
compresi tra 21 e 30 e quelli compresi tra 31 e 40
Testo consigliato da leggere: MARIO LIVIO – La sezione aurea
Esercizio 3
Calcolare con una funzione ricorsiva l’N-esimo termine della successione seguente
a1=3
a2=1
a3=-1
an=an-1*an-2-(an-3+an-1+an-2)
Caso base -> S(1)=3, S(2)=1, S(3)=-1
Chiamata ricorsiva -> S(N)=S(N-1)*S(N-2)-(S(N-3)+S(N-1)+S(N-2))
Mostra codice
