Esercizi · Ricorsione¶

Esercizi · Capitolo 14 · ogni soluzione si apre con un clic · Capitolo 14: Ricorsione · Eserciziario, volume 5 (PDF)

Negli esercizi di questo capitolo i passi di un algoritmo ricorsivo si contano con le convenzioni dei capitoli «Tempo di esecuzione» e «Ricorsione», e le equazioni di ricorrenza si risolvono per semplice srotolamento.

Ogni esecuzione di una riga numerata di pseudocodice è un passo; una riga che contiene una chiamata ricorsiva conta come un passo più tutti i passi eseguiti da quella chiamata.
\(C(n)\) indica il numero di chiamate (nodi dell'albero delle chiamate ricorsive) e \(S(n)\) il numero di passi; la profondità della ricorsione è il massimo numero di nodi su un cammino dalla radice a una foglia dell'albero, cioè il massimo numero di stack frame simultaneamente in memoria.
Induzione forte: se \(P(n_0)\) è vera e, per ogni \(n>n_0\), la verità di \(P(k)\) per ogni \(k\) con \(n_0\le k<n\) implica la verità di \(P(n)\), allora \(P(n)\) è vera per ogni \(n\ge n_0\).
Srotolamento di un'equazione di ricorrenza \(S(n)=S(n-1)+c\) con \(c\) costante:

\[ S(n)=S(n-1)+c=S(n-2)+2c=\cdots=S(n-k)+k\,c, \]

e il caso base si raggiunge per il valore di \(k\) che rende \(n-k\) un caso base.

Esercizio 14.1: Ricorsione (E1)

Si consideri il seguente algoritmo ricorsivo.

Algoritmo: Mystery

Input: Un numero naturale \(n \ge 1\)

Output: Un numero naturale

1function Mystery(n)

2if \(n = 1\) then

3return \(1\)

4end

5return Mystery\((\lfloor n/2 \rfloor)\) \(+\) Mystery\((\lceil n/2 \rceil)\)

6end

Domande

Disegnare l'albero delle chiamate ricorsive di Mystery\((6)\), scrivendo accanto a ogni chiamata il valore che restituisce.
Che cosa calcola l'algoritmo? Dimostrare l'affermazione per induzione forte su \(n\).
Sia \(C(n)\) il numero di chiamate eseguite da Mystery\((n)\). Scrivere un'equazione di ricorrenza per \(C(n)\) e dimostrare che \(C(n) = 2n - 1\) per ogni \(n \ge 1\). Verificare la formula sull'albero della domanda 1.
Qual è la profondità della ricorsione di Mystery\((6)\), cioè il massimo numero di stack frame simultaneamente in memoria?

Soluzione

Si ha \(\lfloor 6/2 \rfloor = \lceil 6/2 \rceil = 3\), \(\lfloor 3/2 \rfloor = 1\), \(\lceil 3/2 \rceil = 2\) e \(\lfloor 2/2 \rfloor = \lceil 2/2 \rceil = 1\). L'albero delle chiamate ricorsive (valori restituiti in rosso) è:

Mystery\((2)\) restituisce \(1+1 = 2\), Mystery\((3)\) restituisce \(1 + 2 = 3\) e Mystery\((6)\) restituisce \(3 + 3 = 6\).
L'algoritmo restituisce \(n\) stesso (calcola \(n\) come somma di \(n\) uni).

Dimostrazione per induzione forte su \(n \ge 1\).
- Caso base (\(n=1\)): l'algoritmo restituisce \(1\) alla riga 3.
- Passo induttivo (\(n \ge 2\)): supponiamo che Mystery\((k)\) restituisca \(k\) per ogni \(1 \le k < n\). Per \(n \ge 2\) si ha \(1 \le \lfloor n/2 \rfloor \le \lceil n/2 \rceil < n\), quindi per ipotesi induttiva la riga 5 restituisce
  
  \[ \lfloor n/2 \rfloor + \lceil n/2 \rceil = n. \]
L'induzione forte è necessaria perché le chiamate ricorsive sono su \(\lfloor n/2 \rfloor\) e \(\lceil n/2 \rceil\), non su \(n-1\).
Ogni chiamata con \(n \ge 2\) effettua due chiamate ricorsive, quindi

\[ C(n) = \begin{cases} 1 & \text{se } n = 1 \\ 1 + C(\lfloor n/2 \rfloor) + C(\lceil n/2 \rceil) & \text{se } n \ge 2 \end{cases} \]

Dimostrazione di \(C(n) = 2n - 1\) per induzione forte su \(n\).
- Caso base (\(n=1\)): \(C(1) = 1 = 2 \cdot 1 - 1\).
- Passo induttivo (\(n \ge 2\)): per ipotesi induttiva,
  
  \[ C(n) = 1 + \big(2\lfloor n/2 \rfloor - 1\big) + \big(2\lceil n/2 \rceil - 1\big) = 2\big(\lfloor n/2 \rfloor + \lceil n/2 \rceil\big) - 1 = 2n - 1. \]
Per \(n = 6\): \(C(6) = 11\), e infatti l'albero della domanda 1 ha \(11\) nodi. (L'albero ha \(n = 6\) foglie, una per ciascun \(1\) della somma, e \(n - 1 = 5\) nodi interni, uno per ciascuna addizione.)
I cammini più lunghi dalla radice a una foglia sono, per esempio, Mystery\((6)\), Mystery\((3)\), Mystery\((2)\), Mystery\((1)\). Quindi la profondità della ricorsione è \(4\): al più \(4\) stack frame sono simultaneamente in memoria, benché vengano eseguite \(11\) chiamate. (In generale la profondità è \(\lceil \log_2 n \rceil + 1\).)

