10. Programmazione Ricorsiva
Ing. Simona Colucci
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
Indice
• La formulazione in termini ricorsivi di problemi e
algoritmi
• La ricorsione come strumento di programmazione
• L’esecuzione dei sottoprogrammi ricorsivi
• Ulteriori esempi
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
La formulazione in termini ricorsivi
di problemi e algoritmi
• La ricorsione: durante l’esecuzione di un
sottoprogramma P avviene una nuova chiamata allo
stesso P
– ricorsione indiretta :
• P chiama -durante la sua esecuzione- un altro sottoprogramma Q
• Q a sua volta chiama un terzo R, …
• R chiama nuovamente P
– ricorsione diretta: P chiama se stesso durante la propria
esecuzione
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
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.
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
Un esempio matematico
DEE - Politecnico di Bari
• La sommatoria di una sequenza di numeri
0
a
i
i 1
n 1
a
i 1
i
0
n
 an 1   ai
i 1
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
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;
}
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
L’esecuzione di sottoprogrammi
ricorsivi
• Calcolo del fattoriale di 3 con l’uso dello schema di
chiamata ai sottoprogrammi noto:
– Il valore del parametro attuale, 3, viene copiato nel parametro
formale, n
– Ha inizio l’esecuzione di FattRic. Essa giunge a n*FattRic(2), il cui
risultato dovrebbe essere assegnato alla cella FattRic per poi
essere passato al chiamante
– A questo punto avviene la nuova chiamata di FattRic.
– Il nuovo valore del parametro attuale, 2, viene copiato nella cella
n, cancellando il precedente valore 3
Necessità di associare un aerea dati per ogni esecuzione
del sottoprogramma: attivazione
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
L’esecuzione di sottoprogrammi
ricorsivi
record di attivazione
n
FattRic
3
3*2 = 6
Prima
attivazione
2
2*1 = 2
Seconda
attivazione
1
0
1*1 = 1
1
Terza
attivazione
Quarta
attivazione
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
L’esecuzione di sottoprogrammi
ricorsivi
Passaggio parametri per indirizzo:
void
{
incrementa(int *n, int m)
if (m != 0)
{
*n = *n + 1;
incrementa(n, m–1);
}
}
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
L’esecuzione di sottoprogrammi
ricorsivi
Sistemi Informativi
DEE - Politecnico di Bari
incrementa(&x, y)
x
2 3 4 55
n
y
Area dati della
funzione
chiamante
3
m
3
Prima
attivazione
2
Seconda
attivazione
Terza
attivazione
1
0
Quarta
attivazione
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
L’esecuzione di sottoprogrammi ricorsivi:
la gestione a pila della memoria
• La memoria per l’esecuzione di un sottoprogramma
ricorsivo non può essere allocata staticamente
• La conseguente perdita di efficienza può essere limitata
usando una disciplina LIFO (Last In First Out) per la
chiamata dei sottoprogrammi: la prima esecuzione a
terminare è sempre quella relativa all’ultima chiamata
• L’organizzazione di memoria utilizzata è la pila
• Ogni aerea dati è chiamata record di attivazione
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
main
P1
L’esecuzione di sottoprogrammi ricorsivi
la gestione a pila della memoria (a)
P2’
P3
P2”
record di
attivazione
di P2"
record di
attivazione
di P3
record di
attivazione
di P2’
record di
attivazione
di P1
record di
attivazione
del main
Variabili globali
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
main
P1
L’esecuzione di sottoprogrammi ricorsivi(6)
la gestione a pila della memoria (b)
P2’
P2’
P3
P3
P2”
record di
attivazione
di P2"
record di
attivazione
di P3
record di
attivazione
di P2’
record di
attivazione
di P1
record di
attivazione
del main
Variabili globali
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
main
P1
L’esecuzione di sottoprogrammi ricorsivi(7)
la gestione a pila della memoria (c)
P2’
P2’
P3
P3
P4
main
P1
P2’
P2”
record di
attivazione
di P4
record di
attivazione
di P2’
record di
attivazione
di P1
record di
attivazione
del main
Variabili globali
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
Ulteriori esempi (1)
DEE - Politecnico di Bari
/* Programma RicPalindr*/
#include <stdio.h>
#include <string.h>
typedef
enum {false, true} boolean;
void
main ()
{
#define
char
boolean
unsigned
LunghMaxStringa
100
Stringa1[LunghMaxStringa];
OK;
LunghStringa;
boolean
Palindrome (char *PC, char *UC);
/* L’istruzione seguente assume che i caratteri componenti la stringa non siano spazi */
scanf ("%s", Stringa1);
LunghStringa = strlen (Stringa1);
if (LunghStringa == 0)
printf ("La stringa è palindroma");
else
…
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
Ulteriori esempi (2)
/* Programma RicPalindr*/
…
else
{
/* Viene chiamata la funzione Palindrome passando per indirizzo il primo e
l'ultimo carattere della stringa da analizzare */
OK = Palindrome (&Stringa1[0], &Stringa1[LunghStringa–1];
if (OK == true)
printf ("La stringa è palindroma”);
else
printf ("La stringa non è palindroma");
}
}
boolean Palindrome (char *PC, char *UC)
…
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011
Sistemi Informativi
Ulteriori esempi (3)
DEE - Politecnico di Bari
/* Programma RicPalindr*/
…
boolean Palindrome (char *PC, char *UC)
{
if
(PC >= UC)
/* Se la stringa è vuota o è costituita da un solo carattere */
return true;
else if (*PC != *UC)
/* Se il primo e l'ultimo carattere sono diversi */
return false;
else
/* Chiama se stessa ricorsivamente escludendo il primo e l'ultimo carattere */
return Palindrome (PC+1, UC–1);
}
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B)- A.A. 2010-2011