Strutture di Controllolacam.di.uniba.it/~nico/corsi/lingpro/materiale/LP... ·...

Strutture di ControlloStrutture di ControlloNicola FanizziDipartimento di Informatica

Università degli Studi di Bari

Linguaggi di

Programmazione [010194]29 apr, 2016

SommarioSommario

1 Espressioni

Definizione

Sintassi

Semantica

2 Comandi

Definizione

Variabili

Assegnamento

3 Controllo della sequenza

Tipologie

Comandi condizionali

Comandi iterativi

Iterazione indeterminata

Iterazione determinata

Programmazione

strutturata

4 Ricorsione

Definizione

Ricorsione in coda

Ricorsione vs. Iterazione

LdP.ITPS/[email protected]/[email protected] Strutture di ControlloStrutture di Controllo 29 apr, 201629 apr, 2016 2 / 582 / 58

http://www.di.uniba.it/~fanizzi/corsi/lp


AgendaAgenda

1 Espressioni

Definizione

Sintassi

Semantica

2 Comandi


4 Ricorsione




Espressioni – definizioneEspressioni – definizioneUn’espressione è un’entità sintattica da valutare;se la valutazione termina produce un valore,

altrimenti il valore è considerato indefinito

nozione presente in tutti i linguaggi, anche quelli dichiarativi

non sono necessariamente numeriche

booleane, alfanumeriche (su stringhe), ecc...

Esempio 4 + 3 * 2pare ovvio che la valutazione produca il valore 10;assunzione implicita: precedenza di * su +altrimenti il risultato sarebbe stato diverso




Espressioni – sintassiEspressioni – sintassiEspressione: composta da

una singola entità: costante, variabile

es.: true, 12.45E4, ipotenusa, contoCorrente, . . .operatore applicato ad una espressione

es.: not(flag), -saldoContooperatore applicato a due (o più) espressioni

es: a+3/4, (n<0) and not(ordinato)

La sintassi è regolata dalla grammatica (libera)

albero di derivazione da cui discende la valutazione

(i.e. la semantica)

le notazioni per la sintassi si differenziano a seconda di come si

rappresenta l’applicazione degli operatori




Notazione infissaNotazione infissanotazione più comune (proviene dalla matematica)

simbolo dell’operatore posto fra le espressioni che

rappresentano i suoi operandi

es. moltiplicazione per z della somma di x e y: (x+y)*zper evitare ambiguità

uso di parentesi

regole di precedenza

per alcuni linguaggi la notazione infissa è solo

un’abbreviazione (syntactic sugar) per la notazione prefissa:

in C++: x * y è abbreviazione di: x.operator*(y)in ADA: *(x,y) è valida

operatori non binari: notazione simile

es. (n >= 0) ? x : y




Notazione prefissaNotazione prefissanotazione polacca prefissa (W. Lukasiewicz):

il simbolo dell’operatore precede le espressioni che


es. somma: +(x y) oppure semplicemente + x yes. appl. funzioni f(x y) oppure semplicemente f x y

NB: non servono parentesi né regole di precedenza purché

sia nota l’arietà di ogni funzione/operatore:

si applica sempre l’operatore che precede immediatamente gli

operandi

es: * + a b + c d equivale a (a+b)*(c+d),in notazione infissa

notazione polacca di Cambridge (LISP):

anche gli operatori dentro le parentesi

es. (* (+ a b) (+ c d))




Notazione postfissaNotazione postfissa

notazione polacca inversa:il simbolo dell’operatore segue le espressioni che


es. a b + c d + *è la scrittura dell’espressione precedente




Notazione postfissa [. . . cont.]Notazione postfissa [. . . cont.]

vantaggi (delle notazioni polacche):

si possono usare per rappresentare facilmente operatori di

qualunque arietà

la notazione infissa necessita di più operatori

ad es. l’op. ternario · ? · : ·si possono evitare le parentesi