Esercizio 14.2: Ricorsione (E2)

Dato un array \(a[1..n]\) di \(n\) numeri interi, si considerino i problemi di calcolare

la somma \(a[1] + a[2] + \dots + a[n]\) (uguale a \(0\) se \(n = 0\));
il valore massimo \(\max\{a[1], a[2], \dots, a[n]\}\) (per \(n \ge 1\)).

Per le domande numeriche si usi l'array \(a = [3, 8, 1, 6]\).

Domande

Scrivere un algoritmo ricorsivo RecSum\((a, n)\) che calcola la somma di \(a[1..n]\) riducendo il problema al sotto-array \(a[1..n-1]\) (decremento di uno).
Scrivere un algoritmo ricorsivo RecMax\((a, n)\) che calcola il massimo di \(a[1..n]\) riducendo il problema al sotto-array \(a[1..n-1]\).
Mostrare la sequenza di chiamate e di ritorni di RecSum\((a, 4)\) e di RecMax\((a, 4)\) per \(a = [3, 8, 1, 6]\).
Dimostrare la correttezza di RecMax per induzione su \(n\).
Scrivere le equazioni di ricorrenza del numero di passi \(S(n)\) dei due algoritmi, risolverle per srotolamento e indicare la profondità della ricorsione.

Soluzione

La somma di \(a[1..n]\) è la somma di \(a[1..n-1]\) più \(a[n]\), e la somma di un array vuoto è \(0\):

Algoritmo: RecSum

Input: Un array \(a[1..n]\) di \(n \ge 0\) numeri interi

Output: La somma \(a[1] + \dots + a[n]\)

1function RecSum(a, n)

2if \(n = 0\) then

3return \(0\)

4end

5return RecSum\((a, n-1) + a[n]\)

6end
Il massimo di \(a[1..n]\) è il maggiore tra il massimo di \(a[1..n-1]\) e \(a[n]\); il massimo di un singolo elemento \(a[1]\) è \(a[1]\):

Algoritmo: RecMax

Input: Un array \(a[1..n]\) di \(n \ge 1\) numeri interi

Output: Il valore massimo in \(a[1..n]\)

1function RecMax(a, n)

2if \(n = 1\) then

3return \(a[1]\)

4end

5\(m :=\) RecMax\((a, n-1)\)

6if \(a[n] > m\) then

7return \(a[n]\)

8end

9return \(m\)

10end

Per \(a = [3, 8, 1, 6]\):

RecSum\((a,4)\): chiamate

\[ \texttt{RecSum}(a,4) \to \texttt{RecSum}(a,3) \to \texttt{RecSum}(a,2) \to \texttt{RecSum}(a,1) \to \texttt{RecSum}(a,0), \]

poi i ritorni:

chiamata	restituisce
`RecSum`\((a,0)\)	\(0\) (caso base)
`RecSum`\((a,1)\)	\(0 + a[1] = 0 + 3 = 3\)
`RecSum`\((a,2)\)	\(3 + a[2] = 3 + 8 = 11\)
`RecSum`\((a,3)\)	\(11 + a[3] = 11 + 1 = 12\)
`RecSum`\((a,4)\)	\(12 + a[4] = 12 + 6 = 18\)

RecMax\((a,4)\): chiamate RecMax\((a,4) \to\) RecMax\((a,3) \to\) RecMax\((a,2) \to\) RecMax\((a,1)\), poi i ritorni:

chiamata	confronto	restituisce
`RecMax`\((a,1)\)	– (caso base)	\(a[1] = 3\)
`RecMax`\((a,2)\)	\(m = 3\), \(a[2] = 8 > 3\)	\(8\)
`RecMax`\((a,3)\)	\(m = 8\), \(a[3] = 1 \le 8\)	\(8\)
`RecMax`\((a,4)\)	\(m = 8\), \(a[4] = 6 \le 8\)	\(8\)

La somma è \(18\) e il massimo è \(8\).

Affermazione: per ogni \(n \ge 1\), RecMax\((a,n)\) restituisce \(\max\{a[1], \dots, a[n]\}\).
- Caso base (\(n=1\)): l'algoritmo restituisce \(a[1] = \max\{a[1]\}\) alla riga 3.
- Passo induttivo (\(n \ge 2\)): per ipotesi induttiva, la riga 5 assegna
  
  \[ m = \max\{a[1],\dots,a[n-1]\}. \]
  
  Se \(a[n] > m\), allora \(a[n]\) è maggiore di tutti gli elementi di \(a[1..n-1]\) e l'algoritmo restituisce \(a[n] = \max\{a[1],\dots,a[n]\}\) (riga 7). Altrimenti \(a[n] \le m\) e l'algoritmo restituisce \(m = \max\{a[1],\dots,a[n]\}\) (riga 9).
