Ricorsione

Se il linguaggio di programmazione prevede la ricorsione… una SUB A può chiamare la SUB A, se stessa, per svolgere lo stesso compito ma con un’stanza diversa

ricorsione

La SUB A chiama la SUB A … finché non succede qualcosa (l’istanza diventa un caso particolare che non necessita di un’ulteriore chiamata ricorsiva) e si ritorna all’indietro fino alla prima chiamata…

Procedura Funzione
Basic
C…
Pascal

Ricorsione indiretta

Nel caso di ricorsione indiretta il sottoprogramma chiama un secondo sottoprogramma che a sua volta … che a sua volta chiama il primo

La torre di Hanoi

Il problema

Nel tempio di Brahma si trova una piattaforma di ottone con tre perni di diamanti.
Sul primo di tali perni sono infilati 64 dischi d’oro, di dimensioni decrescenti, che formano una torre.
Si deve portare la torre sul terzo perno, spostando un solo disco alla volta e in modo che mai un disco di diametro maggiore si trovi sopra un disco di diametro minore.
Per risolvere la questione si può utilizzare il secondo perno come perno di servizio.

Quando i monaci termineranno l’opera il mondo sarà finito!

Analisi

Siano D1, D2, …, Dn le etichette dei dischi di una torre di Hanoi con n dischi.

n Prova! Analisi
1

Il problema con un solo disco è banale

  1. il disco è sinistra
  2. sposta il disco D1 dalla 1° alla 3° torre
2

Se i dischi sono 2 le mosse sono 3

  1. i dischi sono a sinistra
  2. sposta il disco D1 dalla 1° alla 2° torre
  3. sposta il disco D2 dalla 1° alla 3° torre
  4. sposta il disco D1 dalla 2° alla 3° torre
3

Se i dischi sono 3 le mosse sono 7

  1. i dischi sono a sinistra
  2. sposta il disco D1 dalla 1° alla 3° torre
  3. sposta il disco D2 dalla 1° alla 2° torre
  4. sposta il disco D1 dalla 3° alla 2° torre
  5. sposta il disco D3 dalla 1° alla 3° torre
  6. sposta il disco D1 dalla 2° alla 1° torre
  7. sposta il disco D2 dalla 2° alla 3° torre
  8. sposta il disco D1 dalla 1° alla 3° torre

Se i dischi sono 4, 5, … si può riconoscere lo schema risolutivo

  1. i dischi sono a sinistra
  2. sposta i dischi D1…Dn-1 dalla 1° alla 2° torre (usando la 3° come appoggio) in modo da liberare Dn
  3. sposta il disco Dn dalla 1° alla 3° torre
  4. sposta i dischi D1…Dn-1 dalla 2° alla 3° torre (usando la 1° come appoggio) sopra Dn

Algoritmo

Ad ogni passo è sufficiente specificare

  • il numero di dischi coinvolti, perché si parla sempre dei dischi in cima a una torre
  • il nome della torre di origine
  • il nome della torre di appoggio
  • il nome della torre di destinazione

allora l’algoritmo risolutivo per il problema

Hanoi(n, origine, appoggio, destinazione)

diventa

  1. Hanoi(n-1, origine, arrivo , appoggio)
  2. Hanoi(1, origine, appoggio, destinazione)
  3. Hanoi(n-1, appoggio, origine, destinazione)

con l’accortezza che nel caso di torre con un solo disco è sufficiente comunicare di spostare il disco dalla torre origine alla torre destinazione.

Prova!

La soluzione è costituita da una sequenza di coppie

a >> b

di spostamenti dalla torre a alla torre b.

La complessità dell'algoritmo

Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell'algoritmo è proporzionale al numero di spostamenti di dischi

  • T(1) = 1
  • T(2) = T(1)+T(1)+T(1) = 1+1+1 = 3
  • T(3) = T(2)+T(1)+T(2) = 3+1+3 = 7
  • T(4) = T(3)+T(1)+T(3) = 7+1+7 = 15
  • ...
  • T(n) = T(n-1)+T(1)+T(n-1) = 2*T(n-1)+1
  • ...

Numericamente si tratta della successione

1, 3, 7, 15, 31, 63, 127, ...

cioè

21-1, 22-1, 23-1, 24-1, 25-1, 26-1, 27-1, ...

