INFORMATICA - lia.deis.unibo.it

INFORMATICA - lia.deis.unibo.it

IL MODELLO CLIENTE / SERVITORE Cliente controllo & Servitore informazione ambiente condiviso Servitore Cliente CLIENTI E SERVITORI Servitore: un qualunque ente computazionale capace di

nascondere la propria organizzazione interna presentando ai clienti una precisa interfaccia per lo scambio di informazioni. Cliente: qualunque ente in grado di invocare uno o pi servitori per svolgere il proprio compito. SERVITORI Un servitore pu essere passivo o attivo servire molti clienti oppure costituire la risorsa privata di uno specifico cliente in particolare: pu servire un cliente alla volta,

in sequenza, oppure pi clienti per volta, in parallelo trasformarsi a sua volta in cliente, invocando altri servitori o anche se stesso. COMUNICAZIONE CLIENTE / SERVITORE Lo scambio di informazioni tra un cliente e un servitore pu avvenire in modo esplicito tramite le interfacce stabilite dal servitore in modo implicito tramite aree-dati accessibili ad entrambi.

FUNZIONI Una funzione permette di dare un nome a una espressione rendendola parametrica Esempi (pseudo-C): float f(){ 2 + 3 * sin(0.75); } float f1(int x) { 2 + x * sin(0.75); } FUNZIONI come COMPONENTI SW Una funzione un componente software che cattura lidea matematica di funzione

f : A B ... Q S molti possibili ingressi (che non vengono modificati!) una sola uscita (il risultato) FUNZIONI come SERVITORI Una funzione riceve dati di ingresso in corrispondenza ai parametri ha come corpo una espressione, la cui valutazione fornisce un risultato denota un valore in corrispondenza al suo nome

FUNZIONI come SERVITORI Esempio se x vale 1 e f la funzione R R f = 3 * x2 + x - 3 allora f(x) denota il valore 1. FUNZIONI come SERVITORI Una funzione un servitore passivo che serve un cliente per volta che pu trasformarsi in cliente invocando se stessa

FUNZIONI come SERVITORI Una funzione un servitore dotato di nome che incapsula le istruzioni che realizzano un certo servizio. Per chiedere al servitore di svolgere il servizio occorre chiamare tale servitore (per nome) fornirgli le necessarie informazioni Come far comunicare cliente e servitore? COMUNICAZIONE CLIENTE/SERVITORE

Nel caso di una funzione, cliente e servitore comunicano mediante linterfaccia della funzione. FUNZIONI: INTERFACCIA Linterfaccia di una funzione comprende nome della funzione lista dei parametri tipo del valore da essa denotato spesso chiamata firma (signature)

esplicita il contratto di servizio fra cliente e servitore. COMUNICAZIONE CLIENTE/SERVITORE Cliente e servitore comunicano quindi mediante i parametri trasmessi dal cliente al servitore allatto della chiamata (direzione: dal cliente al servitore) il valore restituito dal servitore al cliente (direzione: dal servitore al cliente)

UN ESEMPIO int max (int x, int y ){ return x>y ? x : y; } Il simbolo max denota il nome della nuova funzione Le variabili intere x e y sono i parametri della nuova funzione Il valore restituito un intero. FUNZIONI & INFORMATION HIDING La struttura interna (corpo) di una funzione completamente

inaccessibile dallesterno. Cos facendo si garantisce protezione dellinformazione secondo il principio del suo nascondimento (information hiding) FUNZIONI IN UN PROGRAMMA C Un programma C un insieme di funzioni: ::= { } ::= | |

Il main semplicemente la funzione, di nome prefissato, dove inizia lelaborazione. DEFINIZIONE DI FUNZIONE: struttura Una definita dalla produzione: ::= (){ } DEFINIZIONE DI FUNZIONE: parametri Una definita dalla produzione: ::=

(< parametri >){ } o una lista vuota: void o una lista di variabili (separate da virgole) visibili solo entro il corpo della funzione. DEFINIZIONE DI FUNZIONE: corpo Una definita dalla produzione: ::= (< parametri >){

} tutto ci che sta fra {} La forma base return ; DEFINIZIONE DI FUNZIONE: tipo Una definita dalla produzione: ::= (< parametri >){ }

