Traccia della lezione Lez14:

Lucido 1:
Per inciso, esiste anche una forma di "ricorsione indiretta", meno comune 
di quella diretta, nella quale una funzione ne chiama un'altra, che chiama 
a sua volta la prima. Ovviamente, sono possibili cicli con più di due 
funzioni e strutture anche più complesse.


Lucido 6:
Osservazione essenziale è il fatto che, ad ogni chiamata, il parametro n è 
una cella diversa, contenente un numero diverso. Il fatto di poter dare lo
stesso nome a cose diverse viste in ambienti diversi è fondamentale per
poter scrivere un algoritmo ricorsivo: in ogni ambiente c'è un numero 
corrente n di cui si vuole calcolare il fattoriale. Su tale numero si 
vogliono compiere le stesse operazioni per conoscere un risultato della 
stessa natura (il fattoriale), ma tale numero è ogni volta diverso e quindi 
il valore del risultato è ogni volta diverso.

L'uso dello stesso nome per oggetti diversi viene dal fatto che i nomi di 
parametri e variabili sono locali alla singola chiamata.


Lucido 7:
L'importanza del caso base e della "riduzione" dei dati dovrebbero 
risultare chiare dall'esempio:
1) se non avessimo un caso base, le chiamate non si arresterebbero mai, 
  portando ad allocare una quantità infinita di memoria, cioè ad esaurire 
  la memoria disponibile
2) se non avessimo una "riduzione" dei parametri attuali, la condizione che 
  porta al caso base non sarebbe mai vera, per cui sarebbe come non averlo. 
  
Si noti la profonda analogia con quel che succede nei cicli: la condizione 
che distingue caso base e caso ricorsivo svolge una funzione simile alla 
condizione di permanenza nel ciclo: se vale sempre il caso ricorsivo o se
la condizione di permanenza è sempre vera, il programma non si arresta mai. 
Quindi è un programma, ma non un algoritmo, ed è totalmente inutile.
  
Affinché questo non si verifichi, è essenziale che il caso ricorsivo 
"riduca" i dati, esattamente come era essenziale che il corpo del ciclo 
modificasse le variabili della condizione di permanenza.


Lucido 10:
Vediamo come altro esempio il calcolo della n-esima potenza di un numero 
intero i. Per procedere in modo ricorsivo, occorre:
1) un caso base risolubile con un algoritmo semplice
2) una procedura per "ridurre" i dati nel caso difficile
3) la garanzia che la riduzione porti sempre al caso base
4) una procedura per "ricostruire" la soluzione a partire da quelle dei 
  problemi più piccoli

Il codice POTENZA.C risolve il problema in questo modo:
1) la potenza 0 è sempre uguale a 1: è un caso facile, e l'algoritmo che 
  lo risolve consiste nel rispondere sempre 1
2) per ridurre il problema i^n a un problema "più piccolo" si può ridurre
  n a n-1
3) se si diminuisce n di 1 alla volta, prima o poi si arriva a 0
4) se conosciamo i^(n-1), possiamo moltiplicarlo per i allo scopo di 
 ricostruire i^n 

long potenza (long b, long e)
{
  if (e == 0)
    return 1;
  else
    return b * potenza(b,e-1);
}

Ovviamente, si sta ipotizzando che "e" sia sempre >= 0.

Conviene seguire disegnando lo stack l'esecuzione di potenza(5,4) per 
chiarirsi meglio il funzionamento dello stack


Una versione alternativa del codice potrebbe usare la proprietà matematica:
b^e = b^(e/2) * b^(e/2)

Questa porterebbe al codice POTENZA2.C:

long potenza (long b, long e)
{
  if (e == 0)
    return 1;
  else
    return potenza(b,e/2) * potenza(b,e/2);
}

Questo codice è scorretto perché e/2 è la divisione troncata di un numero 
intero: se "e" è dispari, il risultato non torna (sarebbe b^5 = b^2 * b^2).
Siccome si passa sempre per il caso e = 1, il risultato è b^(1/2)*b^(1/2),
cioè b^0*b^0, cioè 1.

Proviamo a ovviare scomponendo e in due numeri vicini a e/2, e la cui somma 
sia "e" (POTENZA3.C).

long potenza (long b, long e)
{
  if (e == 0)
    return 1;
  else
    return potenza(b,e/2) * potenza(b,e - e/2);
}

Il programma si interrompe bruscamente e senza messaggi di errore.
Il fatto è che è violata un'altra condizione essenziale di correttezza:
che si raggiunga il caso base. Infatti, per e = 1 si ha b^(1/2)*b^(1-1/2),
cioè b^0*b^1. Una delle due chiamate ricorsive non ha ridotto l'argomento
(l'esponente era 1, ed è ancora 1), per cui l'albero delle chiamate è 
infinito e lo stack si riempie fino a consumare la memoria e interrompere 
il programma.

Si può ovviare cambiando il caso base, cioè fermandosi con e == 1, anziché 
e == 0, oppure così (POTENZA4A.C):

long potenza (long b, long e)
{
  if (e == 0)
    return 1;
  else if (e % 2 == 0)
    return potenza(b,e/2) * potenza(b,e/2);
  else
    return b * potenza(b,e/2) * potenza(b,e/2);
}

In questo caso, si può anche migliorare l'efficienza del codice come segue
(POTENZA4B.C):
 
long potenza (long b, long e)
{
  long p;
  
  if (e == 0)
    return 1;
  else 
  {
    p = potenza(b,e/2);
    if (b % 2 == 0)
      return p * p;
    else
      return b * p * p;
  }
}

Questo evita di chiamare due volte la funzione potenza, ripetendo due volte 
il processo di allocazione e deallocazione sullo stack (con tutte le 
chiamate interne). Il risparmio di tempo può essere enorme: per rendersene 
conto chiaramente, basta disegnare l'albero delle chiamate per un numero 
anche relativamente piccolo (ad esempio, n = 10). 

Lucido 11:
Il codice SELECTIONSORT.C illustra l'algoritmo di Selection Sort, che si 
basa sull'idea seguente:
- un vettore vuoto o di un solo elemento è già ordinato: si ordina non 
  facendo nulla
- un vettore generico si rimpicciolisce scartando l'ultimo elemento (come 
  dire conservando il vettore, ma riducendo la variabile n che ne indica 
  la lunghezza utile: la cella n-esima rimane lì, ma ai fini del programma 
  viene considerata esterna)
- se la cella n-esima contenesse l'elemento massimo, una volta ordinato 
  il vettore rimanente, potremmo reinserire l'elemento massimo in fondo. 
  Siccome l'elemento è già in fondo, per reinserirlo basta riaumentare la 
  lunghezza corrente n.
- Occorre quindi prima della chiamata ricorsiva portare l'elemento massimo 
  in posizione finale e l'elemento finale nella posizione occupata 
  precedentemente dall'elemento massimo. Si potrebbero anche scalare gli 
  elementi intermedi, ma sarebbe del tutto inutile.

Nulla vieta di ordinare un vettore portando l'elemento minimo in prima 
posizione. A questo punto, però il vettore residuo andrebbe dalla posizione 
2 alla posizione n. Per passare alla chiamata ricorsiva tale vettore, basta 
passargli V+1 (sfruttando l'aritmetica del puntatori) oppure &V[1] e n-1 
come lunghezza. Questa alternativa è leggermente meno efficiente, dato che 
richiede di calcolare il nuovo V oltre alla nuova n. Però è perfettamente 
corretta.

Si può notare che le funzioni TrovaIndiceMassimo e Scambia non sono state 
riportate fra i prototipi, contrariamente a quanto fatto sinora. Il motivo 
è che in realtà il C richiede solo che le chiamate a una funzione siano 
precedute o dalla loro definizione o dalla dichiarazione (prototipo). 
Le due funzioni in questione vengono usate solo in un punto, dalla funzione 
SelectionSort, per cui si possono considerare abbastanza irrilevanti da non 
essere elencate all'inizio, purché la loro definizione preceda quella della 
funzione che le chiama. Se altre funzioni la chiamassero, sarebbe 
necessario preoccuparsi di metterle prima di loro, e magari la soluzione 
più comoda e ordinata consisterebbe nell'aggiungere il prototipo 
al principio del file.

Lucido 10:
Il codice INSERTIONSORT.C illustra l'algoritmo di Insertion Sort, che si 
basa sull'idea seguente:
- un vettore vuoto o di un solo elemento è già ordinato: si ordina non 
  facendo nulla
- un vettore generico si rimpicciolisce scartando l'ultimo elemento (come 
  dire conservando il vettore, ma riducendo la variabile n che ne indica 
  la lunghezza utile: la cella n-esima rimane lì, ma ai fini del programma 
  viene considerata esterna)