RecSum. \(S(0) = 2\) (righe 2–3) e, per \(n \ge 1\), le righe 2 e 5 più la chiamata ricorsiva:

\[ S(n) = S(n-1) + 2 = S(n-2) + 2 \cdot 2 = \dots = S(0) + 2n = 2n + 2 = \Theta(n). \]

RecMax. \(S(1) = 2\) (righe 2–3) e, per \(n \ge 2\), le righe 2, 5, 6 e una delle righe 7, 9, più la chiamata ricorsiva:

\[ S(n) = S(n-1) + 4 = S(n-2) + 2 \cdot 4 = \dots = S(1) + 4(n-1) = 4n - 2 = \Theta(n). \]

Per \(n = 4\): \(S(4) = 10\) per RecSum e \(S(4) = 14\) per RecMax.

La profondità della ricorsione è \(n+1\) per RecSum (chiamate su \(n, n-1, \dots, 0\)) e \(n\) per RecMax (chiamate su \(n, \dots, 1\)): entrambi usano una memoria \(\Theta(n)\) per il call stack, mentre le versioni iterative (come FindMaximum nel capitolo «Tempo di esecuzione») usano memoria costante.

Se tutti gli elementi usano un numero costante di bit (\(|I| = \Theta(n)\)), il tempo di esecuzione nel caso peggiore sia di RecSum sia di RecMax è \(T(|I|) = \Theta(|I|)\).

Esercizio 14.3: Ricorsione (E3)

Un array \(a[1..n]\) è un palindromo se si legge allo stesso modo da sinistra a destra e da destra a sinistra, cioè \(a[i] = a[n+1-i]\) per ogni \(i \in \{1, 2, \dots, n\}\). Si consideri il seguente algoritmo ricorsivo, chiamato sull'intero array come IsPalindrome\((a, 1, n)\).

Algoritmo: IsPalindrome

Input: Un array \(a\) e due indici \(l, r\)

Output: true se il sotto-array \(a[l..r]\) è un palindromo, false altrimenti

1function IsPalindrome(a, l, r)

2if \(l \ge r\) then

3return true

4end

5if \(a[l] \ne a[r]\) then

6return false

7end

8return IsPalindrome\((a, l+1, r-1)\)

9end

Domande

Mostrare la sequenza di chiamate di IsPalindrome\((a,1,5)\) per gli array \(a = [1, 2, 3, 2, 1]\) e \(a = [1, 2, 3, 3, 1]\).
Dimostrare per induzione sulla lunghezza \(k = r - l + 1\) del sotto-array che l'algoritmo è corretto.
Determinare il numero di passi \(S(n)\) nel caso peggiore di IsPalindrome\((a,1,n)\) e la sua profondità di ricorsione.
L'algoritmo è ricorsivo in coda? In caso affermativo, scrivere l'algoritmo iterativo equivalente.
Scrivere un algoritmo ricorsivo Reverse\((a, l, r)\) che inverte sul posto il sotto-array \(a[l..r]\), e mostrarne l'esecuzione su \(a = [5, 7, 2, 9, 4, 6]\) con \(l = 1\), \(r = 6\).

Soluzione

Per \(a = [1, 2, 3, 2, 1]\):

chiamata	\(a[l]\)	\(a[r]\)	azione
`IsPalindrome`\((a,1,5)\)	\(1\)	\(1\)	uguali \(\Rightarrow\) richiama `IsPalindrome`\((a,2,4)\)
`IsPalindrome`\((a,2,4)\)	\(2\)	\(2\)	uguali \(\Rightarrow\) richiama `IsPalindrome`\((a,3,3)\)
`IsPalindrome`\((a,3,3)\)	–	–	\(l \ge r\) \(\Rightarrow\) restituisce true

Il valore true viene restituito invariato da tutte le chiamate (\(3\) chiamate).

Per \(a = [1, 2, 3, 3, 1]\):

chiamata	\(a[l]\)	\(a[r]\)	azione
`IsPalindrome`\((a,1,5)\)	\(1\)	\(1\)	uguali \(\Rightarrow\) richiama `IsPalindrome`\((a,2,4)\)
`IsPalindrome`\((a,2,4)\)	\(2\)	\(3\)	diversi \(\Rightarrow\) restituisce false

Viene restituito il valore false (\(2\) chiamate).