il tipo della funzione deve coincidere col tipo dellespressione che costituisce il corpo della funzione FUNZIONI COME COMPONENTI SOFTWARE: NASCITA E MORTE Allatto della chiamata, lesecuzione del cliente viene sospesa e il controllo passa al servitore. Il servitore vive solo per il tempo necessario a svolgere il servizio. Al termine, il servitore muore, e lesecuzione torna al cliente.

CHIAMATA DI FUNZIONE La chiamata di funzione unespressione della forma ( ) dove: ::= [ ] { , } CHIAMATE DI FUNZIONE & ESPRESSIONI Linvocazione di una funzione da parte di un cliente costituisce un particolare tipo di espressione.

::= | + | - ::= | * | / | % ::= [- | + ] |( )| | RITORNO DA FUNZIONE Listruzione return provoca la restituzione del controllo al cliente, unitamente al valore dellespressione che la segue. Eventuali istruzioni successive alla return non saranno mai eseguite! IL PROBLEMA DEI SIMBOLI

f(x) + g( f(x), q( x + f(y))) Per fornire il risultato, dobbiamo conoscere: la definizione delle funzioni f, g, q i valori di x e y Come conoscerli? SIMBOLI & SIGNIFICATO Come conoscere il significato di un simbolo? o esiste una convenzione diffusa, una cultura comune, che associa ad un simbolo un preciso significato; o esiste un ente di riferimento che specifica in modo esplicito il significato di un simbolo.

BINDING & ENVIRONMENT La conoscenza di cosa un simbolo denota viene espressa da una legame (binding) tra il simbolo e uno o pi attributi. La collezione dei binding valida in (un certo punto di) un programma si chiama environment. UN ESEMPIO Sia f N->N: Sia z = 2 f(z) + f(z) f(2) + f(y)

g(z) f(x)=x+x vale 8 vale ??? vale ??? SCOPE & SCOPE RULES Tutte le occorrenze di un nome nel testo di un programma a cui si applica un dato binding si dicono essere entro la stessa portata o scope del binding. Le regole in base a cui si stabilisce la

portata di un binding si dicono regole di visibilit o scope rules. ESEMPIO Sia f N->N: f(x)=x+x Sia z = 2 f(z) + f(z) vale 8 f(2) + f(y) vale ??? Sia g N->N: g(x)=x*x g(z) vale 4 f(g(z)) vale 8

DEFINIZIONE DI NUOVE FUNZIONI Per dare un nome alla nuova funzione, il linguaggio deve introdurre costrutti per estendere un environment aggiungendo ad esso il nuovo binding che lega il nome scelto per la funzione allentit che realizza quella specifica funzione. DEFINIZIONE DI NUOVE FUNZIONI La definizione di funzione unisce la denotazione di una nuova funzione lattribuzione di un nome ad essa

Lenvironment corrente viene arricchito con uno nuovo binding tra il nome della funzione, e la sua rappresentazione interna FUNZIONI: IL MODELLO APPLICATIVO 1) Valutazione, nellenvironment corrente, del simbolo che denota il nome della funzione; 2) Valutazione, nellenvironment corrente, delle espressioni che denotano i parametri; 3) Commutazione allenvironment di

definizione della funzione. FUNZIONI: IL MODELLO APPLICATIVO 4) Chiamata della funzione; 5) Esecuzione del corpo della funzione (nel suo environment di definizione); 6) Restituzione al chiamante di controllo risultato con ripristino dellenvironment esistente al momento della chiamata. LENVIRONMENT

La definizione di una funzione introduce un nuovo binding nellenvironment di definizione della funzione in C, il global environment Al momento dellinvocazione, si crea un nuovo environment una struttura che contiene i binding dei parametri e degli identificatori dichiarati localmente alla funzione. ESEMPIO int max (int x, int y ){ return x>y ? x : y;

} Lenvironment corrente viene arricchito di un nuovo binding: max / CodiceDellaFunzione Quando max viene chiamata, si commuta a un nuovo environment, in cui sono definite le variabili intere x e y COMUNICAZIONE CLIENTE SERVITORE Il cliente passa informazioni al servitore mediante una serie di parametri attuali. Parametri formali : sono specificati nella dichiarazione del servitore

esplicitano il contratto fra servitore e cliente indicano cosa il servitore si aspetta dal cliente Parametri attuali : sono trasmessi dal cliente allatto della chiamata devono corrispondere ai parametri formali in numero, posizione e tipo COMUNICAZIONE CLIENTE SERVITORE Il cliente passa informazioni al servitore mediante una serie di parametri attuali. I Parametri attuali sono legati ai parametri formali al momento della chiamata,