utili solo per motivi di leggibilità, non per l’ordine di

valutazione

valutazione è più semplice




SemanticaSemantica

La modalità di valutazione (aspetto semantico)varia a seconda della notazione scelta per la sintassi

Rappresentazione interna delle espressioni: albero

Notazione infissa: evitare l’ambiguitàdefinendo la precedenza,

definendo associatività,

usando parentesi




Valutazione della notazione infissaValutazione della notazione infissanaturalezza della scrittura / maggiore difficoltà di valutazione

albero: unica passata impossibile

chiarire la precedenza tra tutti gli operatori

es.: 4+3*5 deve dare 19 e non 35usare parentesi per imporre la precedenza

es. precedente: 4+(3*5) e non (4+3)*5operatori diversi:

es. x=4 and y=5 senza parentesi porta ad un errore di tipo inPASCAL perché interpretato come x=(4 and y)=5

associatività:

la maggior parte degli operatori associa da sinistra a destracome intendere l’espressione 30-7-5 ?

dovrebbe valere 18 per l’associatività di -Eccezioni: op. potenza ** associativo da destra verso sinistra

es. 532 = 5**3**2 = 5^(3^2) = 5^9 e non (5^3)^2 = 5^6




Valutazione della notazione prefissaValutazione della notazione prefissaScansione da sinistra a destra di una seq. e uso di una pila

1 Leggi prossimo simbolo e mettilo sulla pila

2 Se il simbolo è un operatoreallora inizializza C alla sua arietà e torna a 1

altrimenti (operando) decrementa C3 Se C>0 allora torna a 1

altrimenti (sulla pila presente operatore ed operandi)a. Applica l’ultimo operatore inserito sulla pila agli operandi

presenti, memorizzando il risultato in Rb. Rimuovi dalla pila operandi ed operatore, e inserisci Rc. Se sulla pila non ci sono operatori allora salta a 4

d. Poni C a n-m, conn arietà dell’operatore più in cima;m n. di operandi presenti sopra l’operatore

e. Torna a 3

4 Se ci sono ancora simboli da leggere allora torna a 1




Valutazione della notazione postfissaValutazione della notazione postfissaPiù semplice della precedente:

non serve controllare la presenza degli operandi per

l’operatore inserito dato che vengono letti prima

Scansione da sinistra a destra e uso di una pila

1 Leggi prossimo simbolo e mettilo sulla pila

2 Se il simbolo è un operatorea. Applicalo agli operandi immediatamente precedenti sulla pila

b. Memorizza il risultato in Rc. Elimina operandi ed operatore dalla pila

d. Memorizza R sulla pila3 Se ci sono simboli ancora da leggere torna a 1

4 Se il simbolo letto è un operando torna a 1




Valutazione alberi sintatticiValutazione alberi sintatticiRappresentate da alberi sintattici

Nodi interni: operatori

Nodi foglia: operandi

semplici

Sotto-alberi radicati in N:

operandi per espressioni di

livello inferiore

*

+

a f

b

+

c f

b

Notazioni discusse: corrispondono a visite diverse

Simmetrica (invisita),

anticipata (previsita) e

differita (postvisita)

Risultato dell’analisi sintattica nei ling. compilati

In alcuni linguaggi si trasforma in notazione polacca prima

della valutazione




Ordine di valutazioneOrdine di valutazione

*

+

a f

b

+

c f

b

Trascurabile in matematica

/ Importante in informatica

Effetti collaterali: azione che influenza

i risultati parziali o finali

assenti nei ling. dichiarativi;

ove presenti, conta l’ordine

es. JAVA impone l’ordine

sinistra⇒ destra

la valutazione può mutare variabili

es. f(b) può mutare bAritmetica finita

riordinando i termini delle espressioni si possono causare

Errori di overflow oppure

Errori dovuti alla precisione




