Informatica B Allievi Elettrici - AA 2000-01 Le funzioni ricorsive in C.
-
Upload
pietronella-de-santis -
Category
Documents
-
view
214 -
download
0
Transcript of Informatica B Allievi Elettrici - AA 2000-01 Le funzioni ricorsive in C.
Informatica B
Allievi Elettrici - AA 2000-01
Le funzioni ricorsive in C
IL concetto di ricorsione
• La definizione basata sull’induzione
• L’iterazione e la ricorsione
• Cosa significa “ricorsivo”
• Come si realizza una funzione ricorsiva
• Come si esegue una funzione ricorsiva
• Esempi
L’induzione matematica• Si usa nelle definizioni e nelle dimostrazioni• Definizione: numeri pari
– 1) 0 è un numero pari– 2) se n è un numero pari anche n+2 è un numero
pari
• Dimostrazione: dimostro che (2n)2=4n2
(distributività della potenza di 2 risp. alla moltiplicazione)
– 1) n=1 : vero– 2) suppongo sia vero per k, lo dimostro per k+1:
(2(k+1))2=(2k+2)2=(2k)2+4k+4= (per hp di induzione) 4k2 +8k+4 = 4(k2 +2k+1) = 4(k+1)2
– 1) è il passo base, 2) è il passo di induzione
Iterazione e ricorsione
• Sono i due concetti informatici che nascono dal concetto di induzione
• L’iterazione si realizza mediante la tecnica del ciclo
• Il calcolo del fattoriale:– 0!=1– n!=n(n-1)(n-2)….1 (realizzo un ciclo)
Iterazione e ricorsione
• Il calcolo del fattoriale mediante una tecnica iterativa:int fattoriale (int n)
{ int i, f;
f = 1;
for (i=1; i <= n; i=i+1)
f = f * i;
return f;
}
La ricorsione• Dal latino re-currere (ricorrere, fare
ripetutamente la stessa azione)
• In informatica: si tratta di procedure (funzioni) che richiamano se stesse
• Il concetto di ricorsione viene usato nel contesto di:– algoritmi– strutture dati
Definizione ricorsiva del fattoriale
1) n!=0 se n=0
2) n!= n*(n-1)! se n>0– riduce il calcolo a un calcolo più semplice– ha senso perché si basa sempre sul fattoriale del
numero più piccolo, che io conosco– ha senso perché si arriva a un punto in cui non è
più necessario riusare la def. 2) e invece si usa la 1)
– 1) è il passo base, 2) è il passo di ricorsione
Algoritmo ricorsivo per la definizione del fattoriale
int fattoriale (int n)
{ if (n==0) return 1;
else return n*fattoriale(n-1);
}• Quando si può dire che una ricorsione è ben definita?
Informalmente: se ogni volta che applico la ricorsione sono significativamente più vicino al passo base, allora la definizione non è circolare.
Esempio di traccia• Calcoliamo il fattoriale di 4:
• 4=0? No: calcoliamo il fattoriale di 3 e molt. per 4
• 3=0? No: calcoliamo il fattoriale di 2 e molt. per 3
• 2=0? No: calcoliamo il fattoriale di 1 e molt. per 2
• 1=0? No: calcoliamo il fattoriale di 0 e molt. per 1
• 0=0? Si: il fattoriale di 0 è 1. Risaliamo:
• il fattoriale di 1 è 1 per il fattoriale di 0 cioè 1*1=1
• il fattoriale di 2 è 2 per il fattoriale di 1 cioè 2*1=2
• il fattoriale di 3 è 3 per il fattoriale di 2 cioè 3*2=6
• il fattoriale di 4 è 4 per il fattoriale di 3 cioè 4*6=24
Altri esempi di funzioni ricorsive• La funzione esponenziale
• I numeri di Fibonacci (dinamiche di popolazione)
• Il Massimo Comun Divisore (algoritmo di Euclide)
• Il problema delle torri di Hanoi
La funzione esponenzialeIterativo:
1) xy=1 se y=0
2) xy=x*x*…x (y volte) se y>0
Ricorsivo:
1) xy=1 se y=0
2) xy=x*x(y-1) se y>0
Iterativo:int esponenziale (int x,y)
{ int i, e;
e = 1;
for (i=1; i <= y; i=i+1)
e = e * x;
return e;
}
Ricorsivo:int esponenziale (int x,y)
{ if (y==0) return 1;
else return x*esponenziale(x,y-1);
}
I numeri di Fibonacci
1) fib(n)=1 se n=0 opp. n=1
2) fib(n)=
fib(n-1) + fib(n-2) se n>1
Vengono usati per modellare la crescita di animali per diverse generazioni
int fib(int n)
{if ((n==0) || (n==1)) return 1;
else return (fib(n-1) + fib(n-2));
}
Dinamiche di popolazioneT0: **(1)
T1: ** (1)
T2: ** ** (2)
T3: ** ** ** (3)
T4: ** ** ** ** ** (5)
T5: ** ** ** ** ** ** ** ** (8)
T6: ** ** ** ** ** ** ** ** ** ** ** ** ** (13)
T7: ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** (21) …etc.
Il MCDDefinizione:
1) MCD(m,n)=m se m=n
2a) MCD(m,n)= MCD(m-n,n) se m>n
2b) MCD(m,n)=MCD(m,n-m) se n>m
esempio:
MCD(21,56) = MCD(21,35) = MCD(21,14)=
= MCD(7,14) = MCD(7,7) = 7
IL MCDIterativo:
int mcd (int m,n)
{ while (m != n)
if (m>n)
m=m-n;
else n=n-m;
return m;
}
Ricorsivo:
int mcd(int m,n)
{ if (m==n) return m;
else if (m>n)
return mcd(m-n,n);
else return mcd(m,n-m);
}
• Attenzione alla condizione di terminazione!!!!!
• N.B. è sempre possibile trovare un corrispondente iterativo di un programma ricorsivo!!!
Le torri di Hanoi http://www.cs.cmu.edu/~cburch/survey/recurse/hanoi.html
Problema: spostare tutti i dischi dalla torre A alla torre B (usando la torre C come “supporto intermedio”) in modo che si trovino nello stesso ordine
Le torri di Hanoi
• Scriveremo una funzione ricorsiva che prende come parametro il numero del disco più grande che vogliamo spostare (da 0 a 5 come nel disegno)
• La funzione prenderà anche tre parametri che indicano:– da quale asta vogliamo partire (source),
– a quale asta vogliamo arrivare (dest),
– l’altra asta, che possiamo usare come supporto temporaneo (spare).
Le torri di Hanoi: strategia
Ridurremo il problema a quello di spostare 5 dischi dalla torre Calla torre B, dopo che il disco 5 è stato già messo nella posizione giusta
Le torri di Hanoi: strategia• Muoviamo il disco 4 e i più piccoli da A (source) a C
(spare), usando B (dest) come appoggio temporaneo. Lo facciamo usando ricorsivamente la stessa procedura. Alla fine di questo, avremo tutti i dischi da 4 a 0 sulla torre C.
• Ora possiamo muovere il disco 5 da A (source) a B (dest).
• Infine, vogliamo che i dischi dal 4 al più piccolo siano mossi da C (spare) a B (dest). Lo rifacciamo chiamando ricorsivamente la stessa procedura.
• Alla fine, avremo i dischi dal 5 al più piccolo (0) su B (dest).
Le torri di Hanoi: pseudocodiceFUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
move disk from source to dest
ELSE:
MoveTower(disk - 1, source, spare, dest)
/* (Passo 1) */
move disk from source to dest // /* (Passo 2) */
MoveTower(disk - 1, spare, dest, source) // /* (Passo 3) */
END IF
Nota: l’algoritmo aggiunge un caso base: quando il disco è il più piccolo (il numero 0). In questo caso possiamo muoverlo direttamente perché non ne ha altri sopra. Negli altri casi, seguiamo la procedura descritta per il disco 5.
Le chiamate a sottoprogramma:cosa avviene a livello macchina?
• In seguito a una chiamata a sottoprogramma, il programma in corso viene sospeso e il controllo deve passare al sottoprogramma
• A livello macchina: – Salvataggio del program counter (PC) e del contesto del
programma chiamante
– Assegnazione al PC dell’indirizzo del sottoprogramma
– Esecuzione del sottoprogramma
– Ritorno al programma chiamante con ripristino del suo contesto
Problema• In generale, una procedura può essere chiamata un
numero imprecisato di volte• Ogni chiamata a procedura richiede allocazione di
spazio di memoria per le sue variabili locali• Abbiamo visto che ci sono procedure che
richiamano se stesse (ricorsione)
• In quest’ultimo caso il compilatore non può sapere quanto spazio allocare per le variabili del programma
Il record di attivazioneOgni sottoprogramma (incluso il main) ha
associato un record di attivazione. Contiene:– tutti i dati relativi all’ambiente locale del
sottoprogramma– l’indirizzo di ritorno nel programma chiamante– altri dati utili
In effetti, per ogni attivazione di sottoprogramma si crea un diverso record di attivazione
Richiamiamo: lo STACKUna porzione della memoria di lavoro, chiamata stack (pila: modalità
LIFO (Last in First Out)) permette al sistema operativo di gestire i processi e di eseguire le chiamate a sottoprogramma.
Lo Stack Pointer (puntatore alla pila) è un registro che contiene l’indirizzo della prima parola di memoria da leggere nello stack
Stack pointer=312312
312311
310
303
...Operazione di inserimento: -incremento SP -scrittura in parola indirizzata da SPOperazione di estrazione: -lettura da parola indirizzata da SP -decremento SP
Esempio
Main
P1
P2
Chiama P1
Variabili globali
Act. Record Main
Act. Record P1(1)
Act. Record P2(1)
Act. Record P1(2)
Act. Record P2(2)
etc.
...
Esempio di record di attivazione nel caso del fattoriale
4
3
2
1
0 1
1*1=1
2*1=2
3*2=6
6*4=24
n fattoriale
Quarta chiamata
Quinta chiamata
Terza chiamata
Seconda chiamata
Prima chiamata
Fatt(0)=1