in modo dinamico. Tale legame: vale solo per linvocazione corrente vale solo per la durata della funzione. IL NOSTRO ESEMPIO Il servitore... int max (int x, int y ){ return x>y ? x : y; } e un possibile cliente: main(){ int z = 8; int m = max(2*z,13);

} IL NOSTRO ESEMPIO Il servitore... int max (int x, int y ){ del simbolo z 1) Valutazione return x>y ? nellenvironment x : y; corrente } Si trova che z vale 8. e un possibile cliente: main(){

int z = 8; int m = max(2*z,13); } IL NOSTRO ESEMPIO Il servitore... int max (int2)x, int ydellespressione ){ Calcolo 2*z return x>y ? nellenvironment x : y; corrente

} Si trova che vale 16. e un possibile cliente: main(){ int z = 8; int m = max(2*z,13); } IL NOSTRO ESEMPIO Il servitore... Invocazione int max (int3)x, int y ){della funzione return x>y ?max

x :con y;parametri attuali 16 e 13. } e un possibile cliente: passa al servitore. Il controllo main(){ int z = 8; int m = max(2*z,13); } IL NOSTRO ESEMPIO Il servitore...

int max (int x, int y ){ return x>y ? x : y; } e un possibile cliente: formali x e y 4) I parametri main(){ vengono legati ai parametri int z = 8;attuali 16 e 13. int m = Inizia max(2*z,13); lesecuzione del servitore. }

IL NOSTRO ESEMPIO Il servitore... int max (int x, int y ){ return x>y ? x : y; } e un possibile cliente: 5) Viene valutata lespressione main(){ int z = 8;condizionale nellenvironment del servitore. Il risultato 16. int m = max(2*z,13); } IL NOSTRO ESEMPIO

Il servitore... int max (int x, int y ){ return x>y ? x : y; } e un possibile cliente: 6) Il valore cos determinato (16) main(){ viene restituito al cliente. int z = Il8; servitore termina e il controllo int m = max(2*z,13); torna al cliente.

} IL NOSTRO ESEMPIO Il servitore...7) Il valore restituito (16) viene per inizializzare la int max (intusato x, int y ){ variabile (nellenvironment return x>y ? x :my; del cliente)

} e un possibile cliente: main(){ int z = 8; int m = max(2*z,13); } RIASSUNTO Allatto dellinvocazione di una funzione: si crea una nuova attivazione (istanza) del servitore si alloca la memoria per i parametri (e le eventuali variabili locali) si trasferiscono i parametri al servitore

si trasferisce il controllo al servitore si esegue il codice della funzione. PASSAGGIO DEI PARAMETRI In generale, un parametro pu essere trasferito: per valore o copia (by value) si trasferisce il valore del parametro attuale per riferimento (by reference) si trasferisce un riferimento al parametro attuale PASSAGGIO PER VALORE

si trasferisce una copia del valore del parametro attuale z 45 cliente PASSAGGIO PER VALORE si trasferisce una copia del valore del parametro attuale z 45

copia 45 w istanza del servitore cliente servitore

valore (copiato) di z PASSAGGIO PER VALORE Ogni azione fatta su w si trasferisce una copialocale del valore del strettamente parametro attuale al servitore z

45 copia 45 w istanza del servitore cliente

servitore valore (copiato) di z PASSAGGIO PER RIFERIMENTO si trasferisce un riferimento al parametro attuale z 45 cliente

PASSAGGIO PER RIFERIMENTO si trasferisce un riferimento al parametro attuale z 45 riferimento

w istanza del servitore cliente servitore riferimento az (indirizzo) PASSAGGIO PER RIFERIMENTO

Ogni azione fatta su w si trasferisce riferimento in un realt fatta sulla al parametro attuale variabile z del cliente! z 45

riferimento w istanza del servitore cliente servitore riferimento

az (indirizzo) PASSAGGIO DEI PARAMETRI IN C In C, i parametri sono trasferiti sempre e solo per valore (by value) si trasferisce una copia del parametro attuale, non loriginale! tale copia strettamente privata e locale a quel servitore il servitore potrebbe quindi alterare il valore ricevuto, senza che ci abbia alcun impatto sul cliente

