Ricorsione - Dipartimento di Ingegneria informatica...

RicorsioneCorso di Fondamenti di InformaticaIngegneria delle Comunicazioni – BCORIngegneria Elettronica – BELR

Unità 5

Domenico Daniele Bloisi

Docenti

Parte I – prof. Silvio Salza

[email protected]@dis.uniroma1.it

http://www.dis.uniroma1.it/~salza/fondamenti.htm

Parte II – ing. Domenico Daniele Bloisi, PhD

[email protected]

http://www.dis.uniroma1.it/~bloisi/didattica/fondin f1112.html

Nota: %7E corrisponde alla tilde ~

2011/2012RicorsioneUnità 5

Pagina 2

Informazioni Generali

ing. Domenico Daniele Bloisi, PhD

Dipartimento di Informatica e SistemisticaDipartimento di Informatica e SistemisticaVia Ariosto 25(adiacente Piazza Dante,

A fermate Manzoni, Vittorio Emanuele,Tram 3 fermata via Labicana)

mailto:[email protected]:[email protected]

http://www.dis.uniroma1.it/~bloisi


Pagina 3

Ricevimento

Su appuntamento. Inviare una email per conferma.conferma.

DIS, via Ariosto 25II piano, stanza B211

Si consiglia di controllare la bacheca degli avvisiavvisihttp://www.dis.uniroma1.it/~bloisi/didattica/fondin f1112.html#Avvisi


Pagina 4

Sommario – Unità 5

• Definizione di funzioni• Passaggio dei parametri• Esecuzione di una funzione• Esecuzione di una funzione• Variabili dichiarate in una funzione: scope• Organizzazione di un programma• Domini definiti induttivamente• Ricorsione e funzioni ricorsive• Gestione della memoria a run -time

Pagina 52011/2012

• Gestione della memoria a run -time• Ricorsione multipla

RicorsioneUnità 5

Organizzazione di un programmaProgrammi complessi possono essere organizzati in più file.

Questo consente una maggiore leggibilità e possibilità di Questo consente una maggiore leggibilità e possibilità di riuso .

I file contenenti specifiche di programmi si distin guono in

• file di intestazione o header (estensione .h)

• file di implementazione (estensione .c)

Nei file header vengono inserite solamente le

Pagina 62011/2012

Nei file header vengono inserite solamente le dichiarazioni delle funzioni, mentre nei file di implementazione anche il corpo che implementa la funzione (definizione ).

RicorsioneUnità 5

Organizzazione di un programma

Solitamente la funzione main si trova in un file separato da quello in cui vengono definite altre funzioni.funzioni.

Ogni file che usa funzioni definite altrove deve includere il relativo file header ( non il file con l’implementazione .c !)

Pagina 72011/2012RicorsioneUnità 5

Esempio

File f.h

// dichiarazione delle funzioni// dichiarazione delle funzioni// radiceQuadrata e stampadouble radiceQuadrata(double x);void stampa(double x);


EsempioFile f.c

#include <stdio.h>#include <math.h>#include <math.h>#include "f.h"// implementazione della funzione// radiceQuadratadouble radiceQuadrata(double x) {

return sqrt(x);}

Pagina 92011/2012

}// implementazione della funzione stampavoid stampa(double x) {

printf("%f\n", x);}

RicorsioneUnità 5

Esempio

File main.c

#include "f.h"#include "f.h"// implementazione della funzione mainint main(){

stampa(radiceQuadrata(25));}

Pagina 102011/2012

}

RicorsioneUnità 5

Compilazione

File multipli devono essere compilati indicando tutti (e soli) i file .c

Esempiogcc -o test f.c main.c


Domini definiti induttivamente

Un dominio è definito in modo induttivo se è definito, direttamente o indirettamente, in termini di se stesso.termini di se stesso.

Esempio

La definizione induttiva dell’insieme N dei numeri naturali consiste nelle clausole:

1. 0 ∈∈∈∈ N ∈∈∈∈ ⇒⇒⇒⇒ ∈∈∈∈

caso di base

Pagina 122011/2012

