IEIM
Esercitazione IV
2014-2015
Alessandro A. Nacci
alessandro.nacci@polimi.it - alessandronacci.it
2
RICORSIONE
Divide et impera
•
Metodo di approccio ai problemi che consiste nel dividere il problema dato in problemi più semplici•
I risultati ottenuti risolvendo i problemi più semplici vengono combinati insieme percostituire la soluzione del problema originale
•
Generalmente, quando la semplificazione del problema consiste essenzialmente nellasemplificazione dei DATI da elaborare (ad es. la riduzione della dimensione del vettore da
elaborare), si può pensare ad una soluzione ricorsiva
4
La ricorsione (1)
•
Una funzione è detta ricorsiva se chiama se stessa•
Se due funzioni si chiamano l’un l’altra, sono dette mutuamente ricorsive•
La funzione ricorsiva sa risolvere direttamente solo casi particolari di un problema detti casi di base: se viene invocata passandole dei dati checostituiscono uno dei casi di base, allora restituisce un risultato
•
Se invece viene chiamata passandole dei dati che NON costituiscono uno dei casi di base, allora chiama se stessa (passo ricorsivo) passando deiLa ricorsione (II)
•
Ad ogni chiamata si semplificano/riducono i dati, così ad un certo punto si arriva ad uno dei casi di base•
Quando la funzione chiama se stessa, sospende la sua esecuzione per eseguire la nuova chiamata•
L’esecuzione riprende quando la chiamata interna a se stessa termina•
La sequenza di chiamate ricorsive termina quando quella più interna (annidata) incontra uno dei casi di base•
Ogni chiamata alloca sullo stack (in stack frame diversi) nuove istanze dei parametri e delle variabili locali (non static)6
Esempio: il fattoriale
Esempio: il fattoriale - passo per passo
8
Ricorsione - Esercizio 1
•
Scrivere una funziona ricorsiva che calcoli ricorsivamente la somma di tutti i numeri compresi tra 0 ed x•
Il prototipo della funzione è: int ric(int x)Ricorsione - Esercizio 1
•
Scrivere una funziona ricorsiva che calcoli ricorsivamente la somma di tutti i numeri compresi tra 0 ed x•
Il prototipo della funzione è: int ric(int x)9
Ricorsione - Esercizio 1I
•
Scrivere le versioni ricorsiva ed iterativa di una funziona checalcoli il seguente valore
Ricorsione - Esercizio 1I
•
Scrivere le versioni ricorsiva ed iterativa di una funziona checalcoli il seguente valore
10
Ricorsione - Esercizio 1I
•
Scrivere le versioni ricorsiva ed iterativa di una funziona checalcoli il seguente valore
Ricorsione - Esercizio 1I
•
Scrivere le versioni ricorsiva ed iterativa di una funziona checalcoli il seguente valore
10
Qualche considerazione
•
L’apertura delle chiamate ricorsive semplifica il problema, ma non calcola ancora nulla•
Il valore restituito dalle funzioni viene utilizzato per calcolare il valore finale man mano che sichiudono le chiamate ricorsive: ogni chiamata genera valori intermedi a partire dalla fine
•
Nella ricorsione vera e propria non c’è un mero passaggio di un risultato calcolato nella chiamata più interna a quelle più esterne, ossia le return non si limitano a passare indietro invariato un valore, ma c’è un’elaborazione intermediaQuando utilizzare la ricorsione
12
Quando utilizzare la ricorsione
Ricorsione - Esercizio III
•
Analizzare il comportamento della seguente funzione ricorsiva mostrando l’andamentodelle variabili, considerando i seguenti input:
•
funzione(231,0)•
Dire quale funzione espleta14
#include <stdio.h>
#define DIMENSIONE 10
int mia_funzione(int num, int part) { if (num == 0)
return part;
else {
return mia_funzione(num/10, part*10 + num%10);
} }
int main() {
int a = reverse2(21,0);
printf("%d\n",a);
}
Ricorsione - Esercizio III - Soluzione
int funzione (int num, int port) {
if (num == 0) return port;
else
return funzione (num/10, port*10 + num%10);
num = 231 port = 0
~ STEP = 0
Ricorsione - Esercizio III - Soluzione
16
int funzione (int num, int port) {
if (num == 0) return port;
else
return funzione (num/10, port*10 + num%10);
}
num = 231 port = 0
~ STEP = 0
num = 23 port = 0
~ STEP = 1
Ricorsione - Esercizio III - Soluzione
int funzione (int num, int port) {
if (num == 0) return port;
else
return funzione (num/10, port*10 + num%10);
num = 231 port = 0
~ STEP = 0
num = 23 port = 0
~ STEP = 1
num = 2 port = 0
~ STEP = 2
Ricorsione - Esercizio III - Soluzione
18
int funzione (int num, int port) {
if (num == 0) return port;
else
return funzione (num/10, port*10 + num%10);
}
num = 231 port = 0
~ STEP = 0
num = 23 port = 1
~ STEP = 1
num = 2
port = 10+3 = 13
~ STEP = 2
num = 0
port = 13 *10 + 2 = 132
~ STEP = 3
Ricorsione - Esercizio III - Soluzione
int funzione (int num, int port) {
if (num == 0) return port;
else
return funzione (num/10, port*10 + num%10);
num = 231 port = 0
~ STEP = 0
num = 23 port = 1
~ STEP = 1
num = 2
port = 10+3 = 13
~ STEP = 2
num = 0
port = 13 *10 + 2 = 132
132 STEP = 3
Ricorsione - Esercizio III - Soluzione
20
int funzione (int num, int port) {
if (num == 0) return port;
else
return funzione (num/10, port*10 + num%10);
}
num = 231 port = 0
~ STEP = 0
num = 23 port = 1
~ STEP = 1
num = 2
port = 10+3 = 13
132 STEP = 2
num = 0
port = 13 *10 + 2 = 132
132 STEP = 3
Ricorsione - Esercizio III - Soluzione
int funzione (int num, int port) {
if (num == 0) return port;
else
return funzione (num/10, port*10 + num%10);
num = 231 port = 0
~ STEP = 0
num = 23 port = 1
~ STEP = 1
num = 2
port = 10+3 = 13
132 STEP = 2
num = 0
port = 13 *10 + 2 = 132
132 STEP = 3
Ricorsione - Esercizio III - Soluzione
22
int funzione (int num, int port) {
if (num == 0) return port;
else
return funzione (num/10, port*10 + num%10);
}
num = 231 port = 0
~ STEP = 0
num = 23 port = 1
132 STEP = 1
num = 2
port = 10+3 = 13
132 STEP = 2
num = 0
port = 13 *10 + 2 = 132
132 STEP = 3
Ricorsione - Esercizio III - Soluzione
int funzione (int num, int port) {
if (num == 0) return port;
else
return funzione (num/10, port*10 + num%10);
num = 231 port = 0
~ STEP = 0
num = 23 port = 1
132 STEP = 1
num = 2
port = 10+3 = 13
132 STEP = 2
num = 0
port = 13 *10 + 2 = 132
132 STEP = 3
Ricorsione - Esercizio III - Soluzione
24
int funzione (int num, int port) {
if (num == 0) return port;
else
return funzione (num/10, port*10 + num%10);
}
num = 231 port = 0
132 STEP = 0
num = 23 port = 1
132 STEP = 1
num = 2
port = 10+3 = 13
132 STEP = 2
num = 0
port = 13 *10 + 2 = 132
132 STEP = 3
Un esercizio complesso:
Albero genealogico
L’albero genealogico
•
Scrivere un programma C che sia in grado di rappresentare e gestire un albero genealogico26
•
In particolare, vogliamo poter fare:-
Creare una persona-
Rappresentare di una popolazione-
Aggiungere figli ad una persona-
Elencare i figli e i nipoti dato un antenatoUna famosa struttura dati: l’albero
P0
P1 P2 P3
P4 P5
Una famosa struttura dati: l’albero
27
P0
P1 P2 P3
P4 P5
ogni cerchio si chiama “nodo”
Una famosa struttura dati: l’albero
P0
P1 P2 P3
P4 P5
ogni cerchio si chiama “nodo”
PADRE
FIGLIO
Una famosa struttura dati: l’albero
27
P0
P1 P2 P3
P4 P5
ogni cerchio si chiama “nodo”
PADRE
FIGLIO
PADRE
FIGLI
Una famosa struttura dati: l’albero
P0
P1 P2 P3
P4 P5
ogni cerchio si chiama “nodo”
PADRE
FIGLIO
PADRE
FIGLI
PADRE
FIGLIO
Una famosa struttura dati: l’albero
27
P0
P1 P2 P3
P4 P5
ogni cerchio si chiama “nodo”
PADRE
FIGLIO
PADRE
FIGLI
PADRE
FIGLIO PADRE
FIGLIO
Una famosa struttura dati: l’albero
P0
P1 P2 P3
P4 P5
ogni cerchio si chiama “nodo”
PADRE
FIGLIO
PADRE
FIGLI
PADRE
FIGLIO PADRE
FIGLIO
PADRE
FIGLIO
Una famosa struttura dati: l’albero
27
P0
P1 P2 P3
P4 P5
RADICE
FOGLIA FOGLIA
FOGLIA FOGLIA
ogni cerchio si chiama “nodo”
PADRE
FIGLIO
PADRE
FIGLI
PADRE
FIGLIO PADRE
FIGLIO
PADRE
FIGLIO
Una famosa struttura dati: l’albero
P0
P1 P2 P3
P4 P5
RADICE
FOGLIA FOGLIA
FOGLIA FOGLIA
ogni cerchio si chiama “nodo”
PADRE
FIGLIO
PADRE
FIGLI
PADRE
FIGLIO PADRE
FIGLIO
PADRE
FIGLIO
Una famosa struttura dati: l’albero
27
P0
P1 P2 P3
P4 P5
Può essere utile per rappresentare un albero genealogico?
RADICE
FOGLIA FOGLIA
FOGLIA FOGLIA
ogni cerchio si chiama “nodo”
PADRE
FIGLIO
PADRE
FIGLI
PADRE
FIGLIO PADRE
FIGLIO
PADRE
FIGLIO
OVVIAMENTE SI
•
OGNI NODO DELL’ALBERO SARA’ PER NOI UNA PERSONA==
PUna Persona
•
SESSO•
NOME•
ETA?•
CHI SONO I GENITORI?•
CHI SONO I FIGLI?•
QUANTI FIGLI?29
Una Popolazione
•
Una popolazione è rappresentata da un insieme di persone•
Ogni persona ha un suo indice (numero univoco di identificazione)•
Esiste un numero di persone della1 2 3 4 5 6 7
Una Persona nella popolazione
•
SESSO•
NOME•
ETA?•
CHI SONO I GENITORI?•
CHI SONO I FIGLI?•
QUANTI FIGLI?cardinalità 31
1 2 3 4 5 6 7
Li rappresentiamo con l’indice della persona nella popolazione
Persona e Popolazione (codice C)
Persona e Popolazione (codice C)
32
Persona e Popolazione (codice C)
Creazione di una persona
33
Creazione di una persona
Aggiunta persona alla popolazione
34
Aggiunta persona alla popolazione
Aggiunta di un figlio
35
Aggiunta di un figlio
Funzioni di stampa a schermo
36
Funzioni di stampa a schermo
Funzioni di stampa a schermo
36
38
Tutte il materiale sarà disponibile sul mio sito internet!
alessandronacci.it