PASSAGGIO DEI PARAMETRI IN C In C, i parametri sono trasferiti sempre e solo per valore (by value) Conseguenza: impossibile usare un parametro per trasferire informazioni verso il cliente per trasferire (una) informazione al cliente si sfrutta il valore di ritorno della funzione ESEMPIO: VALORE ASSOLUTO Definizione formale: |x|: N N |x| vale x se x 0

|x| vale -x se x 0 Codifica sotto forma di funzione C: int valAss(int x) { return (x<0) ? -x : x; } ESEMPIO: VALORE ASSOLUTO Servitore & Cliente: int valAss(int x) { return (x<0) ? -x : x; } main(){ int z = -87; int absz = valAss(z);

int abs4 = valAss(4); } ESEMPIO: VALORE ASSOLUTO valAss(z) viene chiamata, ServitoreQuando & Cliente: il valore attuale int valAss(int x) { di z, valutato nel(-87), viene return lenvironment (x<0) ? -x :corrente x; copiato e passato a valAss.

} main(){ int z = -87; int absz = valAss(z); int abs4 = valAss(4); } ESEMPIO: VALORE ASSOLUTO Servitore & Cliente: int valAss(int x) { return (x<0) ? -x : x; } main(){ int z =valAss

-87; riceve quindi una copia del valore -87 e la lega al simbolo x. int absz = valAss(z); Poi=sivalAss(4); valuta lespressione, che qui int abs4 vale 87, e si restituisce questo valore. } ESEMPIO: VALORE ASSOLUTO Servitore & Cliente: int valAss(int x) {

Il valore restituito (87) viene usato return (x<0) ? -x : x; per inizializzare la variabile absz. } main(){ int z = -87; int absz = valAss(z); int abs4 = valAss(4); } ESEMPIO: MASSIMO DI DUE NUMERI Definizione formale: max: N N N max(x,y) vale x

max(x,y) vale y se x y se x < y Codifica sotto forma di funzione C: int max(int x, int y) { return (x

} main(){ int z = -87, y = 12; int m = max(z,18); int n = max(4*y,z+100); } ESEMPIO: MASSIMO DI DUE NUMERI Si & valutano Servitore Cliente:le due espressioni che costituiscono attuali (nelint max(int

x, inti parametri y) { returnlenvironment (x

Servitore & Cliente: int max(int x, int y) { return (x

restituito al main chiamante. } PASSAGGIO DEI PARAMETRI IN C Perch il C adotta sempre e solo il passaggio per valore (by value)? sicuro: le variabili del chiamante e del chiamato sono completamente disaccoppiate consente di ragionare per componenti e servizi: la struttura interna dei singoli componenti irrilevante PASSAGGIO DEI PARAMETRI IN C

Limiti: consente di restituire al cliente solo valori di tipo (relativamente) semplice non consente di restituire collezioni di valori non consente di scrivere componenti software il cui scopo sia diverso dal calcolo di una espressione PASSAGGIO DEI PARAMETRI Molti linguaggi mettono a disposizione il passaggio per riferimento (by reference) non si trasferisce una copia del valore del

parametro attuale si trasferisce un riferimento al parametro, in modo da dare al servitore accesso di- retto al parametro in possesso del cliente il servitore accede e modifica direttamente il dato del cliente. PASSAGGIO DEI PARAMETRI IN C Il C non supporta direttamente il passaggio per riferimento una grave mancanza! il C lo fornisce indirettamente solo per alcuni tipi di dati

ergo, occorre costruirselo quando serve. (vedremo dei casi) Il C++ e Java invece lo forniscono. DEFINIZIONE DI NUOVE FUNZIONI & STRATEGIE DI COMPOSIZIONE La capacit di definire nuove funzioni permette: di definire nuove operazioni di introdurre variabili per denotare i dati in modo simbolico di esprimere la ripetizione di una espressione per un numero (prefissato o meno) di volte.

STRATEGIE DI COMPOSIZIONE Tre grandi approcci: 1) la composizione di funzioni; 2) le espressioni condizionali; 3) la ricorsione. Le funzioni definibili in termini di un insieme prescelto di primitive e delle precedenti strategie di composizione costituiscono un insieme detto delle funzioni ricorsive generali. 1) COMPOSIZIONE DI FUNZIONI I parametri in una chiamata di funzione possono consistere/comprendere altre funzioni Es: f(x) + g(f(x), q(x + f(y)))

x1 = f(x) x2 = f(x) (mossa evitabile da un automa intelligente) x3 = f(y) x4 = x + x3 x5 = q( x4 ) x6 = g( x2,x5 ) x7 = x1 + x6 2) ESPRESSIONE CONDIZIONALE Lespressione condizionale riflette la consuetudine matematica di definire le funzioni per elencazione di casi. Esempio: abs: N -> N