quindi

T(n) = 2n-1

I tempi necessari per risolvere il problema sono

n T(n) = 2n-1 1 Hz (uomo) 1 GHz (PC)
1 21-1 = 1 un secondo 10-9 s
2 22-1 = 3 3 secondi 3*10-9 s
10 210-1 = 1023 ~17 minuti ~10-6 s
20 220-1 = 1.048.575 ~12 giorni ~10-3 s
30 230-1 = 1.073.741.823 ~34 anni ~1 s
64 264-1 = 18.446.744.073.709.551.615 ~5*1011 anni ~500 anni

Conclusioni

  • L'algoritmo per il problema della torre di Hanoi ha complessità in tempo asintotica esponenziale, O(2n)
  • Non può esistere un algoritmo con complessità minore
  • Il problema della torre di Hanoi è un problema intrinsecamente esponenziale
  • Il problema della torre di Hanoi è un problema intrattabile!

Quick sort

Un algoritmo di ordinamento

  • molto complicato: ricorsivo e difficile da ricordare
  • ma ottimo: è quasi sempre molto veloce…

Merge Sort

Algoritmo intuitivo e ottimo.
Utilizza l’algoritmo di fusione di sottosequenze ordinate.

La chiamata chiede di ordinare l’array dal primo, 1, all’ultimo, N, elemento.
A ogni chiamata, dopo aver calcolato Medio, si effettuano due chiamate ricorsive, da Inf a Medio e da Medio+1 a Sup.

In pratica le chiamate ricorsive scendono fino al livello di array con un solo elemento.
Al ritorno di ogni coppia di chiamate si effettua la fusione, merge, delle due parti ordinate (l’array con un solo elemento è già ordinato…).

ms1Esempio 1

Sia v={1, 3, 7, 4, 15, 0, 9, 10}

Le chiamate ricorsive sugli indici da 1 a 8 e con i valori medi successivi

  • (1+8)/2 = 4
  • (1+4)/2 = 2
  • (5+8)/2 = 6
  • (1+2)/2 = 1
  • (3+4)/2 = 3
  • (5+6)/2 = 5
  • (7+8)/2 = 7

hanno l’effetto di raggiungere i singoli elementi.

Con i valori effettivi, l’array dopo le chiamate ricorsive diventa una sequenza di 8 array con un elemento

ms11

Al ritorno di ogni due chiamate ricorsive avviene la fusione di due array ordinati…

ms12

ms2Esempio 2

Sia v={1, 3, 7, 4, 15, 0, 9, 10, 8, 2}

Le chiamate ricorsive sugli indici da 1 a 10 raggiungono i singoli elementi con 2 passaggi in più…

  • (1+10)/2 = 5
  • (1+5)/2 = 3
  • (6+10)/2 = 8
  • (1+3)/2 = 2
  • (4+5)/2 = 4
  • (6+8)/2 = 7
  • (9+10)/2 = 9
  • (1+2)/2 = 1
  • (6+7)/2 = 6.
Considerando i valori effettivi dell’array e l’esecuzione di tutti i passi…
ms22

Numeri di Fibonacci

I numeri di Fibonacci prendono il nome da una sfida matematica che Fibonacci lanciò a un suo collega.
Il problema tratta la proverbiale velocità con cui i conigli si riproducono:

  • il 1° mese è presente una coppia di conigli
  • una coppia di conigli diventa matura all’inizio del 2° mese di vita
  • la gestazione dura un mese
  • ogni parto produce una coppia maschio-femmina di conigli
  • ogni coppia di conigli sopravvive e si riproduce per sempre…

Calcolare il numero di coppie di conigli dopo 10 mesi.

Analisi

Tramite i pulsanti puoi osservare l’evoluzione della popolazione di conigli fino al sesto mese

Ogni mese sono presenti i conigli già presenti il mese precedente più quelli appena nati, che sono in numero uguale ai conigli presenti due mesi prima!

I numeri di Fibonacci sono proprio la successione 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … cioè il numero di coppie di conigli per ogni mese.

Al decimo mese ci saranno 55 coppie di conigli.

Algoritmo iterativo

A partire dai valori noti (1, 1) si calcola, mese dopo mese, un nuovo valore finché non si giunge al mese richiesto.