Ordine di valutazione [. . . cont.]Ordine di valutazione [. . . cont.]

Valutazione degli operandi:

v. eager prima valutare gli operandi poi applicare

l’operatore ai valori ottenuti

operazioni definite anche se alcuni suoi operandi

non lo sono (ad es. i condizionali)

es. a == 0 ? b : b/av. lazy non valutare gli operandi prima dell’operatore;

al momento della sua valutazione si deciderà quali

devono essere valutati e quali no

Più costosa da implementare

Valutazione corto-circuitata

es. a == 0 || b/a > 1Val. lazy: si calcola il valore finale senza valutare tutti gli

operandi

Adottata in JAVA, C, ADA ma non in PASCAL

A volte operatori diversi (come in JAVA)




Ordine di valutazione [. . . cont.]Ordine di valutazione [. . . cont.]Ottimizzazione:

L’ordine influenza l’efficienza dell’esecuzione del codice

es.:

1 a = vettore[i];2 b = a*a+c*d;

linea 2: meglio valutare prima c*d perché il valore per apotrebbe essere ancora non disponibile (più accessi in memoria)

Messa in atto dai compilatori purché la semantica sia

preservata

Pragmatica: particolari sulla semantica

del linguaggio sono spesso:

1) nascosti,

2) poco chiari,

3) dipendenti dall’implementazione (compilatore)

⇒ usare tutti i mezzi per eliminare lefonti di ambiguità




AgendaAgenda

1 Espressioni

2 Comandi

Definizione

Variabili

Assegnamento


4 Ricorsione




ComandiComandi

Un comando è entità sintattica che,valutata, provoca un effetto collaterale,

ed eventualmente produce un valore

Caratteristica dei linguaggi imperativi

Fissato uno stato di partenza...

La valutazione di un comando

può cambiare questo stato come effetto collaterale

La valutazione di un’espressione

produce un valore ma non dovrebbe cambiare lo stato




VariabiliVariabilimatematica variabile=incognita (valore sconosciuto)

informatica dipende dal paradigma

Paradigma imperativo – variabile modificabile:

contenitore (locazione) dotato di nome e che può contenere

valori solitamente di tipo omogeneo

modifiche di valore tramite comandi di assegnamento

NB: In matematica il valore di un’incognita non è modificabile

Paradigma ad oggetti – variabile riferimento:

(detto anche reference od object model) meccanismo diaccesso ad un valore memorizzato altrove (heap)

Simile al concetto di puntatorema questo non deve esseremanipolabile




Variabili [. . . cont.]Variabili [. . . cont.]

Paradigma funzionale – identificatore che denota un valore

“Il linguaggi funzionali puri non hanno variabili”(quelle modificabili degli altri paradigmi)

Paradigma logico – idem

Una volta creato un legame (binding)

tra il nome della variabile ed un valore

questo non è più modificabile




AssegnamentoAssegnamento

L’assegnamento è il comando che permette di modificare ilvalore di una variabile modificabile (e quindi lo stato)

Tipico dei linguaggi imperativi

Esempio X := 2 (PASCAL)Dopo l’esecuzione la locazione associata al nome X conterrà ilvalore 2 che sovrascrive il valore precedente

La modifica dello stato è un effetto collaterale

La valutazione di per sé non restituisce, di norma, alcun valore




Assegnamento [. . . cont.]Assegnamento [. . . cont.]

Esempio X := X+1 (PASCAL)

Dopo l’esecuzione la locazione associata al nome X conterrà ilil precedente valore aumentato di 1

Ciò è possibile perché le due occorrenze di una variabile in un

assegnamento hanno significato diverso:

A destra dell’assegnamento ci sono r-valori“r” sta per rightindicano i contenuti delle locazioni (contenitori di valori)

A sinistra dell’assegnamento ci sono l-valori“l” sta per leftindicano (indirizzi di) locazioni

ogni linguaggio di programmazione stabilisce quali