abs(x) vale x abs(x) vale -x se x 0 se x 0 3) LA RICORSIONE La ricorsione consiste nella pos-sibilit di definire una funzione in termini di se stessa. basata sul principio di induzione matematica: se una propriet P vale per n=n0 e si pu provare che, assumendola valida

per n, allora vale per n+1 allora P vale per ogni nn0 LA RICORSIONE Operativamente, risolvere un problema con un approccio ricorsivo comporta di identificare un caso base la cui soluzione sia ovvia di riuscire a esprimere la soluzione al caso generico n in termini dello stesso problema in uno o pi casi pi semplici (n-1, n-2, etc).

LA RICORSIONE: ESEMPIO Esempio !: N N n! vale 1 se n 0 n! vale n*(n-1)! se n > 0 Codifica: int fact(int n) { return n==0 ? 1 : n*fact(n-1); } LA RICORSIONE: ESEMPIO

Esempio Attenzione: la codifica !: N non N corrisponde alla specifica!! n0, n! valeIl 21 caso si applica se per n 0 cio anche per n<0 !! n! vale n*(n-1)! se

n > 0 MA COS PU NON TERMINARE! Codifica: int fact(int n) { return n==0 ? 1 : n*fact(n-1); } LA RICORSIONE: ESEMPIO Esempio !: N N

n! vale 1 se n 0 n! vale n*(n-1)! se n > 0 Codifica: Nuova codifica int fact(int n) { /* return n==0 ? 1 : n*fact(n-1); */ return n>0 ? n*fact(n-1) : 1; }

ESEMPIO: FATTORIALE Servitore & Cliente: int fatt(int n) { return (n>0) ? n*fatt(n-1) : 1; } main(){ int z = 5; int fz = fatt(z+2); int f6 = fatt(6); } ESEMPIO: FATTORIALE Si valuta lespressione che costituisce il

Servitore & Cliente: parametro attuale (nellenvironment del int fatt(int n) { main) e si trasmette alla funzione fatt return (n>0) ? n*fatt(n-1) : 1; una copia del valore cos ottenuto (7). } main(){ int z = 5; int fz = fatt(z+2); int f6 = fatt(6); }

ESEMPIO: FATTORIALE Servitore & Cliente: int fatt(int n) { return (n>0) ? n*fatt(n-1) : 1; } main(){ La z funzione int = 5; riceve una copia del valore 7 e lafz lega simbolo n. Poi valuta lespresint = al

fatt(z+2); sione int f6 condizionale: = fatt(6); ci impone di valutare } una espressione che contiene una nuova chiamata di funzione. ESEMPIO: FATTORIALE Servitore & Cliente: int fatt(int n) { return (n>0) ? n*fatt(n-1) : 1; } main(){

int z = 5; Si valuta quindi, nellenvironment di fatt, int fz = fatt(z+2); lespressione n-1 (che vale 6), e si effettua int = fatt(6); unaf6 nuova chiamata al servitore fatt, pas} sandogli una copia del valore 6.

ESEMPIO: FATTORIALE Servitore & Cliente: int fatt(int n) { return (n>0) ? n*fatt(n-1) : 1; } main(){ int z = 5;servitore riceve quindi una copia Il (nuovo) int = fatt(z+2); delfz valore 6 e, come sopra, valuta lespresint

f6 condizionale. = fatt(6); Ci lo porta a dover sione } fare una nuova chiamata passando 5. ESEMPIO: FATTORIALE Servitore & Cliente: int fatt(int n) { return (n>0) ? n*fatt(n-1) : 1; } main(){ int z = 5; int fz = fatt(z+2);

int f6 = fatt(6); la cosa prosegue, servitore dopo servitore.. } ... ESEMPIO: FATTORIALE Servitore & Cliente: int fatt(int n) { return (n>0) ? n*fatt(n-1) : 1; } main(){ int z =o 5; Prima

poi, dato che il valore passato cala int fzvolta, = fatt(z+2); ogni si giunge a invocare fatt con int f6 = fatt(6); parametro 1. In questo caso, la valutazione } dellespressione d come risultato 1. ESEMPIO: FATTORIALE Servitore & Cliente:

int fatt(int n) { return (n>0) ? n*fatt(n-1) : 1; } main(){ Cizchiude int = 5; la sequenza di chiamate ricorsive. Il controllo torna al servitore int fz = fatt(z+2); precedente, che pu finalmente valutare int

f6 = fatt(6); } lespressione n*1 (valutando n nel suo environment, dove vale 2) ottenendo 2. ESEMPIO: FATTORIALE Servitore & Cliente: int fatt(int n) { return (n>0) ? n*fatt(n-1) : 1; } main(){ int z = 5; Il valore 2 viene restituito al servitore preint

fz = fatt(z+2); cedente, che a sua volta pu cos valutare int f6 = fatt(6); lespressione n*2 (valutando n nel suo } environment, dove vale 3) ottenendo 6. ESEMPIO: FATTORIALE Servitore & Cliente: int fatt(int n) { return (n>0) ? n*fatt(n-1) : 1; }

main(){ int z = 5; int fz = fatt(z+2); int f6 = fatt(6); la cosa prosegue } ... ESEMPIO: FATTORIALE Servitore & Cliente: int fatt(int n) { return (n>0) ? n*fatt(n-1) : 1; }

main(){ Prima poi, a forza di retrocedere, si torna int z =o 5; al primo attivato, che pu quindi int fz = servitore fatt(z+2); valutare n*720 (valutando n int f6 = lespressione

fatt(6); } nel suo environment, dove vale 7), giungendo cos a trovare il valore 5040. ESEMPIO: FATTORIALE Servitore & Cliente: Il valore 5040, int fatt(int n) { restituito dal servitore pu quindi essere usato per returnfatt, (n>0) ? n*fatt(n-1)

: 1; inizializzare la variabile fz. } main(){ int z = 5; int fz = fatt(z+2); int f6 = fatt(6); } UN ALTRO ESEMPIO Problema: calcolare la somma dei primi N interi Specifica: Considera la somma (1+2+3+...+(N-1)+N come

composta di due termini: (1+2+3+...+(N-1)) N Esiste un caso banale assolutamente ovvio: la somma fino a 1 vale 1. UN ALTRO ESEMPIO Il primo termine non altro che la Problema: soluzione allo stesso problema in calcolare la somma dei primi

N interi un caso pi semplice Specifica: Considera la somma (1+2+3+...+(N-1)+N come composta di due termini: (1+2+3+...+(N-1)) N Esiste un caso banale assolutamente ovvio: Il secondo termine la somma fino a 1 un

valevalore 1. gi noto. UN ALTRO ESEMPIO Problema: calcolare la somma dei primi N interi Codifica: int sommaFinoA(int n){ return (n==1) ? 1 : sommaFinoA(n-1) + n; } UN TERZO ESEMPIO

Problema: calcolare lN-esimo numero di Fibonacci 0, se n=0 fib (n) = 1, se n=1 fib(n-1) + fib(n-2), altrimenti UN TERZO ESEMPIO Problema: calcolare lN-esimo numero di Fibonacci

Codifica: unsigned fibonacci(unsigned n) { return (n<2) : n ? fibonacci(n-1) + fibonacci(n-2); } UN TERZO ESEMPIO Ricorsione non lineare: ogni invocazione servitore causa calcolare lN-esimo numerodel di Fibonacci

due nuove chiamate al servitore medesimo. Codifica: Problema: unsigned fibonacci(unsigned n) { return (n<2) : n ? fibonacci(n-1) + fibonacci(n-2); } UNA RIFLESSIONE Negli esempi di ricorsione visti finora fattoriale

somma dei primi N interi calcolo dellN-esimo numero di Fibonacci si inizia a sintetizzare il risultato solo dopo che si sono aperte tutte le chiamate, a ritroso, mentre le chiamate si chiudono. UNA RIFLESSIONE Le chiamate ricorsive decompongono via via il problema, ma non calcolano nulla Il risultato viene sintetizzato a partire dalla fine, perch prima occorre arrivare al caso banale: il caso banale fornisce il valore di partenza

poi, e solo poi, si sintetizzano, a ritroso, i successivi risultati parziali. UNA RIFLESSIONE Ci indica che tali soluzioni sono sintatticamente ricorsive e danno luogo a un processo computazionale effettivamente ricorsivo. UN ESEMPIO DIVERSO Problema: trovare il Massimo Comun Divisore tra N e M m, MCD(m, n) =

se m=n MCD(m-n, n), se m>n MCD(m, n-m), se m

(m>n) ? mcd(m-n, n) : mcd(m, n-m); } UN ESEMPIO DIVERSO Servitore & Cliente: int mcd(int m, int n){ return (m==n) : m ? (m>n) ? mcd(m-n, n) : mcd(m, n-m); } main(){ int m = mcd(36,15); }

UN ESEMPIO DIVERSO Servitore & Cliente: int mcd(int m, int n){ return (m==n) : m ? Si valutano i parametri (m>n) ? mcd(m-n, n) :attuali e si invoca la funzione con parametri 36 e 15 mcd(m, n-m);

} main(){ int m = mcd(36,15); } UN ESEMPIO DIVERSO Servitore & Cliente: int mcd(int m, int n){ return (m==n) : m ? (m>n) ? mcd(m-n, n) : mcd(m, n-m); Si legano i parametri 36 e 15 ai parametri } formali m e n, e si valuta lespressione

main(){ condizionale. int m = mcd(36,15); } UN ESEMPIO DIVERSO Servitore & Cliente: int mcd(int m, int n){ return (m==n) : m ? (m>n) ? mcd(m-n, n) : mcd(m, n-m); } main(){ Poich 36 15, si invoca nuovamente la con parametri m-n (21) e n (15). int m =funzione

mcd(36,15); } UN ESEMPIO DIVERSO Servitore & Cliente: int mcd(int m, int n){ return (m==n) : m ? (m>n) ? mcd(m-n, n) : mcd(m, n-m); } Il nuovo servitore, poich 21 15, fa la main(){ stessa cosa e invoca nuovamente la int m =funzione mcd(36,15);

con parametri m-n (6) e n (15). } UN ESEMPIO DIVERSO Servitore & Cliente: int mcd(int m, int n){ return (m==n) : m ? (m>n) ? mcd(m-n, n) : mcd(m, n-m); } Il nuovo servitore, poich 6 15, invoca main(){ un ulteriore servitore con parametri m (6) int m =e n-m mcd(36,15);

(9). } UN ESEMPIO DIVERSO Servitore & Cliente: int mcd(int m, int n){ return (m==n) : m ? (m>n) ? mcd(m-n, n) : mcd(m, n-m); } main(){ Poich 6 9, si ha una nuova chiamata parametri m (6) e n-m (3). int m =con mcd(36,15);

} UN ESEMPIO DIVERSO Servitore & Cliente: int mcd(int m, int n){ return (m==n) : m ? (m>n) ? mcd(m-n, n) : mcd(m, n-m); } main(){ Poich 6 3, si ha una nuova invocazione con parametri m-n (3) e n (3). int m =(lultima!) mcd(36,15); }

UN ESEMPIO DIVERSO Servitore & Cliente: int mcd(int m, int n){ return (m==n) : m ? (m>n) ? mcd(m-n, n) : mcd(m, n-m); } Poich 3 = 3, il servitore termina e main(){ restituisce come risultato 3. int m = mcd(36,15); }

UN ESEMPIO DIVERSO Perch questo esempio diverso ? il risultato viene sintetizzato via via che le chiamate si aprono, in avanti quando le chiamate si chiudono non si fa altro che riportare indietro, fino al cliente, il risultato ottenuto. UNA RIFLESSIONE La soluzione ricorsiva individuata per lMCD sintatticamente ricorsiva... ma d luogo a un processo computazionale diverso dal precedente: un processo computazionale ITERATIVO Il risultato viene sintetizzato in avanti

ogni passo decompone e calcola e porta in avanti il nuovo risultato parziale UNA RIFLESSIONE Ogni processo computazionale ITERATIVO calcola a ogni passo un risultato parziale dopo k passi, si ha a disposizione il risultato parziale relativo al caso k questo non vero nei processi computazionali ricorsivi l, finch non si sono aperte tutte le chiamate, non disponibile nessun risultato! RICORSIONE TAIL Una ricorsione che realizza un processo

computazionale ITERATIVO una ricorsione solo apparente la chiamata ricorsiva sempre lultima istruzione i calcoli sono fatti prima la chiamata serve solo, dopo averli fatti, per proseguire la computazione questa forma di ricorsione si chiama RICORSIONE TAIL (ricorsione in coda)

Recently Viewed Presentations