Per calcolare fibonacci(5) si seguono i passi

  1. fibonacci(1) = 1
  2. fibonacci(2) = 1
  3. fibonacci(3) = fibonacci(2)+fibonacci(1) = 1+1 = 2
  4. fibonacci(4) = fibonacci(3)+fibonacci(2) = 2+1 = 3
  5. fibonacci(5) = fibonacci(4)+fibonacci(3) = 3+2 = 5

Algoritmo ricorsivo

La formulazione ricorsiva dei numeri di Fibonacci è molto comoda perché sintetica

f(n)=\left \{ \begin{array}{ll} 1 & n=1,2 \\ f(n-1)+f(n-2) & n>2 \end{array}

Esempio: fibonacci(5) = fibonacci(4)+fibonacci(3) = (fibonacci(3)+fibonacci(2))+(fibonacci(2)+fibonacci(1)) = ((fibonacci(2)+fibonacci(1))+1)+(1+1) = ((1+1)+1)+(1+1) = 5

Con formula!

Non è necessario alcun algoritmo iterativo o ricorsivo se si utilizza la formula

f(n)=\frac{1}{\sqr{5}} \left [\left (\frac{1+\sqr{5}}{2} \right )^n-\left( \frac{1-\sqr{5}}{2} \right )^n \right ]

Il contributo del secondo termine è così piccolo che può essere trascurato.
Calcola il primo termine e considera l’intero più vicino (arrotonda).

Esercizi

  1. Calcola la somma dei primi n numeri di Fibonacci.
    Visualizza i passi compiuti con una tabella per n da 1 a

    n f(n) Somma
    1 1 1
    2 1 2
    3 2 4
    4 3 7
    5 5 12
    6 8 20
  2. Quanto vale il rapporto tra due numeri di Fibonacci consecutivi?
    Prova per n crescente finché non raggiungi un’approssimazione adeguata

    n f(n) (n+1)°/n° n°/(n+1)°
    1 1
    1 1 1 1
    2 1 2 0,5
    3 2 1,5 0,6…
    4 3 1,6… 0,625
    5 5 1,625 0,6153…
    1,6180339… 0,6180339…

Complessità degli algoritmi

Dopo aver analizzato il problema e individuati i 3 algoritmi discutiamo la loro complessità in tempo.

Algoritmo ricorsivo: il tempo di attesa può essere considerato proporzionale al numero di chiamate ricorsive

  • T(1) = 1
  • T(2) = 1
  • T(3) = 1+T(2)+T(1) = 1+1+1 = 3 > 22-1
  • T(4) = 1+T(3)+T(2) = 1+3+1 = 5 > 22-1
  • T(5) = 1+T(4)+T(3) = 1+5+3 = 9 > 23-1
  • T(6) = 1+T(5)+T(4) = 1+9+5 = 15 > 23-1
  • T(7) = 1+T(6)+T(5) = 1+15+9 = 25 > 24-1
  • T(8) = 1+T(7)+T(6) = 1+25+15 = 41 > 24-1
  • T(n) ≥ 2n/2-1.

Il tempo di attesa è maggiore di un tempo esponenziale, anche se con esponente n/2 piuttosto che n, quindi per n molto grande

T(n) ∈ O(2n).

L’algoritmo ricorsivo per il calcolo dell’n-simo numero di Fibonacci ha complessità esponenziale!

Algoritmo iterativo: si tratta di un algoritmo con un’iterazione semplice, senza chiamate ricorsive, quindi

  • T(n)=c1+c2n
  • T(n) ∈ O(n).

L’algoritmo iterativo per il calcolo dell’n-simo numero di Fibonacci ha complessità lineare!

Con formula: se consideriamo costante il tempo necessario per svolgere le singole operazioni presenti nella formula allora

  • T(n)=c
  • T(n) ∈ O(1).

Se consideriamo che per n molto grande l’operazione di elevamento a potenza potrebbe dipendere dal numero di cifre e che il numero di cifre del risultato cresce proporzionalmente al log di n allora si ottiene una complessità O(log n).

Conclusioni: per il calcolo dell’n-esimo numero di Fibonacci esistono diversi algoritmi con complessità diverse. Al variare di n utilizzeremo l’algoritmo più conveniente!