espressioni possono determinare un l-valore





Sintassi

<assegnamento> ::= <espr1> OpAss <espr2>

Semantica

1 Calcola l’l-valore in base all’espressione <espr1>determinando quindi la locazione loc

2 Calcola l’r-valore v, valutando l’espressione <espr2>3 Modifica il valore contenuto in loc con v





In alcuni linguaggi (C e derivati)

Assegnamenti abbreviati, ottimizzati dal compilatore

Incremento/decremento:

pre ++X, --Xpost X++, X--Auto <var> <op>= <espr>

Linguaggi con modello a riferimenti

<var> = <espr>

L’espressione <espr> deve essere valutata producendo unriferimento da assegnare alla variabile riferimento <var>

Utilizzato in JAVA per gli oggetti

mentre le variabili dei tipi primitivi sono modificabili




AgendaAgenda

1 Espressioni

2 Comandi


Tipologie

Comandi condizionali

Comandi iterativi

Programmazione

strutturata

4 Ricorsione




Controllo della sequenzaControllo della sequenza

Comandi esplicitiComposizione (blocco)

Salto

Comandi condizionali (o di selezione)Permettono di specificare alternative con cui continuare la

computazione in dipendenza da condizioni

Comandi iterativiRipetizione di un comando un numero di volte predefinito o

dipendente dal verificarsi di una condizione




Controllo esplicitoControllo esplicitoComando sequenziale

specifica la sequenza tra due comandi più semplici

sintassi

C1; C2L’esecuzione di C2 comincia dopo la terminazione di C1spesso indicato con ;operatore associativo a sinistra

Comando compostoraggruppamento di una sequenza usando delimitatori

begin...endoppure

{...}usabile in luogo di un comando semplice




Controllo esplicito [. . . cont.]Controllo esplicito [. . . cont.]

Comando di salto (es. goto)Deriva dal salto incondizionato dell’AssemblyEsempio goto Al’esecuzione del salto trasferisce il controllo al punto

etichettato da A (potrebbe anche essere un numero di riga)Molto avversato1

Non essenziale, grazie al TEOREMA DI BÖHM-JACOPINI

I salti a grandi distanze diminuiscono la leggibilità

e quindi riuso e manutenibilità

Si accorda male con gli altri costrutti




Controllo esplicito [. . . cont.]Controllo esplicito [. . . cont.]

Salti controllatia distanze brevi presenti in molti linguaggi

returnrestituzione del controllo (e di un valore)

al ritorno da sottoprogramma, funzione, metodo

breakuscita da un ciclo o selezione multipla

continueterminazione dell’iterazione corrente per continuare con la

prossima

EccezioniSalto (implicito/esplicito) ad un flusso di controllo alternativo

1Dijkstra “Go to statement considered harmful”, Communications of the ACM,

11(3), 1968


http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD215.PDF



Comandi condizionali – ifComandi condizionali – ifEsprimono alternative nella computazione

Comando if (introdotto da ALGOL)sintassi

<if> ::= if <espr> then <cmd1> [else <cmd2>]La presenza di if annidati porta ad ambiguità

generalmente un else dipende dall’if più internooppure si usa un terminatore (endif)

Alcuni linguaggi abbreviano esplicitamente l’annidamento di

if con la parola chiave elseifImplementata attraverso i salti condizionati dell’Assembly




Condizionali a selezione multiplaCondizionali a selezione multiplaComando di selezione multipla

sintassi

<case> ::= case <espr> of <listacasi> [else <cmd>]<listacasi> ::= <etichetta> : <cmd> [<listacasi>]etichette rappresentate da una o più costanti (o intervalli)

il tipo di val. ammesso dipende dai linguaggi

in genere scalari

Più leggibile degli if annidatiRealizzato attraverso una jump table

vantaggio: in origine, implementazione più efficiente di quella

degli if annidatisvantaggio: la jump table può consumare spazio se i valori

