Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Ernesto Burattini » 9.Ricorsione non lineare


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.

Supponiamo di avere questo codice.


Ricorsione lineare e non lineare (segue)

Possiamo rappresentarlo mediante il grafico di figura.

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.

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.

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.

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.

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

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

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 codice

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
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
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion