Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 1
Problema:
Un cesto contiene delle palline di forma identica e tutte di peso identico tranne una di peso maggiore delle altre. Bisogna trovare la pallina più pesante
utilizzando una sola bilancia ed il minor numero di pesate … si supponga di avere un numero multiplo di 3 di palline … Soluzione:
• Dividere le palline in tre gruppi di ugual numero e pesare due di tali gruppi
• Se i due gruppi hanno lo stesso peso scartarli entrambi, altrimenti scartare
• il gruppo non pesato e quello che sulla bilancia pesa di meno (la pallina
• cercata è nel gruppo che pesa di più
• Dividere il gruppo rimasto in tre sottogruppi e applicare di nuovo il procedimento finché i sottogruppi contengano una sola pallina: l’ultima pesata indicherà quale delle tre palline rimaste è quella con peso maggiore
Ricorsione
L’ultimo punto del metodo di soluzione indicato è il ricorrere all’applicazione dello stesso metodo su un set ridotto di dati fino a che non ci troviamo di fronte ad un caso banale (caso base), da cui è possibile ricavare una soluzione immediata:
tre gruppi di una sola pallina ciascuno
Una descrizione più vicina a quella di un programma per risolvere il problema:
Se i gruppi di palline consistono di una sola pallina, la pallina più pesante è la soluzione cercata (caso base)
altrimenti … (regola di ricorsione)
Dividere il gruppo di palline in tre sottogruppi e poni due sottogruppi sulla bilancia
Se i due gruppi hanno peso uguale scartarli entrambi, altrimenti scartare il gruppo non pesato e quello di peso minore
Applica il metodo delle pesate al sottogruppo individuato
… ovvero richiama l’algoritmo …
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 3
… in pratica …
… un algorimo è ricorsivo quando è definito in termini di se stesso, cioè esso contiene una istruzione che richiede una nuova esecuzione dell’algoritmo stesso ma su un insieme ridotto di dati
Devono essere definiti:
• Il caso base (o base della ricorsione): stabilisce le condizioni iniziali cioè il risultato per i dati iniziali (in genere per i valori 0 e/o 1)
• La regola di ricorsione: stabilisce il risultato per un valore n, diverso da quello iniziale, tramite un’espressione che richiama il risultato dello stesso algoritmo calcolato per il valore n – i (in genere i = 1)
Ricorsione
Il concetto di ricorsione (o ricorsività) si riconduce a quello di induzione matematica
Principio di induzione
Sia P un predicato sull’insieme N dei numeri naturali e sia vero il predicato P(0) - (rappresenta il caso base);
se per ogni k (con k N) dal predicato P(k) vero discende la verità di P(k+1), allora P(n) è vero per qualsiasi n .
Es. : Fattoriale di n
0! = 1 (caso base) n! = n * (n-1)!
Un algoritmo ricorsivo può essere espresso mediante un sottoprogramma ricorsivo, cioè un sottoprogramma che chiama se stesso (ricorsione diretta).
Il predicato P(0) forma il cosidetto ‘caso base’
… per risolvere il sottoproblema P è necessario risolvere il sottoproblema P stesso !!
… la soluzione di un caso generico può essere ricavata sulla base della soluzione di un
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 5
La ricorsione può essere ‘diretta’, quando un sottoprogramma chiama se stesso, o ‘indiretta’, quando in una catena di attivazioni di sottoprogrammi uno di questi chiama uno già attivato in precedenza nella catena
subA
subB subC
main Esempio di ricorsione indiretta:
void subA( ) { ...
subB();
...}
void subB( ) { ...
subC();
...}
void subC( ) { ...
subA();
...}
Esempio di ricorsione diretta:
void subA( ) { ...
subA();
...} subA
Il fattoriale è un tipico esempio di ricorsione diretta n! = n (n-1)!
n! = n * (n-1) ! = n * (n-1) * (n-2)! = ... ... = n * (n-1) * (n-2) * ... * 0!
5! = 5 * 4 ! =
5 * (4 * 3!) = 5 * (4 * (3 * 2!)) = 5 * (4 * (3 * (2 * 1!))) = 5 * (4 * (3 * (2 * (1 * 0!)))) 0! = 1 Caso base
Ricorsione
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 7
Si innesca una ripetizione di attivazioni, non realizzata con strutture cicliche, dovuta alle susseguenti attivazioni che il sottoprogramma fa a se stesso (se il sottoprogramma richiama se stesso, questa chiamata a sua volta richiamerà di nuovo il sottoprogramma e così via).
A ciascuna attivazione del sottoprogramma corrisponde una nuova istanziazione delle sue variabili che contengono i valori correnti calcolati (questi sono mantenuti fino alla terminazione dell’esecuzione relativa alla corrispondente attivazione).
Oltre al fattoriale, altri esempi di algoritmi ricorsivi sono:
Sommatoria … somma valore n-esimo alla sommat dei rimanenti (n-1) numeri
Ricerca elemento in un array ordinato …
confronta il valore da cercare con quello dell’elemento in posizione centrale …
‘dimezza’ lo array … confronta con il nuovo ‘centro’ del ‘mezzo’ array …
Serie di Fibonacci …
0, 1, 1, 2, 3, 5, 8, 13, 21, ... ogni numero è la somma dei due precedenti
#include <stdio.h>
long fat(int);
main() {int n;
printf("CALCOLO DI n!\n\n");
printf("Inserire valore di n: \n");
scanf("%d", &n);
printf(“Fattoriale di %d = %d\n", n, fat(n));
}
long fat (int n) {long a;
if (n==0) a=1;
else
a= n * fat(n-1);
return a;
}
Calcolo fattoriale con sottoprogramma ricorsivo
Soluzione iterativa:
……
if(n==0) fat = 1;
else fat=1;
for(fat=n; n>2; n--) fat = fat*(n-1);
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 9
Ricorsione
Esempio di esecuzione ricorsiva per il calcolo di 3!:
Bisogna assicurarsi che la ricorsione converga altrimenti si genera una ricorsione infinita !!
main
…….
fat(3);
……..
1
return a = 1 return a = 1
return a = 2 return a = 6
fatt(3)
…….
if (n==0) a=1;
else a=3*fat(2);
return a;
……..
2
//n = 3 fatt(2)
…….
if (n==0) a=1;
else a=2*fat(1);
return a;
……..
3
//n = 2 fatt(1)
…….
if (n==0) a=1;
else a=1*fat(0);
return a;
……..
//n = 1 fatt(0)
…….
if (n==0) a=1;
else a=n*fat(n-1);
return a;
……..
4
//n = 0
• Serie di Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
– Ogni numero è la somma dei due precedenti:
fib(n) = fib(n-1) + fib(n-2) … formula ricorsiva …
Caso base: fib(0) = 0 ; fib(1) = 1
long fibonacci(long n)
{ if (n==0 || n==1) // caso base a = n;
else a = fibonacci(n-1) + fibonacci(n-2);
return a;
}
Esempio: Serie di Fibonacci
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 11
#include <stdio.h>
long int fibo(int);
main(){
int n;
printf(“Serie di Fibonacci f(0)= 1 f(1)=1 f(n)=f(n-1)+f(n-2)");
printf("\nInserire n: \t");
scanf("%d", &n);
printf("Termine della serie di argomento %d:
%d\n", n, fibo(n));
}
long int fibonacci(int n) {long int a;
if(n==0) a=0;
else
if(n==1) a = 1;
else
a =( fibonacci(n-1)+ fibonacci (n-2) );
return a;
}
F(n) = F(n 1) + F(n 2) Per esempio, F(7):
F(0) = 0 F(1) = 1 F(2) = 1 + 0 = 1 F(3) = 1 + 1 = 2 F(4) = 2 + 1 = 3 F(5) = 3 + 2 = 5 F(6) = 5 + 3 = 8 F(7) = 8 + 5 = 13
f( 3 )
f( 1 ) f( 2 )
f( 1 ) f( 0 ) return 1
return 1 return 0
return +
+ return
Serie di Fibonacci
… attivazioni per n =3…
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 13
• Ripetizione
– Iterazione: loop espressi esplicitamente
– Ricorsione: chiamate a sottoprogrammi ripetute (non esplicitamente)
• Terminazione
– Iterazione : controllate esplicitamente da condizioni – Ricorsione: riconoscimento del caso base
• Possibilità /Rischio di avere per entrambe ripetizioni infinite
• Algoritmi iterativi sono più performanti; algoritmi ricorsivi sono più comprensibili (migliore progettazione del sw)
