La Programmazione Ricorsiva
La ricorsione: che cos’è?
La ricorsione: che cos’è?
Un sottoprogramma P chiama -durante la sua esecuzione- un altro sottoprogramma Q
Q a sua volta chiama un terzo R, …
R chiama nuovamente P: (ricorsione indiretta)
Oppure P chiama se stesso durante la propria esecuzione (ricorsione diretta)
2
Un esempio classico
Individuare, in un gruppo di palline l’unica pallina di peso maggiore delle altre facendo uso di una bilancia “a basculla” (Per semplicità: il numero di palline sia una potenza di 3)
Algoritmo Pesate:
• Se il gruppo di palline consiste in una sola pallina, allora essa è banalmente la pallina cercata, altrimenti procedi come segue.
• Dividi il gruppo di palline in tre e confronta due dei tre sottogruppi.
• Se i due gruppi risultano di peso uguale scarta entrambi, altrimenti scarta il gruppo non pesato e quello risultato di peso minore.
• Applica l’algoritmo Pesate al gruppo rimanente.
3
Altri esempi di ricorsione
La sommatoria di una sequenza di numeri
Fattoriale:
In arte e non solo…
4
Fact(n)=n*Fact(n-1) Fact(0)=1
Scopo della programmazione ricorsiva
Lo scopo è quelo di risolvere un problema facendo riferimento allo stesso problma su scala ridotta
La condizione di terminazione avviene quando si identifica uno o più casi semplici con soluzione immediata
La struttura di un algoritmo ricorsivo è il seguente
if (è il caso semplice) risolvilo
else
usa la ricorsione su dati ridotti 5
ris = FattRic(3) ris = FattRic(2) ris = FattRic(1) ris = FattRic(0) La ricorsione come strumento
di programmazione
Calcolo del Fattoriale in modo ricorsivo:
int FattRic(int n) {
int ris;
if (n == 0) ris = 1;
else ris = n * FattRic(n–1);
return ris;
1 1 2 6
6
Fact(n)=n*Fact(n-1) Fact(0)=1
Moltiplicazione
Ideare un procedimento ricorsivo per calcolare il prodotto di due interi
Nota: A*1=A; A*B = A + A*(B-1)
int MulRic(int a, int b) {
int ris;
if (b == 0) ris = a;
else ris = a + MulRic(a ,b–1);
return ris;
}
7
Successione di Fibonacci
"Quante coppie di conigli si ottengono dopo N mesi (salvo i casi di morte) supponendo che ogni coppia dia alla luce un'altra coppia ogni mese e che le coppie più giovani siano in grado di riprodursi già al secondo mese di vita?”.
Nota:
Fib(n)=Fib(n-1)+Fib(n-2)
Fib(0)=0; Fib(1)=1;
int fibRic (int n) { int ris;
if (n == 0) ris = 0;
else if (n == 1) ris = 1;
else ris = fibRic(n–1) + fibRic(n–2);
return ris;
}
8
Esercizio: Massimo di un array
Ideare un procedimento ricorsivo per calcolare il massimo di un array di interi
Idea: max(vect[0 : N]) =max(vect[0],max(vect[1 : N]))
9
int max(int *array, int n){
int maxs;
if (n==1) return array[0]; /*Caso Array 1 elemento*/
if (n==2){ /*Caso Base*/
if (array[0]>array[1]) return array[0];
else return array[1];
}
maxs = max(&array[1],n-1); /*Risolvi Problema Ridotto*/
if (array[0]>maxs)return array[0];
else return maxs;
}
Identificazione di una stringa palindroma
Nel Main
int lungStringa;
char myString[30];
lunghStringa = strlen(myString);
...
if (palRic(&myString[0], &myString[LunghStringa–1]) printf("La stringa è palindroma”);
else printf("La stringa non è palindroma");
...
Funzione Ricorsiva
int palRic (char, *PC, char *UC){
/* stringa vuota o un solo carattere */
if (PC >= UC) return 1;
else if (*PC != *UC) return 0;
10
