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.
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
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
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
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
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
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
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
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 * Fi + 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_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_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.
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_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_14
Le lezioni del Corso
1. Prolusione
2. Sistemi Operativi – parte prima
3. Sistemi Operativi – parte seconda
6. Il linguaggio C – parte prima
8. Il linguaggio C – funzioni e puntatori
10. Il linguaggio C – parte terza
11. La documentazione del software
12. Dati strutturati
13. Esercizi sui dati strutturati
14. Approfondimenti di C, Stringhe e file
15. Esercizi su stringhe e file
16. La ricorsione
17. Il linguaggio c++ parte prima
18. Il linguaggio C++ - parte seconda
19. Strutture dati di tipo astratto
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
