G. Amodeo, C. Gaibisso Programmazione di Calcolatori Lezione XXVII La ricorsione Programmazione di Calcolatori: la ricorsione 1 G. Amodeo, C. Gaibisso La ricorsione • Definizione ricorsiva: definizione di un oggetto (un insieme, una struttura, una funzione, …) in termini della definizione dell’oggetto stesso • Comportamento ricorsivo quello esibito da una classe di oggetti definibili tramite due proprietà: • un insieme di casi base • un insieme di regole che riducono qualsiasi caso a uno dei casi base Programmazione di Calcolatori: la ricorsione 2 G. Amodeo, C. Gaibisso Le funzioni ricorsive • Il fattoriale: fatt : N 0 N 1 if n 0 fatt ( n) n fatt ( n 1) otherwise • I numeri di Fibonacci: fib : N 0 N 0 if n 0 fib( n) 1 if n 1 fibn 1 fib(n-2 ) otherwise Programmazione di Calcolatori: la ricorsione 3 G. Amodeo, C. Gaibisso Le funzioni ricorsive • Il calcolo: fatt(5) = 5 * fatt(4) = = 5 * 4 * fatt(3) = = 5 * 4 * 3 * fatt(2) = = 5 * 4 * 3 * 2 * fatt(1) = = 5 * 4 * 3 * 2 * 1 * fatt(0) = = 5*4*3*2*1*1 Programmazione di Calcolatori: la ricorsione = 4 G. Amodeo, C. Gaibisso Le funzioni ricorsive 1 if n 0 fatt ( n) n fatt ( n 1) otherwise // Nome e posizione del file: // Lezione_XXVII/fatt.c // Descrizione del contenuto del file: // funzioni per il calcolo ricorsivo del fattoriale // Descrizione della funzionalita' implementata: // calcola ricorsivamente il fattoriale di un intero positivo // Tipo, nome e significato dei parametri della funzione: // int n: valore dell'argomento del fattoriale // Tipo e significato del valore restituito: // int: fattoriale del valore fornito in ingresso int fatt(int n) { // il fattoriale di 0 e' 1 if (n == 0) return(1); // il fattoriale di n, con n diverso da, e' n per il fattoriale di n-1 return(n*fatt(n-1)); }; Programmazione di Calcolatori: la ricorsione 5 G. Amodeo, C. Gaibisso Le funzioni ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 6 G. Amodeo, C. Gaibisso Le funzioni ricorsive 0 if n 0 // Nome e posizione del file: fib( n) 1 if n 1 // Lezione_XXVII/fibonacci.c // Descrizione del contenuto del file: fibn 1 fib(n-2 ) otherwise // funzioni per il calcolo ricorsivo // della sequenza di fibonacci // Descrizione della funzionalita' implementata: // calcola l’n-esimo numero della sequenza di fibonacci // Tipo, nome e significato dei parametri della funzione: // int n: posizione del numero all'interno della sequenza di fibonacci // Tipo e significato del valore restituito: // int: l'n-esimo valore della sequenza di fibonacci int fib(int n) { // il primo numero nella sequenza di fibonacci e' 0 if (n == 0) return(0); // il secondo numero nella sequenza di fibonacci e' 1 if (n == 1) return(1); // l'n-esimo numero nella sequenza di fibonacci, con n > 1, e' la somma // dell'(n-1)-esimo e dell'(n-2)-esimo numero della stessa sequenza return(fib(n-1)+fib(n-2)); }; Programmazione di Calcolatori: la ricorsione 7 G. Amodeo, C. Gaibisso Le funzioni ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 8 G. Amodeo, C. Gaibisso Le strutture ricorsive • Lista di valori di tipo T (LT): empty LT LT if t T and L LT then t . L LT • Le liste: tn.tn-1. … . t2. t1. empty Programmazione di Calcolatori: la ricorsione 9 G. Amodeo, C. Gaibisso Le strutture ricorsive • LLN?: L = 100.8.4. 5. 28. empty LN ? SI 100N e 8.4. 5. 28. empty LN ? SI 8N e 4. 5. 28. empty LN ? SI 4N e 5. 28. empty LN ? SI 5N e 28. empty LN ? 28N e empty LN ? SI SI SI Programmazione di Calcolatori: la ricorsione 10 G. Amodeo, C. Gaibisso Le strutture ricorsive • LLN?: L = 100.8,5.4. 5. 28. empty LN ? SI 100N e 8,5.4. 5. 28. empty LN ? NO 8,5N e 4. 5. 28. empty LN ? NO Programmazione di Calcolatori: la ricorsione 11 G. Amodeo, C. Gaibisso Le strutture ricorsive • Qual è la somma degli elementi di LLN (liste di naturali)? somma : LN N if L empty 0 somma(L) t somma(L') if L t.L' Programmazione di Calcolatori: la ricorsione 12 G. Amodeo, C. Gaibisso Le strutture ricorsive 0 somma(L) t somma(L') if L empty if L t.L' // Nome e posizione del file: // Lezione_XXVII/somma.c // Descrizione del contenuto del file: // funzioni per il calcolo ricorsivo della somma degli elementi di // un vettore di naturali (codificata con un vettore di interi) // Descrizione della funzionalita' implementata: // calcola ricorsivamente la somma degli elementi del vettore // Tipo, nome e significato dei parametri della funzione: // int vett: riferimento ad un vettore di interi // int dim: dimensione del vettore // Tipo e significato del valore restituito: // int: somma degli elementi del vettore int somma(int *vett, int dim) { // se il vettore e' vuoto la somma vale 0 if (dim == 0) return(0); // la somma degli elementi di un vettore di dimensione non nulla // e' pari al primo elemento del vettore + la somma degli // elementi nella parte rimanente del vettore return(vett[0] + somma(vett+1, dim-1); }; Programmazione di Calcolatori: la ricorsione 13 G. Amodeo, C. Gaibisso Le strutture ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 14 G. Amodeo, C. Gaibisso Le strutture ricorsive • Ricerca ricorsiva di un elemento in LLT: cerca : N LN true, false if L empty false cerca(t, L) true if t t' cerca(t, L') otherwise if L (t'.L') Programmazione di Calcolatori: la ricorsione 15 G. Amodeo, C. Gaibisso Le strutture ricorsive if L empty false cerca(t, L) true if t t' cerca(t, L') otherwise if L (t'.L') // Nome e posizione del file: // Lezione_XXVII/cerca.c // Descrizione del contenuto del file: // funzioni per la ricerca ricorsiva di un valore all'interno di una lista di // naturali (codificata con un vettore di interi) // Descrizione della funzionalita' implementata: // ricerca ricorsivamente un valore all'interno di un vettore // Tipo, nome e significato dei parametri della funzione: // int vett: riferimento ad un vettore di interi // int dim: dimensione del vettore // int val: valore cercato // Tipo e significato del valore restituito: // int: 1 se l'elemento è presente; 0 altrimenti int cerca(int *vett, int dim, int val) { // se il vettore e' vuoto restituisce false if (dim == 0) return(0); // se il primo elemento del vettore coincide con il valore cercato restituisce 1 if (vett[0] == val) return(1); // altrimenti cerca lo stesso valore all'interno del vettore privato del // primo elemento return(cerca(vett+1, dim-1, val, nro_call, lev_of_nest+1)); }; Programmazione di Calcolatori: la ricorsione 16 G. Amodeo, C. Gaibisso Le strutture ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 17 G. Amodeo, C. Gaibisso Le strutture ricorsive • LLT è ordinata in modo strettamente crescente? ord : LT true, false if L empty true true if L t .empty ord (L) if t1 t2 false if L t1 .t2 . S' ord (t .L') otherwise 2 Programmazione di Calcolatori: la ricorsione 18 G. Amodeo, C. Gaibisso Le strutture ricorsive if L empty true true if L t .empty ord (L) if t1 t 2 false if L t1 .t2 . S' ord (t 2 .L') otherwise // Nome e posizione del file: // Lezione_XXVII/ordinata.c // Descrizione del contenuto del file: // funzioni che verificano se una // lista di interi e' ordinata // Descrizione della funzionalita' implementata: // verifica ricorsivamente se la lista e' ordinata // Tipo, nome e significato dei parametri della funzione: // int vett: riferimento ad un vettore di interi // int dim: dimensione del vettore // Tipo e significato del valore restituito: // int: 1 se la lista e' ordinata; 0 altrimenti int ordinata (int *vett, int dim) { // se il vettore e' vuoto restituisce 1 if (dim == 0) return(1); // se la lista contiene un solo elemento restituisce 1 if (dim == 1) return(1); // se il primo elemento della lista e' superiore al secondo restituisce 0 if (vett[0] > vett[1]) return(0); // altrimenti verifica il vettore privato del primo elemento return(ordinata(vett+1, dim-1)); }; Programmazione di Calcolatori: la ricorsione 19 G. Amodeo, C. Gaibisso Le strutture ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 20 G. Amodeo, C. Gaibisso Le strutture ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 21 G. Amodeo, C. Gaibisso Le strutture ricorsive • Qual è il massimo di LLN? max : LN N 1 if L empty 1 t if L t .empty max(L) if t max(L') t if L t.L', L' empty max(L') otherwise Programmazione di Calcolatori: la ricorsione 22 G. Amodeo, C. Gaibisso Le strutture ricorsive if L empty 1 // Nome e posizione del file: t if L t .empty // Lezione_XXVII/max_1.c // Descrizione del contenuto del file: max(L) t if t max(L') // funzioni per il calcolo ricorsivo if L t.L' // del massimo di una lista di max(L') otherwise // naturali // Descrizione della funzionalita' implementata: // calcola ricorsivamente il massimo degli elementi del vettore // Tipo, nome e significato dei parametri della funzione: // int vett: riferimento ad un vettore di interi // int dim: dimensione del vettore // Tipo e significato del valore restituito: // int: massimo degli elementi del vettore int max(int *vett, int dim) { // se il vettore e' vuoto il massimo è 0 if (dim == 0) return(0); // se il vettore contiene un solo elemento il massimo e' l'elemento stesso if (dim == 1) return(vett[0]); // se il primo elemento e' maggiore del massimo della parte rimanente // del vettore il massimo e' il primo elemento if (vett[0] >= max(vett+1, dim-1)) return(vett[0]); else // altrimenti il massimo e' quello della parte rimanente del vettore return(max(vett+1, dim-1)) }; Programmazione di Calcolatori: la ricorsione 23 G. Amodeo, C. Gaibisso Le strutture ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 24 G. Amodeo, C. Gaibisso Le strutture ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 25 G. Amodeo, C. Gaibisso Le strutture ricorsive if L empty 1 t if L t .empty max(L) if t max(L') t if L t.L' max(L') otherwise // Nome e posizione del file: // Lezione_XXVII/max_1_o.c // Descrizione del contenuto del file: // funzioni per il calcolo ricorsivo // del massimo di una lista di // naturali limitando il numero // delle chiamate ricorsive // Descrizione della funzionalita' implementata: // calcola ricorsivamente il massimo degli elementi del vettore // Tipo, nome e significato dei parametri della funzione: // int vett: riferimento ad un vettore di interi // int dim: dimensione del vettore // Tipo e significato del valore restituito: // int: massimo degli elementi del vettore int max(int *vett, int dim) { // definisce una variabile di appoggio per il massimo int aux; // se il vettore e' vuoto il massimo e' 0 if (dim == 0) return(0); // se il vettore contiene un solo elemento il massimo e' l'elemento stesso if (dim == 1) return(vett[0]); Programmazione di Calcolatori: la ricorsione 26 G. Amodeo, C. Gaibisso Le strutture ricorsive // se il primo elemento e' maggiore del massimo della parte rimanente // del vettore il massimo e' il primo elemento if (vett[0] >= (aux=max(vett+1, dim-1))) return(vett[0]); else // altrimenti il massimo e' quello della parte rimanente del vettore return(max(vett+1, dim-1)); }; Programmazione di Calcolatori: la ricorsione 27 G. Amodeo, C. Gaibisso Le strutture ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 28 G. Amodeo, C. Gaibisso Le strutture ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 29 G. Amodeo, C. Gaibisso Le strutture ricorsive • Qual è il massimo di LLN? max : LN N 1 if L empty 1 t if L t .empty max(L) max(t .L') if t t 1 1 2 if L t1 .t2 . L' max(t 2 .L') otherwise Programmazione di Calcolatori: la ricorsione 30 G. Amodeo, C. Gaibisso Le strutture ricorsive 1 t max(L) max(t1 .L') if t1 t2 max(t .L') otherwise 2 if L empty if L t .empty // Nome e posizione del file: // Lezione_XXVII/max_2.c // Descrizione del contenuto del file: // funzioni per il calcolo ricorsivo if L t1 .t2 . L' // del massimo degli elementi di // una lista di naturali // Tipo, nome e significato dei parametri della funzione: // int vett: riferimento ad un vettore di interi // int dim: dimensione del vettore // Descrizione della funzionalita' implementata: // calcola ricorsivamente il massimo degli elementi del vettore // Tipo e significato del valore restituito: // int: massimo degli elementi del vettore int max(int *vett, int dim) { // se il vettore e' vuoto il massimo è 0 if (dim == 0) return(0); // se il vettore contiene un solo elemento il massimo e' // l'elemento stesso if (dim == 1) return(vett[0]); Programmazione di Calcolatori: la ricorsione 31 G. Amodeo, C. Gaibisso Le strutture ricorsive // se il primo elemento e' maggiore del secondo, il massimo e' il massimo // tra il primo elemento e gli elementi del vettore a partire dal terzo if (vett[0] >= vett[1]) { //scambia il primo elemento con il secondo scambia(vett, vett+1); return(max(vett+1, dim-1)); } else // altrimenti il massimo e' il massimo tra il II elemento e gli elementi // del vettore a partire dal terzo return(max(vett+1, dim-1)); }; Programmazione di Calcolatori: la ricorsione 32 G. Amodeo, C. Gaibisso Le strutture ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 33 G. Amodeo, C. Gaibisso Le strutture ricorsive • Esecuzione: Programmazione di Calcolatori: la ricorsione 34