Sia \(k = r - l + 1\) la lunghezza di \(a[l..r]\) (\(k \le 0\) significa sotto-array vuoto). Dimostriamo per induzione forte su \(k\) che l'algoritmo restituisce true se e solo se \(a[l..r]\) è un palindromo.
- Casi base (\(k \le 1\), cioè \(l \ge r\)): un array vuoto o con un solo elemento è un palindromo, e l'algoritmo restituisce true alla riga 3.
- Passo induttivo (\(k \ge 2\)): \(a[l..r]\) è un palindromo se e solo se \(a[l] = a[r]\) e il sotto-array interno \(a[l+1..r-1]\) è un palindromo. Se \(a[l] \ne a[r]\), l'algoritmo restituisce correttamente false (riga 6). Altrimenti restituisce il risultato della chiamata su \(a[l+1..r-1]\), la cui lunghezza è \(k-2 < k\); per ipotesi induttiva, questo risultato è true se e solo se \(a[l+1..r-1]\) è un palindromo, quindi se e solo se \(a[l..r]\) è un palindromo.
La lunghezza diminuisce di \(2\) a ogni chiamata, ed è per questo che sia \(k=0\) sia \(k=1\) devono essere casi base.
Il caso peggiore si ha quando l'array è un palindromo (la ricorsione non viene mai fermata alla riga 6). Ogni chiamata con \(l < r\) esegue le righe 2, 5 e 8 (\(3\) passi), e l'ultima chiamata esegue le righe 2–3 (\(2\) passi). In funzione della lunghezza \(k\):

\[ S(k) = S(k-2) + 3 \quad (k \ge 2), \qquad S(0) = S(1) = 2. \]

Srotolando, dopo \(\lfloor k/2 \rfloor\) passaggi si raggiunge \(S(0)\) oppure \(S(1)\):

\[ S(n) = 3\lfloor n/2 \rfloor + 2 = \Theta(n). \]

L'algoritmo effettua \(\lfloor n/2 \rfloor + 1\) chiamate, che è anche la profondità della ricorsione (l'albero è un cammino). Per \(n = 5\): \(3\) chiamate, come nella domanda 1, e \(S(5) = 8\).
Sì: la chiamata ricorsiva alla riga 8 è l'ultima operazione e il suo risultato viene restituito invariato. Sostituendo la chiamata in coda con l'aggiornamento \((l, r) \leftarrow (l+1, r-1)\) otteniamo:

Algoritmo: IterativeIsPalindrome

Input: Un array \(a[1..n]\)

Output: true se \(a\) è un palindromo, false altrimenti

1function IterativeIsPalindrome(a, n)

2\(l := 1\)

3\(r := n\)

4while \(l < r\) do

5if \(a[l] \ne a[r]\) then

6return false

7end

8\(l \leftarrow l + 1\)

9\(r \leftarrow r - 1\)

10end

11return true

12end

Usa una memoria costante invece di una pila di profondità \(\lfloor n/2 \rfloor + 1\).