1. 0 ∈∈∈∈ N 2. n ∈∈∈∈ N ⇒⇒⇒⇒ (n + 1) ∈∈∈∈ N3. null’altro è in N

stabilisce che N è “il più piccolo insieme” che soddisfa 1 e 2

clausola induttiva

RicorsioneUnità 5

Principio di induzione matematica

Il principio d'induzione asserisce che se è una proprietà che vale per , e seper , allora vale con .per , allora vale con .


Domini infiniti

La definizione induttiva (o ricorsiva ) di un dominio ci permette di definire in modo finito un insieme infinitoinsieme infinito

Ad esempio, l’insieme dei numeri naturali


Funzioni definite induttivamente

Analogamente ai domini, è possibile utilizzare definizioni ricorsive di funzioni matematiche.definizioni ricorsive di funzioni matematiche.

Esempio: la funzione di Ackermann -Péter


Ricorsione

Una funzione si dice ricorsiva se al suo interno contiene un’attivazione di se stessa (eventualmente indirettamente, attraverso (eventualmente indirettamente, attraverso l’attivazione di altre funzioni).

Esempio: Fattoriale


Ricorsione: caratteristiche

La definizione ricorsiva di una funzione ha le seguenti caratteristiche:

• uno (o più) casi base , per i quali il risultato può essere determinato direttamente;

• uno (o più) casi ricorsivi , per i quali si riconduce il calcolo del risultato al calcolodella stessa funzione su un valore più

Pagina 172011/2012

della stessa funzione su un valore più piccolo/semplice.

RicorsioneUnità 5

Funzione fattoriale ricorsiva

int fattoriale(int n) {if(n == 0)

return 1;return 1;else

return n * fattoriale(n - 1);}


Esempio: implementazione ricorsiva della somma di due interi

Definizione ricorsiva di somma tra due interi non negativi:negativi:


Implementazione

int somma(int x, int y) {if (y == 0)if (y == 0)

return x;else

return 1 + somma(x, y - 1);}


Esempio: implementazione ricorsiva del prodotto tra due interiDefinizione ricorsiva del prodotto tra due interi no n negativi:

int prodotto(int x, int y) {if (y == 0)

return 0;

Pagina 212011/2012

return 0;else

return somma(x, prodotto(x, y-1));}

RicorsioneUnità 5

Esempio: implementazione ricorsiva dell’elevamento a potenzaDefinizione ricorsiva a dell’elevamento a potenza tra due interi non negativi:

int potenza(int b, int e) {if (e == 0)

return 1;

Pagina 222011/2012

return 1;else

return (prodotto(b, potenza(b, e-1)));}

RicorsioneUnità 5

Confronto tra ricorsione e iterazione

Le funzioni implementate in modo ricorsivo ammettono anche un’implementazione iterativa.

EsempioEsempio

int fattorialeIterativa(int n) {int ris = 1;while (n > 0) {

ris = ris * n;

Pagina 232011/2012

ris = ris * n;n--;

}return ris;

}RicorsioneUnità 5

Caratteristiche dell’implementazione iterativa• inizializzazione

Es. ris = 1;

• operazione del ciclo, eseguita un numero di volte p ari al numero di ripetizioni del ciclo

Es. ris = ris * n;

• terminazione

Pagina 242011/2012

Es. n--; consente di rendere la condizione (n > 0)del ciclo while falsa

RicorsioneUnità 5

Funzione fattoriale ricorsiva

int fattoriale(int n) {if(n == 0)

return 1;return 1;else

return n * fattoriale(n - 1);}


Caratteristiche dell’implementazione ricorsiva• passo base

Es. return 1;

• passo ricorsivo

Es. return n * fattoriale(n - 1);

• terminazione

Es. la chiamata ricorsiva fattoriale(n-1) diminuisce di uno il valore passato come parametro,

Pagina 262011/2012

diminuisce di uno il valore passato come parametro, per cui, se inizialmente n > 0 , prima o poi si arriverà ad un’attivazione in cui la condizione n==0 sarà vera e quindi verrà eseguito solo il passo base.

RicorsioneUnità 5

Confronto tra ciclo di lettura e lettura ricorsivaStruttura del ciclo di lettura

leggi primo elementoleggi primo elementowhile (elemento valido ) {

elabora elemento letto ;leggi elemento successivo ;

}


Confronto tra ciclo di lettura e lettura ricorsivaStruttura della lettura ricorsiva

leggi un elementoleggi un elementoif (elemento valido ) {

elabora elemento letto;chiama ricorsivamente lettura;

}


Copia ricorsiva

#include <stdio.h>

void copiaRicorsiva() {int c;int c;c = getchar();if(c != EOF) {

putchar(c);copiaRicorsiva();

}}

Si confronti con il ciclo while per la lettura (Unità 4)

Pagina 292011/2012

}