- se la cella n-esima contiene un elemento qualsiasi, una volta ordinato 
  il vettore rimanente, il nuovo elemento non si può reinserire in fondo. 
- Occorre quindi trovare la posizione in cui inserirlo e scalare tutti gli 
  elementi successivi per fargli spazio. Ovviamente, l'elemento in 
  posizione n-1 finirà in posizione n e il vettore sarà perfettamente 
  ricostituito (a meno che l'elemento da reinserire non sia già quello
  massimo).

Anche qui si può facilmente procedere dalla cima del vettore anziché dal 
fondo.


Lucido 11:
Il codice FIBONACCI-RIC.C calcola l'n-esimo numero di Fibonacci applicando 
la definizione, che è già di per sé ricorsiva:

F(n) = 1                se n = 0 o 1
       F(n-1) + F(n-2)  se n > 1

Seguendo l'esecuzione del codice sullo stack, per esempio per F(4), è 
curioso osservare come in diversi punti si risolva più volte lo stesso 
problema. Questo suggerisce che si sta facendo un calcolo inefficiente. 
Si potrebbero invece salvare da qualche parte i risultati per riutilizzarli 
quando vi fosse bisogno.

Al contrario degli altri codici visti prima, la versione iterativa di 
Fibonacci, cioè il codice FIBONACCI-ITE.C, non esegue esattamente le stesse 
operazioni della versione ricorsiva, ma è proprio un algoritmo diverso. 
E' più efficiente, dato che evita di ricalcolare più volte gli stessi 
valori. Provando con n = 40, la differenza è evidente. L'idea di fondo 
di questo algoritmo consiste nel salvare i risultati che potrebbero essere 
utili, cioe' F(n-1) e F(n-2), in modo da non doverli ricalcolare.

Esercizio:
Si provi a implementare una versione ricorsiva di Fibonacci che, oltre
a gestire il caso base, conserva le soluzioni dei sottoproblemi, cioe'
i valori di F(i) in un opportuno vettore inizializzato a zero, e ogni 
volta verifica se il problema corrente ha soluzione nel vettore oppure no.
Nel primo caso, non è necessario eseguire il caso ricorsivo, ma si può
direttamente usare la soluzione del vettore. In altre parole, si introduce
un secondo caso base che corrisponde ai valori già calcolati. Volendo, 
questo secondo caso base si può fondere con il primo: basta che il vettore
delle soluzioni contenga già in partenza i valori F(0) e F(1).
Per poter accedere al vettore in ogni chiamata, esso deve essere passato
come parametro alla funzione ricorsiva. Essendo un vettore, non ci sono 
problemi ad aggiornare i suoi valori ogni volta che se ne calcola uno 
nuovo. Questo codice ricorsivo evita la maggior parte delle inefficienze 
di FIBONACCI-RIC.C (la ripetizione insistita degli stessi calcoli), ma è 
comunque meno efficiente del codice iterativo, dato che comunque richiede
n-1 chiamate annidate, con tutte le relative operazioni di allocazione
sullo stack, copia dei parametri, deallocazione dallo stack e restituzione
del risultato.