Per invertire \(a[l..r]\): si scambiano i due elementi estremi, poi si inverte il sotto-array interno \(a[l+1..r-1]\). Un sotto-array con al più un elemento è già invertito (caso base, non c'è nulla da fare).

Algoritmo: Reverse

Input: Un array \(a\) e due indici \(l, r\)

Output: Il sotto-array \(a[l..r]\) invertito sul posto

1function Reverse(a, l, r)

2if \(l < r\) then

3scambia \(a[l]\) e \(a[r]\)

4Reverse\((a, l+1, r-1)\)

5end

6end

Esecuzione su \(a = [5, 7, 2, 9, 4, 6]\):

chiamata	azione	array dopo lo scambio della chiamata
`Reverse`\((a,1,6)\)	scambia \(a[1]=5\), \(a[6]=6\)	\([6, 7, 2, 9, 4, 5]\)
`Reverse`\((a,2,5)\)	scambia \(a[2]=7\), \(a[5]=4\)	\([6, 4, 2, 9, 7, 5]\)
`Reverse`\((a,3,4)\)	scambia \(a[3]=2\), \(a[4]=9\)	\([6, 4, 9, 2, 7, 5]\)
`Reverse`\((a,4,3)\)	\(l \ge r\): caso base, nulla da fare	\([6, 4, 9, 2, 7, 5]\)

L'array finale è \([6, 4, 9, 2, 7, 5]\), dopo \(\lfloor 6/2 \rfloor + 1 = 4\) chiamate e \(3\) scambi. La correttezza segue per induzione su \(k = r - l + 1\) esattamente come nella domanda 2.

Esercizio 14.4: Ricorsione (E4)

Si consideri l'algoritmo ricorsivo ingenuo per i numeri di Fibonacci (\(F(0) = 0\), \(F(1) = 1\), \(F(n) = F(n-1) + F(n-2)\) per \(n \ge 2\)).

Algoritmo: Fib

Input: Un numero naturale \(n\)

Output: Il numero di Fibonacci \(F(n)\)

1function Fib(n)

2if \(n \le 1\) then

3return \(n\)

4end

5return Fib\((n-1)\) \(+\) Fib\((n-2)\)

6end

Domande

Disegnare l'albero delle chiamate ricorsive di Fib\((6)\) e calcolare il valore restituito.
Contare il numero di chiamate \(C(6)\) e verificare la formula \(C(n) = 2F(n+1) - 1\).
Quante volte viene chiamata Fib\((k)\), per ogni \(k = 0, 1, \dots, 6\), durante il calcolo di Fib\((6)\)? Che cosa si osserva?
Confrontare il numero di passi di Fib (\(S(n) = 4F(n+1) - 2\)) con il numero di passi di IterativeFib (\(S(n) = 5n + 1\)) per \(n = 6\) e per \(n = 20\).
Qual è la profondità della ricorsione di Fib\((6)\)?

Soluzione

L'albero delle chiamate ricorsive di Fib\((6)\) (scriviamo F\(k\) per Fib\((k)\)):

Risalendo dalle foglie alla radice: Fib\((2) = 1 + 0 = 1\), Fib\((3) = 1 + 1 = 2\), Fib\((4) = 2 + 1 = 3\), Fib\((5) = 3 + 2 = 5\), Fib\((6) = 5 + 3 = 8\). Quindi \(F(6) = 8\).
Contando i nodi dell'albero livello per livello: \(1 + 2 + 4 + 8 + 8 + 2 = 25\). La formula dà

\[ C(6) = 2F(7) - 1 = 2 \cdot 13 - 1 = 25. \]

Equivalentemente, dall'equazione di ricorrenza \(C(n) = C(n-1) + C(n-2) + 1\) con \(C(0) = C(1) = 1\): \(C(2) = 3\), \(C(3) = 5\), \(C(4) = 9\), \(C(5) = 15\), \(C(6) = 15 + 9 + 1 = 25\).
Contando i nodi con la stessa etichetta:

\(k\) 6 5 4 3 2 1 0 totale

numero di chiamate Fib\((k)\) 1 1 2 3 5 8 5 25

I numeri di chiamate sono essi stessi numeri di Fibonacci: Fib\((k)\) viene chiamata \(F(7-k)\) volte per \(k \ge 1\) (e Fib\((0)\) viene chiamata \(F(5)\) volte, una per ogni chiamata Fib\((2)\)). Gli stessi sottoproblemi vengono risolti più e più volte: per esempio \(F(2)\) viene calcolato \(5\) volte, mentre basterebbe calcolarlo una volta e memorizzarlo. Questa è la motivazione della Programmazione Dinamica.

Il numero di chiamate e di passi dei due algoritmi è:

\(n\)	chiamate \(C(n) = 2F(n+1)-1\)	passi di `Fib`: \(4F(n+1) - 2\)	passi di `IterativeFib`: \(5n+1\)
\(6\)	\(2 \cdot 13 - 1 = 25\)	\(4 \cdot 13 - 2 = 50\)	\(31\)
\(20\)	\(2 \cdot 10946 - 1 = 21891\)	\(4 \cdot 10946 - 2 = 43782\)	\(101\)

Per \(n = 6\) i due algoritmi sono confrontabili, ma per \(n = 20\) l'algoritmo ingenuo esegue più di \(400\) volte il numero di passi di quello iterativo: il primo cresce esponenzialmente, il secondo linearmente.

Il cammino più lungo dalla radice a una foglia è Fib\((6)\), Fib\((5)\), Fib\((4)\), Fib\((3)\), Fib\((2)\), Fib\((1)\): la profondità della ricorsione è \(6\). Benché vengano eseguite \(25\) chiamate, al più \(6\) stack frame sono simultaneamente in memoria.

Esercizio 14.5: Ricorsione (E5)

Si considerino le Torri di Hanoi con \(n = 4\) dischi, numerati \(1, 2, 3, 4\) dal più piccolo al più grande, inizialmente sul piolo \(A\), da spostare sul piolo \(C\) usando il piolo \(B\) come piolo ausiliario, con l'algoritmo ricorsivo:

Algoritmo: Hanoi

Input: Il numero di dischi \(n \ge 1\), i pioli \(from\), \(to\), \(aux\)

Output: La sequenza di mosse che trasferisce i dischi \(1,2,\dots,n\) da \(from\) a \(to\)

1function Hanoi(n, from, to, aux)

2if \(n = 1\) then

3sposta il disco \(1\) da \(from\) a \(to\)

4else

5Hanoi\((n-1, from, aux, to)\)

6sposta il disco \(n\) da \(from\) a \(to\)

7Hanoi\((n-1, aux, to, from)\)

8end

9end

Domande

Elencare, in ordine, tutte le mosse eseguite da Hanoi\((4, A, C, B)\).
Verificare che il numero di mosse è \(M(4) = 2^4 - 1\).
Quante volte viene spostato ciascun disco? Dimostrare che, con \(n\) dischi, il disco \(k\) viene spostato esattamente \(2^{n-k}\) volte (\(\forall k \in \{1, 2, \dots, n\}\)), e verificare che \(\sum_{k=1}^{n} 2^{n-k} = 2^n - 1\).
Quante chiamate di Hanoi vengono eseguite per \(n = 4\), e qual è la profondità della ricorsione?
Secondo la leggenda, \(n = 64\) dischi d'oro vengono spostati alla velocità di una mossa al secondo. Quanto tempo ci vuole?

Soluzione

Hanoi\((4, A, C, B)\) esegue Hanoi\((3, A, B, C)\), poi sposta il disco \(4\) da \(A\) a \(C\), poi esegue Hanoi\((3, B, C, A)\). Ogni chiamata con \(n = 3\) effettua \(7\) mosse (secondo lo stesso schema di Hanoi\((3, A, C, B)\) nel capitolo, con i pioli rinominati):

mossa disco da a mossa disco da a

1 1 A B 9 1 B C

2 2 A C 10 2 B A

3 1 B C 11 1 C A

4 3 A B 12 3 B C

5 1 C A 13 1 A B

6 2 C B 14 2 A C

7 1 A B 15 1 B C

8 4 A C

Le mosse \(1\)–\(7\) trasferiscono i dischi \(1,2,3\) da \(A\) a \(B\) (chiamata Hanoi\((3,A,B,C)\)), la mossa \(8\) sposta il disco più grande, e le mosse \(9\)–\(15\) trasferiscono i dischi \(1,2,3\) da \(B\) a \(C\) (chiamata Hanoi\((3,B,C,A)\)).
Ci sono \(15\) mosse e \(2^4 - 1 = 15\). Equivalentemente, \(M(1) = 1\), \(M(2) = 2 \cdot 1 + 1 = 3\), \(M(3) = 2 \cdot 3 + 1 = 7\), \(M(4) = 2 \cdot 7 + 1 = 15\).
Dalla tabella: il disco \(1\) viene spostato \(8\) volte, il disco \(2\) viene spostato \(4\) volte, il disco \(3\) viene spostato \(2\) volte e il disco \(4\) viene spostato una volta; sono \(2^{4-1}, 2^{4-2}, 2^{4-3}, 2^{4-4}\).

Dimostrazione per induzione su \(n\) che, in Hanoi\((n, \cdot, \cdot, \cdot)\), il disco \(k\) viene spostato \(2^{n-k}\) volte per ogni \(k \in \{1, 2, \dots, n\}\).
- Caso base (\(n = 1\)): il disco \(1\) viene spostato una volta \(= 2^{1-1}\).
- Passo induttivo (\(n \ge 2\)): il disco \(n\) viene spostato solo dalla chiamata stessa, una volta \(= 2^{n-n}\). Un disco \(k \le n-1\) viene spostato solo all'interno delle due chiamate ricorsive con \(n-1\) dischi, e per ipotesi induttiva viene spostato \(2^{(n-1)-k}\) volte in ciascuna di esse: in totale \(2 \cdot 2^{n-1-k} = 2^{n-k}\) volte.
Sommando su tutti i dischi (somma geometrica),

\[ \sum_{k=1}^{n} 2^{n-k} = 2^{n-1} + 2^{n-2} + \dots + 2 + 1 = 2^n - 1 = M(n). \]

Per \(n=4\): \(8 + 4 + 2 + 1 = 15\).
Ogni chiamata esegue esattamente una mossa (il caso base sposta il disco \(1\), le altre chiamate spostano il disco \(n\)), quindi il numero di chiamate è uguale al numero di mosse: \(15\) chiamate. L'albero delle chiamate ricorsive è un albero binario completo con \(4\) livelli (\(1 + 2 + 4 + 8 = 15\) nodi), quindi la profondità della ricorsione è \(4\).
\(M(64) = 2^{64} - 1 = 18\,446\,744\,073\,709\,551\,615\) mosse, cioè lo stesso numero di secondi. Un anno ha circa \(365.25 \cdot 24 \cdot 3600 = 31\,557\,600\) secondi, quindi il tempo è

\[ \frac{2^{64}-1}{31\,557\,600} \approx 5.85 \cdot 10^{11} \text{ anni}, \]

circa \(585\) miliardi di anni (più di \(40\) volte l'età dell'universo). Poiché il numero di mosse di Hanoi è ottimo, nessun algoritmo può fare meglio.

Esercizio 14.6: Ricorsione (E6)

Si considerino i due algoritmi ricorsivi seguenti: FastPower calcola \(x^n\) per elevamento al quadrato, ToBinary stampa la rappresentazione binaria di un numero naturale \(n\).

Algoritmo

Algoritmo: FastPower

Input: Un numero \(x\) e un numero naturale \(n\)

Output: La potenza \(x^n\)

1function FastPower(x, n)

2if \(n = 0\) then

3return \(1\)

4end

5\(y :=\) FastPower\((x, \lfloor n/2 \rfloor)\)

6if \(n \bmod 2 = 0\) then

7return \(y \cdot y\)

8else

9return \(x \cdot y \cdot y\)

10end

11end

Algoritmo: ToBinary

Input: Un numero naturale \(n\)

Output: Le cifre binarie di \(n\), stampate a partire dalla più significativa

1function ToBinary(n)

2if \(n \le 1\) then

3stampa \(n\)

4else

5ToBinary\((\lfloor n/2 \rfloor)\)

6stampa \(n \bmod 2\)

7end

8end

Domande

Mostrare la sequenza di chiamate di FastPower\((x, 25)\) e contare il numero di moltiplicazioni. Confrontare con l'algoritmo ingenuo, che esegue \(n\) moltiplicazioni.
Calcolare il numero di moltiplicazioni e il numero di passi \(S(n) = 4\lfloor \log_2 n \rfloor + 6\) di FastPower per \(n = 31\), \(n = 32\) e \(n = 100\).
Uno studente sostituisce la riga \(y :=\) FastPower\((x, \lfloor n/2 \rfloor)\) e le righe seguenti con

\[ \textbf{return } \texttt{FastPower}(x, \lfloor n/2 \rfloor) \cdot \texttt{FastPower}(x, \lfloor n/2 \rfloor) \quad (\text{per } x \text{ se } n \text{ è dispari}). \]

Scrivere l'equazione di ricorrenza del numero di chiamate \(C(n)\) di questa versione, calcolare \(C(13)\) e \(C(16)\), e mostrare che \(C(n) = \Theta(n)\).
Mostrare l'esecuzione di ToBinary\((37)\): chiamate, cifre stampate e numero di chiamate. Perché le cifre vengono stampate nell'ordine corretto, mentre l'algoritmo ChangeOfBase (capitolo «Algoritmi numerici») le produce a partire dalla meno significativa?
Dimostrare per induzione forte che ToBinary\((n)\) stampa la rappresentazione binaria di \(n\), e che esegue \(\lfloor \log_2 n \rfloor + 1\) chiamate per \(n \ge 1\).

Soluzione

Gli esponenti delle chiamate sono \(25, 12, 6, 3, 1, 0\). Risalendo dal caso base:

chiamata	\(y\)	restituisce	moltiplicazioni
`FastPower`\((x, 0)\)	–	\(1\) (caso base)	\(0\)
`FastPower`\((x, 1)\)	\(1\)	\(x \cdot 1 \cdot 1 = x\) (dispari)	\(2\)
`FastPower`\((x, 3)\)	\(x\)	\(x \cdot x \cdot x = x^3\) (dispari)	\(2\)
`FastPower`\((x, 6)\)	\(x^3\)	\(x^3 \cdot x^3 = x^6\) (pari)	\(1\)
`FastPower`\((x, 12)\)	\(x^6\)	\(x^6 \cdot x^6 = x^{12}\) (pari)	\(1\)
`FastPower`\((x, 25)\)	\(x^{12}\)	\(x \cdot x^{12} \cdot x^{12} = x^{25}\) (dispari)	\(2\)

In totale \(2 + 2 + 1 + 1 + 2 = 8\) moltiplicazioni, contro \(25\) dell'algoritmo ingenuo. Si noti che \(25 = (11001)_2\): \(5\) cifre binarie, tre delle quali uguali a \(1\), e \(5 + 3 = 8\).

Il numero di moltiplicazioni è il numero di cifre binarie di \(n\) più il numero di cifre uguali a \(1\) (ogni chiamata con \(n \ge 1\) esegue \(1\) moltiplicazione se \(n\) è pari, \(2\) se \(n\) è dispari, e la parità degli esponenti successivi dà le cifre binarie di \(n\)):

\(n\)	binario	moltiplicazioni	\(S(n) = 4\lfloor \log_2 n \rfloor + 6\)	ingenuo
\(31\)	\(11111\)	\(5 + 5 = 10\)	\(4 \cdot 4 + 6 = 22\)	\(31\)
\(32\)	\(100000\)	\(6 + 1 = 7\)	\(4 \cdot 5 + 6 = 26\)	\(32\)
\(100\)	\(1100100\)	\(7 + 3 = 10\)	\(4 \cdot 6 + 6 = 30\)	\(100\)

Si noti che \(x^{32}\) richiede meno moltiplicazioni di \(x^{31}\), benché \(32 > 31\).

Ogni chiamata con \(n \ge 1\) effettua ora due chiamate ricorsive su \(\lfloor n/2 \rfloor\):

\[ C(n) = 2C(\lfloor n/2 \rfloor) + 1 \quad (n \ge 1), \qquad C(0) = 1. \]

Quindi \(C(1) = 3\), \(C(3) = 7\), \(C(6) = 15\), \(C(13) = 31\), e \(C(2) = 7\), \(C(4) = 15\), \(C(8) = 31\), \(C(16) = 63\).

L'albero delle chiamate ricorsive è ora un albero binario completo. I suoi livelli corrispondono agli esponenti \(n, \lfloor n/2 \rfloor, \dots, 1, 0\), cioè ci sono \(L = \lfloor \log_2 n \rfloor + 2\) livelli, con \(1, 2, 4, \dots, 2^{L-1}\) nodi. Quindi

\[ C(n) = 1 + 2 + \dots + 2^{L-1} = 2^{L} - 1 = 4 \cdot 2^{\lfloor \log_2 n \rfloor} - 1. \]

(Verifica: \(C(13) = 4 \cdot 8 - 1 = 31\), \(C(16) = 4 \cdot 16 - 1 = 63\).) Poiché \(n/2 < 2^{\lfloor \log_2 n \rfloor} \le n\), si ottiene \(2n - 1 < C(n) \le 4n - 1\), cioè \(C(n) = \Theta(n)\): la versione con due chiamate ricorsive identiche non è migliore dell'algoritmo ingenuo. Calcolare il valore una sola volta e memorizzarlo in \(y\) è essenziale.

Esecuzione di ToBinary\((37)\):

Chiamate:

ToBinary\((37) \to\) ToBinary\((18) \to\) ToBinary\((9) \to\)
ToBinary\((4) \to\) ToBinary\((2) \to\) ToBinary\((1)\)

Stampe (nell'ordine in cui le chiamate terminano):

chiamata	azione	stampato finora
`ToBinary`\((1)\)	caso base, stampa \(1\)	\(1\)
`ToBinary`\((2)\)	stampa \(2 \bmod 2 = 0\)	\(10\)
`ToBinary`\((4)\)	stampa \(4 \bmod 2 = 0\)	\(100\)
`ToBinary`\((9)\)	stampa \(9 \bmod 2 = 1\)	\(1001\)
`ToBinary`\((18)\)	stampa \(18 \bmod 2 = 0\)	\(10010\)
`ToBinary`\((37)\)	stampa \(37 \bmod 2 = 1\)	\(100101\)

Quindi \(37 = (100101)_2\) (infatti \(32 + 4 + 1 = 37\)), con \(6\) chiamate.

I resti \(n \bmod 2\) vengono calcolati nello stesso ordine di ChangeOfBase (divisioni ripetute: \(1, 0, 1, 0, 0, 1\), a partire dalla cifra meno significativa). Tuttavia, ogni chiamata stampa il proprio resto dopo che la sua chiamata ricorsiva è terminata, cioè dopo che tutte le cifre più significative sono state stampate: il call stack inverte l'ordine delle cifre, e non serve alcun array.

Correttezza, per induzione forte su \(n\).
- Casi base (\(n \in \{0,1\}\)): la rappresentazione binaria di \(n\) è la singola cifra \(n\), che viene stampata.
- Passo induttivo (\(n \ge 2\)): si ha \(n = 2\lfloor n/2 \rfloor + (n \bmod 2)\) con \(1 \le \lfloor n/2 \rfloor < n\). Se \(\lfloor n/2 \rfloor = (d_{k-1} \dots d_0)_2\), allora
  
  \[ n = 2\sum_{i=0}^{k-1} d_i 2^i + (n \bmod 2) = (d_{k-1} \dots d_0 \; (n \bmod 2))_2, \]
  
  cioè la rappresentazione binaria di \(n\) è quella di \(\lfloor n/2 \rfloor\) seguita dalla cifra \(n \bmod 2\). Per ipotesi induttiva la chiamata ricorsiva stampa \(d_{k-1} \dots d_0\), e poi l'algoritmo stampa \(n \bmod 2\).
Numero di chiamate. Sia \(C(n)\) il numero di chiamate per \(n \ge 1\): \(C(1) = 1\) e \(C(n) = C(\lfloor n/2 \rfloor) + 1\) per \(n \ge 2\). Dimostriamo \(C(n) = \lfloor \log_2 n \rfloor + 1\) per induzione forte: \(C(1) = 1 = \lfloor \log_2 1 \rfloor + 1\); per \(n \ge 2\), usando \(\lfloor \log_2 \lfloor n/2 \rfloor \rfloor = \lfloor \log_2 n \rfloor - 1\),

\[ C(n) = \big(\lfloor \log_2 n \rfloor - 1 + 1\big) + 1 = \lfloor \log_2 n \rfloor + 1. \]

Questo è il numero di cifre binarie di \(n\) (una cifra stampata per ogni chiamata). Per \(n = 37\): \(\lfloor \log_2 37 \rfloor + 1 = 5 + 1 = 6\).

mossa	disco	da	a	mossa	disco	da	a
1	1	A	B	9	1	B	C
2	2	A	C	10	2	B	A
3	1	B	C	11	1	C	A
4	3	A	B	12	3	B	C
5	1	C	A	13	1	A	B
6	2	C	B	14	2	A	C
7	1	A	B	15	1	B	C
8	4	A	C

mossa	disco	da	a	mossa	disco	da	a
1	1	A	B	9	1	B	C
2	2	A	C	10	2	B	A
3	1	B	C	11	1	C	A
4	3	A	B	12	3	B	C
5	1	C	A	13	1	A	B
6	2	C	B	14	2	A	C
7	1	A	B	15	1	B	C
8	4	A	C

mossa	disco	da	a	mossa	disco	da	a
1	1	A	B	9	1	B	C
2	2	A	C	10	2	B	A
3	1	B	C	11	1	C	A
4	3	A	B	12	3	B	C
5	1	C	A	13	1	A	B
6	2	C	B	14	2	A	C
7	1	A	B	15	1	B	C
8	4	A	C