1 Introduzione alla Ricorsione Corso di Informatica A Vito Perrone.
20
1 Introduzione alla Ricorsione Corso di Informatica A Vito Perrone
-
Upload
fiorella-corradini -
Category
Documents
-
view
218 -
download
3
Transcript of 1 Introduzione alla Ricorsione Corso di Informatica A Vito Perrone.
1
Introduzione alla Ricorsione
Introduzione alla Ricorsione
Corso di Informatica A
Vito Perrone
2Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
IndiceIndice
•La formulazione in termini ricorsivi di problemi e algoritmi
•La ricorsione come strumento di programmazione
•L’esecuzione dei sottoprogrammi ricorsivi
•Ulteriori esempi
3Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
La formulazione in termini ricorsivi
di problemi e algoritmi
•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)
4Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
Un esempio classicoUn 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.
5Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
Esempi matematici (1)Esempi matematici (1)
x + 0 = x;x + y = x + Successore(y–1) = Successore (x + (y–1)):
1+3 =Successore (1+2) = Successore(Successore(1+1)) = Successore(Successore(Successore(1+0))) =Successore(Successore(Successore(1))) =Successore(Successore(2)) = Successore(3) = 4
6Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
Esempi matematici (2)Esempi matematici (2)
• I numeri di Fibonacci, F = {f0, ..., fn}:
f0 = 0
f1 = 1
Per n > 1, fn = f n–1 + fn–2
• Esempio:
f0 = 0
f1 = 1
f2 = f1 + f0 = 1 + 0 = 1
f3 = f2 + f1 = 1 + 1 = 2
f4 = f3 + f2 = 2 + 1 = 3
7Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
Esempi matematici (3)Esempi matematici (3)
• La sommatoria di una sequenza di numeri
00
1
i
ia
n
iin
n
ii aaa
11
1
1
Es. {2,5,7,9} n=4
8Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
Esempi matematici (4)Esempi matematici (4)
• La lista inversa L–1 di una lista di elementi L = {a1, ..., an}:se n = 1, L–1 = L;altrimenti, L–1 = {an, (Ln–1)–1}
Dove Ln–1 indica la lista ottenuta da L cancellando l’ultimo elemento an.
• Esempio:
2,7,5,4–1 = 4, 2,7,5–1
= 4,5, 2,7–1
= 4,5,7, 2–1
= 4,5,7,2
9Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
La ricorsione come strumentodi programmazione
La ricorsione come strumentodi programmazione
• Programma Fibonacci:
int fibonacci (int n) {
int ris;
if (n == 0) ris = 0;else if (n == 1) ris = 1;else ris = fibonacci(n–1) +
fibonacci(n–2);return ris;
}
10Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
Esempio Fattoriale
• 5! = 5*4*3*2*1
• n! = n*(n-1)!
• 0! = 0 <- convenzione
11Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
L’esecuzione di sottoprogrammi ricorsivi (1)
L’esecuzione di sottoprogrammi ricorsivi (1)
• Calcolo del fattoriale di 3 (secondo lo schema conosciuto):− 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
12Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
record di attivazione
Seconda attivazione
2
Terza attivazione1
Quarta attivazione
0
1*1 = 1
2*1 = 2
Prima attivazione
n FattRic
3 3*2 = 6
1
L’esecuzione di sottoprogrammi ricorsivi (2)
L’esecuzione di sottoprogrammi ricorsivi (2)
13Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
• Passaggio parametri -anche- per indirizzo:
void incrementa(int *n, int m){
if (m != 0){
*n = *n + 1; incrementa(n, m–1);
}}
L’esecuzione di sottoprogrammi ricorsivi (3)
L’esecuzione di sottoprogrammi ricorsivi (3)
14Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
L’esecuzione di sottoprogrammi ricorsivi (4)
L’esecuzione di sottoprogrammi ricorsivi (4)
y
3
Area dati della funzione chiamante
x
2
Prima attivazione
n m
3
3
Seconda attivazione
2
4
Terza attivazione1
5
Quarta attivazione
0
5
15Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
L’esecuzione di sottoprogrammi ricorsivi (5):
la gestione a pila della memoria (a)
L’esecuzione di sottoprogrammi ricorsivi (5):
la gestione a pila della memoria (a)
Variabili globali
main
record di attivazione del main
P1
record di attivazione di P1
P2’
record di attivazione di P2’
P3
record di attivazione di P3
P2”record di attivazione di P2"
16Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
P1 P2’ P3 P2”main
Variabili globali
record di attivazione del main
record di attivazione di P1
record di attivazione di P2’
record di attivazione di P3
record di attivazione di P2"
P3P2’
L’esecuzione di sottoprogrammi ricorsivi (6):
la gestione a pila della memoria (b)
L’esecuzione di sottoprogrammi ricorsivi (6):
la gestione a pila della memoria (b)
17Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
Variabili globali
record di attivazione del main
record di attivazione di P1
record di attivazione di P2’
P3P2’
main P1 P2’ P3 P2”
P4
record di attivazione di P4
P2’P1main
L’esecuzione di sottoprogrammi ricorsivi (7):
la gestione a pila della memoria (c)
L’esecuzione di sottoprogrammi ricorsivi (7):
la gestione a pila della memoria (c)
18Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
Ulteriori esempi (1)Ulteriori esempi (1)/* Programma RicPalindr*/
#include <stdio.h>#include <string.h> typedef enum {false, true} boolean; void main (){
#define LunghMaxStringa 100
char Stringa1[LunghMaxStringa];boolean OK;unsigned LunghStringa;
boolean Palindrome (char *PC, char *UC);
/* L’istruzione seguente assume che i caratteri componenti la stringa non siano spazi */
scanf ("%s", Stringa1);LunghStringa = strlung (Stringa1);if (LunghStringa == 0)
printf ("La stringa è palindroma");else…
19Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
Ulteriori esempi (2)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)…
20Ricorsione
Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl
/* 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);}
Ulteriori esempi (3)Ulteriori esempi (3)
