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

Salvatore Cuomo » 16.La ricorsione


La ricorsione

Definizione

Una funzione si dice ricorsiva se, assegnato un valore iniziale ao , il valore assunto in un punto an, si può ottenere come funzione del valore
precedente an-1. Ovvero:

  • ao se né uguale 0
  • an =f(an-1) se non è uguale a 0

Un primo esempio di approccio ricorsivo è dato dal calcolo del fattoriale di un assegnato numero n. Ricordiamo che per n! si intende il prodotto dei primi n interi.

Esempio

5!=1*2*3*4*5

La Ricorsione.

La Ricorsione.


Esempio versione iterativa

Il calcolo del fattoriale

Il calcolo di n! può essere fatto utilizzando un algoritmo di tipo iterativo. Si riporta un codice in linguaggio C che implementa questo approccio.

Nell’esempio si utilizza l’header file limits.h per controllare se nel calcolo del fattoriale si ottenga un numero troppo grande rispetto all’intero massimo rappresentabile. In particolare la costante deputata a tale scopo è:

LONG_MAX

Codice_C_1

Codice_C_1


Esempio versione ricorsiva

Il calcolo del fattoriale

In figura si mostra una rappresentazione grafica dell’approccio ricorsivo per il calcolo di n! e successivamente si analizza l’implementazione della funzione fattoriale in linguaggio C.

Codice_C_2

Codice_C_2


Esempio

La successione di fibonacci

I termini della successione di Fibonacci sono definiti
dalla seguente relazione per ricorrenza
ao =1
a1 =1
an =f(an-1)+f(an-2) se n>1

Esempio
I primi 10 termini sono:
0, 1 , 1 , 2, 3, 5, 8, 13, 21, 34,…

In figura riportiamo una semplice procedura scritta nello pseudo-linguaggio pascal-like per il calcolo dei termini della successione di fibonacci mediante un approccio di tipo iterativo.

Ricorsione in Pascal

Ricorsione in Pascal


Esempio ricorsivo

La successione di fibonacci

I termini della successione di Fibonacci possono anche essere calcolati attraverso un approccio di tipo ricorsivo.
La modalità che sembra essere più naturale è una chiamata del tipo:

fibo=fibonacci(n-1)+fibonacci(n-2);

Questo approccio porta con se alcuni:

Vantaggi:

  • Compattezza nella scrittura di codice
  • Comodità implementativa

Svantaggi:
Questo approccio è computazionalmente proibitivo. Esso, per dirlo in termini poco rigorosi, genera una cascata di chiamate a funzioni che rende inaccettabili i tempi di calcolo già per n=50.

Tale considerazione è legata alla complessità computazionale dell’algoritmo che è O(1,61n) .

Esempio fibonacci ricorsivo vers. 1

La successione di fibonacci

L’algoritmo basato su una chiamata a funzione del tipo:

fibo=fibonacci(n-1)+fibonacci(n-2);

viene implementata nell’esercizio proposto i questa diapositiva. Si richiede di eseguire il codice per n=5,10,20,30,40,50 ed analizzare l’ attesa per una risposta che si ritiene in “tempo accettabile”.

Codice_C_3

Codice_C_3


Esempio fibonacci ricorsivo vers. 2

La successione di fibonacci

L’algoritmo proposto è sempre bastato su una complessità non polinomiale dell’ordine di O(1,61n) viene però inserita una variabile:

conta

che segnala quante chiamate a funzione sono state effettuate. Tale variabile è utile a mettere in evidenza l’impraticabilità dell’approccio proposto.

Codice_C_4

Codice_C_4


Esempio fibonacci ricorsivo vers. 2

La successione di fibonacci

L’algoritmo proposto è sempre bastato su una complessità Polinomiale dell’ordine di O(1,61n) viene però inserita una variabile:

conta

che segnala quante chiamate a funzione sono state effettuate. Tale variabile è utile a mettere in evidenza l’impraticabilità dell’approccio proposto.

Codice_C_5

Codice_C_5


Esempio ricorsivo cont.

La successione di fibonacci

I termini della successione di Fibonacci possono anche essere calcolati attraverso un approccio di tipo ricorsivo con complessità di tempo lineare ovvero O(n).
I trucco consiste nell’utilizzare due variabili chiamiamole

fd (termine di posto dispati) e fp ( termine di posto dispati)

che memorizzano due termini consecutivi della successione che sono già stati calcolati.
A questo punto basta effettuare una chiamata ricorsiva alla funzione che passi contemporaneamente i due argomenti sopra trattati e li aggiorni opportunamente. Più in dettaglio:

Nel programma principale:

fibonacci(n/2+1,fd,fp);

Nella funzione che si auto-richiama (caso base):

Se (n>1)

fibonacci(n-1,fd,fp);
fp=fd+fp;
fd=fp+fd;

Esempio fibonacci ricorsivo vers. 3

L’algoritmo proposto è bastato su una complessità
polinomiale dell’ordine di O(n) viene però inserita una variabile:

conta

che segnala quante chiamate a funzione sono state effettuate. E’ interessante comparare il numero adesso ottenuto con quello visto nella versione ricorsiva 2.

Codice_C_6

Codice_C_6


Esempio ricorsivo cont.

termini della successione di Fibonacci possono anche essere calcolati attraverso un approccio di tipo ricorsivo con complessità di tempo sub-lineare ovvero O(log(n)). Intenderemo con log(n) il logaritmo in base 2 di n.

Infatti per calcolare i numeri di Fibonacci di indice 2n e 2n-1 dai numeri di indice n ed n-1
si procede per induzione iterando la formula: Fi +1 = Fi + Fi -1 Vediamo come nel dettaglio:

Fi +1 = Fi + Fi -1
Fi +2 = Fi * 2 + Fi -1
Fi +3 = Fi * 3 + Fi -1* 2
Fi +4 = Fi * 5 + Fi -1* 3
Fi +j = Fi * Fj +1 + Fi -1* Fj = Fi * Fj + Fi * Fj -1 + Fi -1* Fj

Ponendo j uguale rispettivamente ad i ed i-1 si ottiene:

F2i = Fi * Fi + 2 * Fi * Fi -1
F2i -1 = Fi * F
i + Fi -1 * Fi -1

Esempio fibonacci ricorsivo vers. 4

L’algoritmo proposto è bastato su una complessità sub polinomiale dell’ordine di O(log(n)).

I numeri di Fibonacci sono calcolati a coppie:

Fib(n) e Fib(n-1)

Le formule ricorsive usate sono le seguenti :

F(2n ) = F(n) * F(n) + 2 * F(n) * F(n – 1)
F(2n -1) = F(n) * F(n) + F(n – 1) * F(n – 1)

Codice_C_7

Codice_C_7

Codice_C_8

Codice_C_8


Esempio fibonacci iterativo

L’algoritmo proposto è sempre bastato su una complessità sub polinomiale dell’ordine di O(log(n)). ma si propone un codice scritto in C che utilizza un approccio di tipo iterativo.

Codice_C_9

Codice_C_9

Codice_C_10

Codice_C_10


La torre di Hanoi

La torre di Hanoi

L’algoritmo consiste nello spostamento di una pila di dischi forati di dimensioni decrescenti da un piolo, in un secondo piolo, muovendo un disco alla volta in modo che un disco piu’ piccolo non stia sotto uno piu’ grande, un terzo piolo e’ usato come ausilio per i trasferimenti.

Torre di Hanoi ricorsiva

Per risolvere lo spostamento di una pila di n dischi si puo’

  • spostare la pila di n-1 dischi dal piolo iniziale al piolo ausiliario
  • spostare il disco n dal piolo iniziale al piolo destinazione
  • spostare la pila di n-1 dischi dal piolo ausiliario al piolo destinazione
Torre di Hanoi.

Torre di Hanoi.


La torre di Hanoi

La torre di Hanoi ricorsiva

Lo spostamento della pila di n dischi e’ stata ricondotta allo spostamento di 2 pile di n-1 dischi ( per ciascuna pila di n-1 dischi si puo’ ripetere la sequenza di operazioni). Ovvero:

hanoi(n,pioloIniziale,pioloDestinazione,pioloAusiliario){

if (n==1) muovi(n,pioloIniziale,pioloDestinazione);
else{

hanoi(n-1,pioloIniziale,pioloAusiliario,pioloDestinazione);
muovi(n,pioloIniziale,pioloDestinazione);
hanoi(n-1,pioloAusiliario,pioloDestinazione,pioloIniziale);

}

}

Esempio hanoi ricorsivo

Nel seguito si propone un algoritmo per il calcolo del numero di passi per spostare una pila di dischi
con una funzione ricorsiva implementato in linguaggio C.

Si osservi lo sviluppo di una funzione void muovi( ) che consente lo spostamento di un pezzo.

Codice_C_11

Codice_C_11

Codice_C_12

Codice_C_12


La torre di Hanoi

La torre di Hanoi iterativa

  • Si immaginano i pioli posti ai vertici di un triangolo equilatero in modo che una vista in senso orario veda i pioli nell’ordine 0,1,2,
  • Si comincia muovendo il disco piu’ piccolo, che successivamente viene spostato ad ogni mossa dispari (1,3,5,7,……)
  • il disco piu’ piccolo si muove in senso orario se il numero totale di dischi e’ dispari, altrimenti in senso antiorario
  • quando non si muove il disco piu’ piccolo, si effettua l’unica mossa possibile.

Nel seguito si propone una implementazione in linguaggio C della versione iterativa.

Codice_C_13

Codice_C_13

Codice_C_14

Codice_C_14


I materiali di supporto della lezione

Mario Livio, La Sezione Aurea, Storia di un numero e di un mistero che dura da tremila anni - Bur, 2003. ISBN 9788817872010

Esercizi

jsFibonacci

  • 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