sono distanti

Differenti comandi a seconda del linguaggio

case (PASCAL) e switch (C e derivati)




Condizionali a selezione multipla [. . . cont.]Condizionali a selezione multipla [. . . cont.]istruzioni prima di casecalcola v da Exp

if (v < label1) salta a L(n+1)if (v > labeln) salta a L(n+1)

salta a L(0)+v*ksalta a L(1) L(0)salta a L(2)

...salta a L(n)

C1 L(1)salta a FINE

C2 L(2)salta a FINE

...Cn L(n)

salta a FINECn+1 L(n+1)

istruzioni dopo case FINEramo else

rami alternativi

jump table

controllo limitivalutazione espressione




Comandi iterativiComandi iterativi

sequenza e selezione (senza salti)

possono esprimere una computazione finitadi lunghezza proporzionale alla lunghezza del programma

linguaggi a basso livello

salti: jump, gotolinguaggi ad alto livello

iterazione strutturata

iterazione determinataiterazione indeterminata

ricorsione

iterazione implicita




Iterazione indeterminataIterazione indeterminataIterazione logicamente controllata formata da 2 parti

condizione (o guardia): espressionecorpo comando

sintassi (ALGOL e derivati)

while <Bespr> do <cmd>

1) viene valutata l’espressione (booleana) <Bespr>2) se vera

si esegue il comando <cmd>si torna al passo precedente

altrimenti termina

implementata sulla macchina fisica con un salto condizionato

sequenza + selezione + iterazione indeterminata

=⇒ Turing-completezza del linguaggio




Iterazione indeterminata [. . . cont.]Iterazione indeterminata [. . . cont.]

In molti linguaggi esiste anche l’istruzione che esegue il controllodopo aver eseguito il comandoPASCAL:

repeat <cmd> until <Bespr>corrisponde a:

<cmd>; while not <Bespr> do <cmd>C, C++, JAVA:

do <cmd> while <Bespr>corrisponde a:

<cmd>; while (<Bespr>) <cmd>




Iterazione determinataIterazione determinataIterazione controllata numericamente

meno potente di quella indeterminata ma utile (prammatica)

sintassi (generica)

for <var> = <espr1> to <espr2> by <espr3> do <cmd>

dove

<var> è la variabile di controllo del ciclo<espr1> ed <espr2> rappresentano, rispettivamente, i valoriiniziale e finale assunti dalla variabile

<espr3> rappresenta l’incremento progressivo della variabile,dopo aver eseguito il corpo <cmd>

vincolo (semantica statica)

la variabile di controllo non può essere modificata nel corpo




Iterazione determinata [. . . cont.]Iterazione determinata [. . . cont.]

Semantica

1) valutare <espr1>, <espr2>, <espr3> e ricordare i valori,risp., val1 e val2 e val3

2) inizializzare la <var> a val13) se il valore della <var> è maggiore di val2 termina4) eseguire il comando <cmd> del corpo5) incrementare il valore di <var> del valore di val36) tornare al passo 3)





Osservazionise l’incremento (val3) è negativo, il test al passo 3) è perminore anziché maggiore

numero iterazioni (iteration count):ic =

val2− val1+ val3val3

non è possibile avere cicli infiniti





Caratteristiche dei nei diversi linguaggi

non modificabilità della var. di controllo

numero di iterazioni

se val1 > val2 il corpo non viene mai eseguitoalcuni linguaggi eseguono il test dopo l’esecuzione del corpo

passo costante ?

in ALGOL e PASCAL potrebbe anche essere negativo

parole chiave downto o reversein FORTRAN: calcolo di ic

se positivo viene usato per controllare il ciclo,

altrimenti termina





valore finale dell’indice

la var. di controllo è visibile fuori dal ciclo ?

si possono avere ambiguità o errori

in FORTRAN e PASCAL il val. è indefinito

