Premi qui per scaricare il PDF
Definizioni induttive
Esempio: il fattoria di un naturale (n!)- Se N = 0, il fattoriale N! è 1;
- Se N>0 il fattoriale N! è N * (N-1)!
- 0 è un numero pari
- 1 non è un numero pari
- se n > 1 è un numero pari, anche n-2 è un numero pari
- Se n = 1: vero (per verifica diretta)
- Suppongo sia vero per n = k (ipotesi di induzione $(2n)^2 = 4n^2$) e dimostro l’uguaglianza di cui sopra, per n = k+1:
- \[(2n)^2 = (2(k+1))^2 = (2k+2)^2 = (2k)^2 + 8k + 4 =\] (per ipotesi di induzione) \[4k^2+8k+4 = 4(k^2+2k+1) = 4(k+1)^2 = 4n^2\]
- è il caso base
- è il passo induttivo
Iterazione e ricorsione
Iterativa
L’iterazione si realizza mediante la tecnica del ciclo, per il calcolo del fattoriale:0! = 1;
n! = n(n-1)(n-2)...1 (realizzo un ciclo)
int fattoriale(int n)
{
int f;
for (f = 1; n > 0; n--)
f = f*n;
return f;
}
Ricorsiva
- Esiste almeno un caso base che rappresenta un sotoo-problema di facile soluzione
- Esempio: se N = 0, N! = 1.
- Esiste almeno un passo induttivo che prima o poi riconduce il problema generale a un caso base
- Consiste nell’esprimere la soluzione al problema in termini di operazioni semplici e della soluzione allo stesso problema su dati “più piccoli” (per ipotesi)
- Esempio: N generico, esprimo N! in termini di N moltiplicato per (N-1) (che non conosco ma so calcolare per ipotesi induttiva)
In C
Occupa più spazio in memoria.
Un sottoprogramma P, invoca se stesso
Calcolo fattoriale
int FattRic (int n)
{
if (n == 0) //Se il valore di n è 0, restituisce 1
return 1;
else
return n * FattRic(n-1); //Calcolo il prodotto richiamando il sottoprogramma stesso
}
Esempio: Il calcolo della prima ricorsione viene sospeso finchè non arrivo alla fine. Finite le ricorsioni risolvo e restituisco tutti i valori dall’ultimo al primo (in ordine inverso).
Quando si può dire che una ricorsione è ben definita?
Se per ogni applicazione del passo induttivo ci si avvicina alla situazione riconosciuta come caso base (assioma), allora la definizione non è circolare e la catena di invocazioni termina.
Esempio – Serie di Fibonacci
- Prendiamo una coppia di conigli appena nati
- La coppia diventa fertile dopo 1 mese e genera una nuova coppia ogni mese dopo il primo
- Le nuove coppie si comportano in modo analogo e i conigli non muoiono mai.
Quante coppie ci sono dopo n mesi?
int fibo (int n)
{
if (n == 0 || n == 1)
return 1;
else return fibo(n-1) + fibo (n-2);
}
Supponiamo n ≥ 0
Esempio MCD Euclide
MCD tra M e N (naturali positivi)
- Se M = N allora MCD è N;
- Se M = 0 allora MCD è M;
- Se N = 0 allora MCD è N;
- Se M > N allora esso è il MCD tra N e M-N
- Se M < N allora esso è il MCD tra M e N-M
3 casi base e 2 passi induttivi
Metodo ricorsivo
int EuclideRic(int m, int n)
{
if ( m == n)
reutrn m;
if (m > n)
return EuclidRic(m-n, n);
else
return EuclideRic(m, n-m)
}
Metodo Iterativo
int EuclideIter(int m, int n)
{
while (m != n)
if(m > n)
m = m - n;
else
n = n - m;
return m;
}Funzione esponenziale (intera)
Definizione iterativa
\[b^e = 1\qquad se \quad e = 0\] \[b^e = b*b*b…b (e \quad volte) \qquad se \quad e >0\]Codice iterativo
int esp (int b, int e)
{
int i, r = 1;
for (i = 1; i <= e; i++)
r = r*b;
return r;
}
Definizione induttiva
\[b^e = 1\qquad se \quad e = 0\] \[b^e = b * b^{(e-1)} \qquad se \quad e > 0\]Codice ricorsivo
int esp (int b, int e)
{
if (e == 0)
return 1;
else
return b * esp(b, e-1);
}
- In un certo istante possono essere in corso diverse attivazioni dello stesso sottoprogramma
- Ovviamente sono tutte sospese tranne una, l’ultima invocata, all’interno della quale si sta svolgendo il flusso di esecuzione
- Ogni attivazione esegue lo stesso codice ma opera su copie distinte dei parametri e delle variabili locali
Modello a runtime
int FattRic(int)
int main()
{
int val, ris;
printf("Dammi un naturale\\n");
scanf("%d", &val);
ris = FattRic(val);
printf("\\nfattoriale = %d", ris);
return 0;
}
int FattRic (int n)
{
int temp;
if (n == 0)
return 1;
else
{
temp = n * FattRic(n-1);
return temp;
}
}
temp → cella temporanea per memorizzare il risultato della funzione chiamata.
Terminazione
- Attenzione al rischio di catene infinite di chiamate
- Occorre che le chiamate siano soggette a una condizione che assicura che prima o poi la catena termini.
- Occorre anche che l’argomento sia “progressivamente ridotto” dal passo induttivo, in modo da tendere prima o poi al caso base.
Esempio: lunghezza stringhe
Soluzione iterativa
int lunghezzaI (char s[])
{
int i = 0;
while (s[i] != '\\0')
i++;
return i;
}
Soluzione ricorsiva
int lunghezzaR(char s[])
{
if (s[0] == '\\0')
return 0;
else
return 1 + lunghezzaR(&s[1]);
}
Esempio parola palindroma
Palindromo → Parola che si può leggere indifferentemente da destra a sinistra e viceversa
onorarono → è palindroma
a → è palindroma;
anno → NON è palindroma
Versione iterativa
int palindromoI(char par[])
{
int da = 0; //Indice del primo carattere
int a = strlen (par) - 1; //Indice dell'ultimo carattere
while (da < a)
{
if (par[da] != par[a])
return 0;
++da;
--a;
}
return 1;
}
Il programma scansiona la parola facendo muovere gli indici verso il centro di par e dice FALSE alla prima differenza.
Versione ricorsiva 1
int palindromoR (char par[], int da, int a)
{
if (da >= a)
return 1;
else
return (par[da] == par[a] && palindromoR(par, da+1, a-1));
}
É più efficiente rispetto alla versione 2 per via degli operatori logici valutati “pigramente” dal C.
Versione ricorsiva 2
int palindromoR (char par[], int da, int a)
{
if (da >= a)
return 1;
else
return (palindromoR(par, da+1, a-1) && par[da] == par[a]);
}
Chiamare la funzione nel main
palindromoR("oro", 0,2);
//OPPURE
palindromoR(str, 0, strlen(str)-1);
Esempio: inversione stringa
Scrivere una funzione che costruisca la stringa inversa di una stringa data nello stesso vettore.
Il chiamante deve invocare la funzione con i parametri che sono (la stringa da invertire str[ ] e la lunghezza n della stessa).
Il ragionamento induttivo che applichiamo è:
- Se abbiamo il risultato dell’inversione della sottostringa ottenuta da quella di partenza senza il primo e l’ultimo carattere (che sarà lunga n-2 caratteri).
- Possiamo completare l’inversione della stringa di partenza, scambiando il primo e l’ultimo carattere.
void inversione (char str[], int n)
{
if (n <= 1) //caso base
return;
inversione (&str[1], n-2); //passo induttivo
char temp = str[n-1];
str[n-1] = str[0];
str[0] = temp;
}
Esercizio: riscrivere la funzione con prototipo:
void inversione (char str[], int inizio, int fine)