int main () {copiaRicorsiva();return 0;

}RicorsioneUnità 5

Esempio: gli ultimi saranno i primi

Vogliamo leggere i caratteri di input e copiarli su llo schermo, invertendo l’ordine.

Facendo uso della ricorsione, questa operazione risu lta Facendo uso della ricorsione, questa operazione risu lta particolarmente semplice.

void copiaInversa() {int c;c = getchar();if(c != EOF) {

Pagina 302011/2012

if(c != EOF) {copiaInversa();putchar(c);

}}

RicorsioneUnità 5

Esecuzione


Alcune considerazioni

La funzione copiaInversa non si può facilmente formulare in modo iterativo, in quanto la stampa in ordine inverso richiederebbe la memorizzazione delle ordine inverso richiederebbe la memorizzazione delle linee lette in una struttura dati apposita.

Si noti la differenza tra questo tipo di ricorsione ed i casi più semplici visti in precedenza, in cui passa re ad un’implementazione iterativa risulta immediato, come nel caso della funzione copiaRicorsiva .

Pagina 322011/2012

Quando l’ultima istruzione effettuata prima che la funzione termini è la chiamata ricorsiva si parla di tail recursion .

RicorsioneUnità 5

Conteggio di elementi usando laricorsione

Struttura della funzione ricorsiva

leggi un elemento ;if (!elemento valido )

return 0;else

return 1 + risultato-della-chiamata-ricorsiva ;


Esempio: lunghezza di una sequenza di caratteriCaratterizzazione ricorsiva dell’operazione di contare i caratteri in input dalla tastiera:

• se l’utente digita Ctrl+Z, restituisci 0;

• altrimenti, leggi il primo carattere in input e re stituisci 1 più il numero di caratteri presenti nel resto del flusso in input.


Implementazione

int contaCaratteri() {int c;c = getchar();c = getchar();if(c == EOF)

return 0;else

return 1 + contaCaratteri();}

Pagina 352011/2012

}

Come bisogna modificare il codice per non contare i caratteri '\n'?

RicorsioneUnità 5

Conteggio condizionato di elementi usando la ricorsione


leggi un elemento ;if (!elemento valido )

return 0;else if (condizione )

return 1 + risultato-della-chiamata-ricorsiva ;else

Pagina 362011/2012

elsereturn risultato-della-chiamata-ricorsiva ;

RicorsioneUnità 5

Esempio

int contaCaratteriTranneAccapo() {int c;c = getchar();c = getchar();if(c == EOF)

return 0;else if(c != ' \n')

return 1 + contaCaratteri();else

Pagina 372011/2012

elsereturn contaCaratteri();

}

RicorsioneUnità 5

Calcolo di valori usando la ricorsione


leggi un elemento ;leggi un elemento ;if (!elemento valido )

return elemento-neutro-di-op ;else

return valore-elemento op risultato-della-chiamata-ricorsiva ;

dove elemento-neutro-di-op è l’elemento neutro rispetto

Pagina 382011/2012

dove elemento-neutro-di-op è l’elemento neutro rispetto all’operazione da effettuare (ad esempio, 0 per la s omma, 1 per il prodotto, ecc.).

RicorsioneUnità 5

Esempio: somma di interi in un flussodi input

� leggi un elemento i ;

� se il flusso è terminato, restituisci 0;

� altrimenti, restituisci la somma tra il valoreletto e la somma dei valori del resto del flusso.


Implementazione