(dipende dalla particolare implementazione)

In ALGOLW e IV, e anche in ADA la var. è locale al ciclo

salto del ciclo

in alcuni linguaggi è permesso uscire prematuramente con un

goto





In C e suoi derivati

Sintassi

for (<esp1>; <esp2>; <esp3>) <cmd>Semantica

1) valuta esp12) valuta esp2; se è nulla termina3) esegui il comando <cmd> del corpo4) valuta esp3 e riprendi da 2)nessun vincolo sui valori delle espressioni né sulla

modificabilità delle variabili coinvolte nelle espressioni

tuttavia le variabili di controllo sono spesso locali al ciclo

(C++ e JAVA)

si sfrutta spesso il fatto che in C anche un comando produce

un valore (quindi può essere visto come espressione)





Iterazione determinata for-eachIterazione per la scansione di tutti gli elementi di una

struttura dati

es. scansione array

Sintassi

foreach (<parFormale>:<espr>) <cmd>si applica il comando <cmd> ad ognuno degli elementiselezionati (<parFormale>) dalla struttura dati cherappresenta il valore di <espr>spesso correlato alla possibilità di esprimere tipi iterabili

in JAVA (ver. 5+) parola chiave for applicabile ai sottotipidell’interfaccia Iterable della libreria standard




Programmazione strutturataProgrammazione strutturataprogettazione top-down (o comunque gerarchica)

modularizzazione del codice

raggruppare codice che svolge una specifica funzione

costrutti per l’astrazione del controllo (sottoprogrammi)

uso di nomi significativi + uso estensivo dei commenti

essenziali per la leggibilità, la verifica e il riuso del codice

uso di tipi strutturati

aggregati di tipi anche differenti

es. record

uso di costrutti strutturati per il controllo

1 punto di ingresso; 1 punto di uscita

consente la nidificazione del codice

più leggibile e modificabile




AgendaAgenda

1 Espressioni

2 Comandi


4 Ricorsione

Definizione

Ricorsione in coda

Ricorsione vs. Iterazione




RicorsioneRicorsioneInformalmente:

una funzione è ricorsiva se nel corpo compare una chiamata a sé

stessa (diretta) o ad altra funzione che ne provocherà la chiamata(indiretta)

es. mutua ricorsione: P chiama Q che, a sua volta, chiama P

Esempio calcolo dell’n-esimo termine della succ. di Fibonacci

1 int fib (int n) {2 if (n == 0) return 1;3 else if (n == 1) return 1;4 else return fib(n-1) + fib(n-2);5 }




Ricorsione [. . . cont.]Ricorsione [. . . cont.]

In matematica: def. induttivef chiama se stessa su argomenti “più piccoli”f definita su un dominio con garanzia di assenza di cateneinfinite di elementi più piccoli in modo da giungere prima opoi a casi di base

le def. devono essere ben poste

es. la seguente def. è problematica:foo(0) = 1foo(n) = foo(n) + 1 per n > 0nessuna funzione totale sui naturali può soddisfare le eq.

e nemmeno la seguente è ben posta:fie(1) = fie(1)tautologica, infinite funzioni corrispondono




Ricorsione [. . . cont.]Ricorsione [. . . cont.]

In informatica: sottoprogramma che richiama se stesso

è possibile implementare anche le funzioni mal poste

queste possono divergere (sempre o per alcuni input)

casi precedenti

1 int foo(int n) {2 if (n == 0) return 1;3 else return foo(n)+1;4 }

1 int fie(int n) {2 if (n == 1) return fie(1);3 }

non sono un problema: programmi = funzioni parziali




Ricorsione in codaRicorsione in coda

la ricorsione rende necessaria la gestione dinamica della

memoria (pila di record di attivazione)

istanze dello stesso sottoprogramma in numero variabile

a volte è possibile risparmiare questo spazio in memoria a

seconda della definizione della funzione

