1
Ricorsione lineare e non lineare
Una ricorsione si definisce lineare quando si ha al massimo una chiamata
ricorsiva per blocco
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.
2
Supponiamo di avere il seguente
codice:
// MAIN
int main()
{
int N;
cout<<"main chiama A"<<endl;
problemaA(1);
cout<<"A ritorna a main"<<endl;
cout<<"main chiama C(1)"<<endl;
problemaC(1);
cout<<"C(1) ritorna a main"<<endl;
cout<<"main chiama Fine"<<endl;
cout<<"
Fine"<<endl;
system("pause");
}
void problemaA(int N)
{
cout<<"A chiama B"<<endl;
problemaB(N);
cout<<"B ritorna A"<<endl;}
void problemaB(int N)
{ cout<<"C("<<N<<") chiama C("<<N-1 <<") “<<endl;
cout<<"B chiama C(1)"<<endl;
problemaC(1);
cout<<" C(1) ritorna a B )"<<endl;
}
void problemaC(int N)
{
if (N>0)
{cout<<"C("<<N<<") chiama C("<<N-1<<")"<<endl;
problemaC(N-1);
cout<<" C("<<N-1<<") ritorna a C("<<N<<")"<<en
}
}
3
Possiamo rappresentarlo mediante il grafico di figura
problema C(1)
MAIN
problema C(0)
problema A
problema B
problema C(1)
problema C(0)
4
A sinistra è possibile leggere l’output generato dal codice posto a destra
main chiama A
A chiama B
B chiama C(1)
C(1) chiama C(0)
C(0) ritorna a C(1)
C(1) ritorna a B
B ritorna A
A ritorna a main
main chiama C(1)
C(1) chiama C(0)
C(0) ritorna a C(1)
C(1) ritorna a main
main chiama Fine
Fine
int main()
{
int N;
cout<<"main chiama A"<<endl;
problemaA(1);
cout<<"A ritorna a main"<<endl;
cout<<"main chiama C(1)"<<endl;
problemaC(1);
cout<<"C(1) ritorna a main"<<endl;
cout<<"main chiama Fine"<<endl;
cout<<"
Fine"<<endl;
system("pause");
}
// DEFINIZIONI
void problemaC(int N)
{ if (N>0)
{
cout<<"
C("<<N<<") chiama C("<<N-1<<")"<<endl;
problemaC(N-1);
cout<<"
C("<<N-1<<") ritorna a C("<<N<<")"<<endl;
}
}
void problemaB(int N)
{
cout<<" B chiama C(1)"<<endl;
//
cout<<" C("<<N<<") chiama C("<<N-1<<")"<<endl;
problemaC(1);
cout<<" C(1) ritorna a B )"<<endl;
}
void problemaA(int N)
{ cout<<" A chiama B"<<endl;
problemaB(N);
cout<<" B ritorna A"<<endl;
}
5
Rappresentiamo le chiamate alle varie function con il grafico di figura
main chiama Fine
main
main chiama A
Fine ritorna a main
main chiama C(1)
A
A chiama B
A ritorna a main
C(1) ritorna a main
B
B ritorna A
B chiama C(1)
C(1)
C(1)
C(1) ritorna a B
C(1) chiama C(0)
C(0)
C(1) chiama C(0)
C(0) ritorna a C(1)
C(0) ritorna a C(1)
6
C(0)
Più sinteticamente rappresentato dall’albero seguente:
main
A
B
fine
C(1)
C(1)
C(0)
C(0)
Allegato: La ricorsione non lineare
7
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 a 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.
8
La copia del Liber Abaci
posseduta dalla Biblioteca
Nazionale di Napoli
9
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?
10
La successione di Fibonacci
1
0
2
1
3
2
4
3
5
5
6
8
7
11
13
La successione di numeri interi che così si ottiene è detta
successione di Fibonacci.
E’ possibile rinvenire tale successione in molti esempi presenti in
natura.
Nella diapositiva successiva è mostrato il caso delle spirali dei
girasole e dei cammini che un ape può percorrere per andare
dalla prima cella di un alveare alla n-esima, supponendo che tutte
le celle siano di forma esagonale.
12
ALCUNI CASI STRANI
L’ape può raggiungere la cella n
seguendo FIB(n+1) percorsi diversi
Girasole con 53 (FIB(10)) spirali antiorarie e 89 (FIB(11)) orarie
13
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))
14
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);
}
15
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.
16
Albero delle chiamate ricorsive di FIB(3) e FIB(4)
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);
}
main
main
F(3)
F(1)
F(4)
Fibonacci(3)
F(2)
F(2)
F(0)
F(3)
F(1)
F(1)
F(1)
Fibonacci(4)
F(2)
F(0)
17
F(1)
F(0)
Albero delle chiamate ricorsive di FIB(6)
F(6)
F(5)
F(4)
F(2)
F(1)
F(3)
F(0)
F(1)
F(2)
F(1)
F(1)
1F(1)
+
1
F(2)
+
3F(4)
F(2)
F(1)
F(0)
F(3)
F(1)
F(0)
F(2)
F(1)
0F(0)
0F(0)
1F(2)
stack
F(0)
+
1F(1)
F(4)
F(3)
+
1F(1)
2F(3)
+
F(6)
F(5)
int FIB(int N) {
if (N==0)
return 0;
else if (N==1)
return 1;
else
18
return FIB(N-1)+FIB(N-2);
}
F(0)
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).
N
1,61^N
30 MFLOP
1 TERAFLOP
1
2
10
117
20
13.694
40
187.514.580
6,3
sec
50
21.942.888.767
12,2
min
100
481.490.367.451.071.000.000
508.931
anni
508
200
231.832.973.948.168.000.000.000.000.000.000.000.000.000
3E+26
anni
3E+23
sec
19
Il codice che segue mostra il calcolo della successione di Fibonacci per un
preassegnato valore e il numero di chiamate ricorsive necessarie.
// La successione di fibonacci ricorsiva
#include <iostream>
// DEFINIZIONI
using namespace std;
double FIB(int N, double &chiama)
// PROTOTIPI
{
double FIB(int , double &);
chiama++;
// MAIN
if (N==1)
int main()
return 1;
{
else if (N==2)
double N;double Tot;
return 1;
do
else
{
return FIB(N-1,chiama)+FIB(N-2,chiama);
cout<<"Assegna N "<<endl;
}
cin>>N;
Tot=0;
cout<<" Il numero di fibonacci "<<N<<" = "<< FIB(N,Tot)<<"chiamate = "<< Tot
<<endl;
}
while (N>=0);
system("pause");
20
}
Output del codice precedente per diversi valori di N.
Fibonacci(5) =
5
Fibonacci(10) =
55
Fibonacci(15) =
610
Fibonacci(20) =
6.765
Fibonacci(25) =
75.025
Fibonacci(30) =
832.040
Fibonacci(35) =
9.227.465
Fibonacci(40) =
102.334.155
Fibonacci(45) = 1.134.903.170
chiamate=
chiamate=
chiamate=
chiamate=
chiamate=
chiamate=
chiamate=
chiamate=
chiamate=
9
109
1.219
13.529
150.049
1.664.080
18.454.900
204.668.000
2.269.810.000
21
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]
22
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[0]=0
FibNos[1]=1
FibVetNo(2)
FibNos[2]=1
FibVetNo(3)
FibNos[3]=2
FibVetNo(4)
FibNos[4]=3
F(4)
FibNos[N]=FibNos[N-2] + FibNos[N-1];
F(2)
F(3)
F(1)
Svantaggio
Siamo limitati dalla dimensione dell’array per determinare N
massimo
fibonacci
F(2)
23
Un’altra soluzione sempre di complessità lineare sfrutta due variabili di appoggio
ed è illustrata di seguito.
int main () {
double Num;
cout<<" Quale numero di fibonacci desideri ? ";
cin>>Num;
double i=2, p=1, chiama=0;
cout<<" Il fibonacci di "<<Num<<" e' "<<fibo(Num,p,a,i,chiama)<<" passi “<<chiama << endl
system("pause");
}
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;
}
24
Lo 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
N=6, prec=5, att=8, i=6
att=8
return att;
}
N=6, prec=3, att=5, i=5
N=6, prec=2, att=3, i=4
N=6, prec=1, att=2, i=3
+
N=6, prec=1, att=1, i=2
Allegato: fibonacci
25
ESERCIZIO
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: fibondiff
26
Esercizio
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
27
ESERCIZIO
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))
Di seguito è riportato il codice corrispondente.
28
/*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)
*/
double succ(double N)
{
if (N==1)
return 3;
else if (N==2)
return 1;
else
if (N==3)
return -1;
else
return succ(N-1)*succ(N-2)-(succ(N-3)+succ(N-1)+succ(N-2));
29
Riscrivere la procedura precedente rendendola lineare
30