int sommaValori() {int i, v;i = scanf("%d", &v);i = scanf("%d", &v);if (i == EOF)

return 0;else

return v + sommaValori();}

Pagina 402011/2012

}

RicorsioneUnità 5

Esempio: presenza di un valore in uninsiemeCaratterizzazione ricorsiva dell’operazione di trovare un valore in un insieme di valori letti da tastiera:

� leggi un elemento i ;

� se il flusso è terminato, restituisci false;

� altrimenti, se i è il valore cercato, restituisci true;

Pagina 412011/2012

� altrimenti, continua la ricerca nel resto del fluss o.

RicorsioneUnità 5

Implementazione

int trovaValore(int x) {int i, v;i = scanf("%d", &v);i = scanf("%d", &v);if (i == EOF)

return 0;else

return (v == x) || trovaValore(x);}


Oppure

int trovaValore2(int x) {int i, v;i = scanf("%d", &v);i = scanf("%d", &v);if (i == EOF)

return 0;else if (v == x)

return 1;else

return trovaValore2(x);

Pagina 432011/2012

return trovaValore2(x);}

RicorsioneUnità 5

Esempio: massimo di interi positivi letti da tastieraCaratterizzazione ricorsiva dell’operazione di trovare il massimo tra i valori di un insieme di interi positi vi :

• leggi un elemento i ;

• se il flusso è terminato, restituisci 0;

• altrimenti,1. trova il massimo mtra i valori rimanenti nel

Pagina 442011/2012

1. trova il massimo mtra i valori rimanenti nel flusso;

2. restituisci il maggiore tra i ed m.

RicorsioneUnità 5

Implementazione

int massimo() {int i, v;i = scanf("%d", &v);i = scanf("%d", &v);if (i == EOF)

return 0;else {

int m = massimo();if (m > v)

return m;

Pagina 452011/2012

return m;else

return v;}

}RicorsioneUnità 5

Inserimento di stampeint massimo() {

int i, v;i = scanf("%d", &v);printf("ho letto %d il valore di "

"ritorno di scanf e \ ' %d \ n", v, i); "ritorno di scanf e \ ' %d \ n", v, i); if (i == EOF) {

printf("valore di ritorno 0\n");return 0;

}else {

int m = massimo();if (m > v) {

printf("valore di ritorno m = %d\n", m);return m;


return m;}else {

printf("valore di ritorno v = %d\n", v);return v;

}}

}

Implementazione funzione main

int main() {int max = massimo();int max = massimo();printf("il massimo e \' %d \n", max);return 0;

}


Esempio di esecuzione12 5 45ho letto 12 il valore di ritorno di scanf e' 1ho letto 5 il valore di ritorno di scanf e' 1ho letto 45 il valore di ritorno di scanf e' 1ho letto 45 il valore di ritorno di scanf e' 123 7ho letto 23 il valore di ritorno di scanf e' 1ho letto 7 il valore di ritorno di scanf e' 1^Zho letto 1981638873 il valore di ritorno di scanf e ' -1valore di ritorno 0valore di ritorno v = 7valore di ritorno v = 23


valore di ritorno v = 23valore di ritorno v = 45valore di ritorno m = 45valore di ritorno m = 45il massimo e' 45

Esercizio

Esercizio 5.3

Implementare una funzioni ricorsiva sfruttando la seguente definizione ricorsiva:seguente definizione ricorsiva:

resto della divisione tra un intero ed un intero po sitivo

resto(x + y, y) , se x < 0 (caso ricorsivo)resto(x, y) = x, se 0 ≤ x < y (caso base)

resto(x − y, y), se x > y (caso ricorsivo)

Pagina 492011/2012

resto(x − y, y), se x > y (caso ricorsivo)

RicorsioneUnità 5

Esercizio

Esercizio 5.4

Fornire l’implementazione di una funzione ricorsiva c he conta quanti 1 compaiono in una sequenza di interi letti conta quanti 1 compaiono in una sequenza di interi letti da tastiera.


Ricorsione - Dipartimento di Ingegneria informatica...

Documents

Transcript of Ricorsione - Dipartimento di Ingegneria informatica...