riutilizzo dello stesso spazio in memoria




Ricorsione in coda [. . . cont.]Ricorsione in coda [. . . cont.]

1 int fatt (int n) {2 if (n<=1)3 return 1;4 else5 return fatt(n-1)*n;6 }

puntatore di catena dinamicaindirizzo risultatoparametro n

risultato intermedio (fatt(n-1))RdA semplificato

non è ricorsiva in coda

valore del risultato intermedio nel RdA per f(n) può esseredeterminato solo al termine della chiamata di f(n-1)

e così via....

quindi tutti i RdA devono coesistere





PCD

Ind. R.

n 1

fact(n-1)

fact(1)

PCD

Ind. R.

n 2

fact(n-1)

fact(2)

PCD

Ind. R.

n 3

fact(n-1)

chiamate ricorsive

fact(3)

PCD

Ind. R.

n 2

fact(n-1) 1

fact(2)

PCD

Ind. R.

n 3

fact(n-1)

ritorno da fact(1)

fact(3)

PCD

Ind. R.

n 3

fact(n-1) 2

ritorno da fact(2)

fact(3)





1 int fattrc (int n, int ris) {2 if (n<=1)3 return ris;4 else5 return fattrc(n-1, n*ris);6 }

chiamate ricorsive prodotte da fattrc(n,1):fattrc(n,1):fattrc(n-1,n*1)fattrc(n-2,(n-1)*n*1). . .

fattrc(1,2*...*(n-1)*n*1)valore finale pari a quello dell’ultima chiamata

non occorre risalire alle chiamate precedenti: basta 1 RdA

la potrebbe memoria essere allocato staticamente





Una chiamata di g da f si dice in coda (tail call)se f restituisce il valore ricevuto da gsenza ulteriori computazioni

f si dice ricorsiva in coda (tail recursive)se tutte le sue chiamate ricorsive sono chiamate in coda

Osservazionivale anche e soprattutto per f = gpiù complesso il caso in cui siano ammesse funzioni come

parametri

funzioni di ordine superiore

vantaggio: implementabile come ottimizzazione da parte del

compilatore





In generale,

si può trasformare automaticamente una funzione ricorsiva in

una funz. ricorsiva in coda equivalente:si deve anticipare tutta la computazione che avverrebbe dopola chiamata ricorsiva

quanto non può essere anticipato va passato nella chiamata

attraverso parametri aggiuntiviris nell’esempio precedente

tramite continuazione (continuation passing style)funzione di appoggio per la parte rimanente da calcolarese usa variabili da valutare nell’ambiente del chiamantenon basta più un solo RdAvenendo così meno, in parte, il risparmio





Esempio calcolo dell’n-esimo termine della succ. di Fibonacci

con funzione ricorsiva in coda:

1 int fibrc (int n, int r1, int r2) {2 if (n == 0) return r2;3 else if (n == 1) return r2;4 else return fibrc(n-1,r2,r1+r2);5 }6

7 int fib (int n) {8 return fibrc(n,1,1);9 }




Ricorsione vs. IterazioneRicorsione vs. Iterazione

criteri di scelta

predisposizione del programmatore

natura del problema

strutture dati coinvolte

numeriche: vettori, matrici, tabelle, file, record, . . .

simboliche: liste, alberi, grafi, . . .

parametri di efficienza

velocità di computazione memoria necessaria




EserciziEsercizi

Dal libro di testo (2a ed.)

Es.1

Es.2

Es.3

Es.4

Es.5

Es.6




RiferimentiRiferimenti

Gabbrielli & Martini: Linguaggi di Programmazione,

McGraw-Hill 2a edizione. Cap. 8




Strutture di Controllolacam.di.uniba.it/~nico/corsi/lingpro/materiale/LP... ·...

Documents

Transcript of Strutture di Controllolacam.di.uniba.it/~nico/corsi/lingpro/materiale/LP... ·...