Capitolo 7

PROCEDURE E FUNCTION.

Nel capitolo precedente abbiamo dovuto riscrivere, durante la stesura di algoritmi, interi blocchi di istruzioni per svolgere operazioni identiche su variabili diverse. Ad esempio, nell'algoritmo relativo al problema 12, la maggior parte delle istruzioni serve per risolvere il problema della lettura dei due vettori, mentre per la risoluzione del problema del confronto sono utilizzate solo 5 righe di codice. Lo stesso dicasi per quasi tutti i problemi visti nel capitolo 6. Riscrivere parecchio codice che differisce solo per le variabili su cui si opera, oltre ad essere noioso e poco produttivo per il programmatore, spesso rende il programma finale meno chiaro. Le istruzioni da ripetere potrebbero essere anche molte centinaia, rendendo l'algoritmo illeggibile. Se avessimo la possibilità di definire a piacimento nuove istruzioni ecco che il problema sarebbe risolto.

Esempio: sommare tre vettori di numeri.

Definiamo la somma di tre vettori, con eguale numero di componenti, come un vettore che ha per componenti la somma delle componenti dei tre vettori. Formalizzando avremo:

BEGIN

END;

Supponiamo di avere a disposizione nuove istruzioni, come ad esempio una istruzione di lettura che ci restituisca un vettore con associato il numero di elementi effettivamente introdotto. Allora "leggi a", "leggi b", "leggi c" diventerà:

dove con n_a, n_b, n_c si intende il numero di elementi del vettore a, del vettore b e del vettore c.

Similmente somma_vet potrebbe essere un'istruzione che avuto in ingresso i tre vettori da sommare, restituisce in un quarto vettore la somma.

dove

- a, b, c sono i tre vettori di cui si richiede la somma

- n_a, n_b, n_c sono le quantità di elementi dei tre vettori

- r è il vettore contenente il risultato della somma

- n_r è la quantità di elementi del vettore somma

Anche "scrivi ris" potrebbe diventare:

Il nostro algoritmo diventerà:

BEGIN

END.

Come si può osservare dall'esempio, l'introduzione di nuove istruzioni presenta numerosi vantaggi e precisamente:

• riduce o elimina la ripetizione di istruzioni identiche. Definendo nuove istruzioni vengono eliminate tutte le ripetizioni di codice per svolgere compiti identici su variabili diverse.
• chiarezza del programma. I programmi diventano più chiari e leggibili perchè sfrondati da dettagli inutili per la comprensione dell'algoritmo. Nell'esempio proposto la somma dei vettori deve essere eseguita una sola volta, ma l'introduzione della nuova istruzione rende l'algoritmo più chiaro e leggibile.
• decomposizione del problema in sottoproblemi. Tutti i problemi proposti sinora sono stati descritti in prima analisi come una sequenza di sottoproblemi. L'introduzione di nuove istruzioni offre la possibilità di risolvere separatamente i sottoproblemi, fornendo così uno strumento fondamentale di programmazione.

Il linguaggio Pascal fornisce due costrutti per la realizzazione di nuove istruzioni: le procedure e le function.

Una procedura è un'unità di programma indipendente. Ha una propria dichiarazione di tipi, costanti e variabili ed eventualmente di altre procedure o funzioni. Come esempio vediamo la dichiarazione di una procedura per la lettura di un vettore.

PROCEDURE read_vet( VAR x:vettore; VAR n_x:INTEGER );

VAR

BEGIN

END;

Nella dichiarazione di una procedura si possono individuare due parti: il titolo della procedura, composto dal nome e da eventuali variabili, e il corpo, composto dalla sequenza di istruzioni che devono essere svolte racchiuse tra begin/end.

Il nome della procedura compare subito dopo la parola riservata procedure e può essere seguito da una lista di variabili con associato il tipo. La lista, se compare, è racchiusa tra due parentesi rotonde.

Nell'esempio visto prima il nome della nuova istruzione è read_vet e la lista delle variabili è composta da due elementi, x e n_x, seguiti dal tipo corrispondente. Queste variabili vengono chiamate parametri formali.

Subito dopo possono comparire la dichiarazione di nuovi tipi, nuove variabili o anche nuove procedure o funzioni. Nell'esempio compare solo la dichiarazione di una variabile, i, preceduta dalla parola riservata var.

Il corpo della procedura descrive le operazioni che debbono essere compiute sui parametri in ingresso quando la nuova istruzione viene eseguita. Possono essere utilizzate tutte le istruzione del Pascal: il corpo è racchiuso da begin/end;.

Come già osservato, lo scopo di una procedura è descrivere le istruzioni che debbono essere eseguite per operare su dei dati in ingresso per ottenere dei risultati. E` importante capire che si tratta di descrizione. Non vengono eseguite azioni sino a quando la nuova istruzione non viene usata nel corso del programma. Per esempio, per richiedere l'esecuzione della procedura read_vet bisogna scrivere così:

Questa chiamata è corretta se

• a è di tipo vettore
• n_a è di tipo INTEGER

La chiamata di una procedura è corretta se nella chiamata vengono indicate tante variabili quanti i parametri formali della procedura e nello stesso ordine di tipo. In pratica i parametri formali vengono inizializzati con variabili indicate nella chiamata dette parametri attuali. L'operazione avviene in base alla posizione occupata.

Riepilogando possiamo dire che con la definizione di procedura si descrive un'operazione complessa che deve essere svolta su dei dati di un determinato tipo. Solo al momento della chiamata vengono definiti i dati sui quali la procedura dovrà operare. I dati dovranno essere dello stesso tipo dei parametri formali e nello stesso numero.

Esempio.

Sia:

PROCEDURE write_ris( x:vettore; n_x:INTEGER );

VAR

BEGIN

END;

la dichiarazione di un'istruzione che stampa un vettore di numeri.

Per utilizzare tale procedura si scriverà:

La chiamata sarà corretta se e solo se sarà

Dopo la chiamata il parametro formale x sarà inizializzato con il contenuto di r mentre il parametro formale n_x sarà inizializzato con il contenuto di n_r.

Il programma completo per il problema presentato in precedenza sarà:

PROGRAM completo( INPUT, OUTPUT );

CONST

TYPE

VAR

PROCEDURE read_vet( VAR x:vettore; VAR n_x:INTEGER );

VAR

BEGIN

END;

PROCEDURE write_ris( x:vettore; n_x:INTEGER );

VAR

BEGIN

END;

PROCEDURE somma_vet( a, b, c :vettore; VAR r :vettore;

VAR

BEGIN

END;

BEGIN { main program }

Nei capitoli precedenti abbiamo avuto a che fare spesso con blocchi di istruzioni che operavano su dati per dare in risposta un valore: in matematica quando si verifica una situazione del genere si parla di funzione. Ad esempio nel problema di ricerca del massimo di un vettore si può pensare ad una funzione che, operando su un vettore di numeri, restituisce come risultato un valore numerico, il massimo.

Esempio: ricerca del massimo di un vettore

ALGORITMO:

BEGIN

END;

massimo è una funzione che ha come dominio v e che restituisce il valore massimo.

Per le function valgono le osservazioni viste in precedenza per le procedure. In questo paragrafo sottolineeremo le differenze.

Esempio: ricerca del massimo di un vettore di REAL con alla posizione 0 la dimensione ( dimensione > 0).

FUNCTION massimo( v:vettore ):REAL;

VAR

BEGIN

END;

In questo esempio si possono osservare alcune differenze con quanto visto per le procedure:

• nella dichiarazione del nome e dei parametri formali compare una nuova informazione: il tipo del risultato della funzione. Nell'esempio proposto il tipo è REAL. Questo avviene inserendo il carattere di ':' (duepunti) dopo la lista dei parametri formali. Il risultato di una funzione può essere di qualsiasi tipo scalare.
• Un'altra differenza con le procedure è l'indicazione del risultato: in ogni function deve comparire tra le istruzioni un'assegnazione che abbia come identificatore della variabile alla quale assegnare il valore il nome della function. Nel nostro esempio questo avviene con l'assegnazione:

Per il resto valgono tutte le osservazioni fatte con le procedure.

Così come per le procedure, anche le function descrivono un'operazione che avviene su dati generici avuti in ingresso e che però fornisce in output un risultato scalare. L'operazione vera e propria avviene solo al momento della chiamata. Per esempio, utilizzando la function massimo possiamo chiamarla così:

Per quanto riguarda l'associazione tra parametri formali e attuali valgono le stese considerazioni viste con le procedure. Il meccanismo di chiamata è però diverso. Mentre con le procedure si può pensare a nuove istruzioni, con le function il paragone corretto è con le funzioni matematiche per cui si può pensare di utilizzare direttamente il valore che si ottiene in risposta. Ad esempio poichè il problema richiede la stampa del massimo avremmo potuto scrivere il programma così:

BEGIN

END.

La function viene attivata utilizzandola in un'espressione esattamente come se fosse una variabile o una costante. Poichè inoltre ogni function ha associato un tipo, l'espressione in cui compare deve essere compatibile con il tipo dichiarato.

Il programma completo per il problema della stampa del massimo sarà:

PROGRAM stampa_massimo( INPUT, OUTPUT );

CONST

TYPE

VAR

PROCEDURE leggi( VAR x:vettore );

VAR

BEGIN

END;

FUNCTION massimo( v:vettore ):REAL;

VAR

BEGIN

END;

END.

Come abbiamo già osservato parecchie volte nei paragrafi precedenti, le procedure e le function, cioè i sottoprogrammi, possono essere pensati come veri e propri programmi. A loro sono permesse tutte le operazioni che sono definite in Pascal, possono cioè fare input/output, dichiarare variabili, tipi, costanti, possono dichiarare nuovi sottoprogrammi, possono infine utilizzare sottoprogrammi dichiarati precedentemente. Oltre a queste operazioni comuni esiste il meccanismo dei parametri che abbiamo descritto brevemente in precedenza. Vediamo allora in dettaglio come avviene il passaggio dei parametri tra il programma chiamante e il sottoprogramma.

Negli esempi proposti nei paragrafi precedenti abbiamo notato due modi diversi per indicare le variabili nella lista dei parametri. Ad esempio nella dichiarazione della procedure read_vet abbiamo scritto:

mentre nella dichiarazione della procedure write_ris abbiamo scritto:

Come si può osservare nella prima dichiarazione abbiamo utilizzato la parola riservata VAR davanti ad ogni variabile definita nella lista dei parametri, mentre nella seconda non compare VAR. Sempre in precedenza abbiamo utilizzato anche una procedure così dichiarata:

dove si può notare che nella lista dei parametri formali compaiono variabili con VAR e variabili senza VAR.

Si parla di passaggio per valore quando non si usa VAR, si parla di passaggio per riferimento quando compare VAR.

La differenza tra i due meccanismi è la seguente:

• passaggio per valore: al momento della chiamata del sottoprogramma viene calcolato il valore del parametro attuale con il quale si inizializza il parametro formale. Si può pensare come la creazione di una copia del parametro attuale chiamata con il nome del parametro formale. Il sottoprogramma opera sulla copia.
• passaggio per riferimento: al momento della chiamata del sottoprogramma il parametro formale viene sostituito con il parametro attuale. Il sottoprogramma opererà allora sull'originale. Questo meccanismo viene utilizzato per ottenere i risultati dal sottoprogramma.

PROCEDURE uno( x:INTEGER );

BEGIN

END;

END.

Il risultato sarà

2

1

Il parametro attuale al momento della chiamata conterrà il valore 1. Viene creata una copia che verrà utilizzata dalla procedura che incrementerà il valore. La writeln nella procedure stamperà il valore 2. Poichè la procedure ha operato su una copia, la variabile a nel propramma principale non risulterà modificata. La writeln del programma principale stamperà 1

PROCEDURE uno( VAR x:INTEGER );

BEGIN

END;

END.

Il risultato sarà

2

2

Il parametro formale, al momento della chiamata, verrà sostituito con il parametro attuale. Tutte le operazioni compiute nella procedure sulla variabile x in realtà saranno effettuate sulla variabile a.

PROCEDURE uno( x:INTEGER );

BEGIN

END;

Il risultato sarà

4

1

Il parametro formale x sarà inizializzato con il risultato dell'espressione a + 2.

PROCEDURE uno( VAR x:INTEGER );

BEGIN

END;

END.

La chiamata alla procedure uno è scorretta. a+2 è un'espressione e non una variabile.

Esempio 5: riprendiamo il problema 7 svolto nel capitolo precedente: dato un vettore v e un numero x stampare la prima occorrenza di x in v.

STRUTTURA DATI:

CONST

TYPE

VAR

ALGORITMO:

BEGIN

END.

Sviluppando nei dettagli:

• leggi( v ) è una procedure così definita:

• ricerca( v, x ) è una function che avuto in ingresso v e x restituisce un intero. Se risultato=0 significa non trovato, se <>0 è la prima posizione dove è stato trovato.

• scrivi è una procedura che, avuto in ingresso un numero intero p stamperà i seguenti messaggi:

Osservazione: in questo paragrafo abbiamo visto con precisione il passaggio di variabili per riferimento e per valore, indicando quando utilizzare l'uno o l'altro. Esiste un'eccezione a quanto detto ed è il caso di passaggio di una grossa quantità di dati, per esempio di un vettore. In questo caso, anche se occorresse un passaggio per valore si preferisce utilizzare un passaggio per riferimento, sia per ragioni di velocità sia di spazio. Infatti fare una copia di un vettore molto grande provoca un grosso spreco di spazio e di tempo.

Esercizi.

1. Utilizzando la struttura dati del problema 13 del capitolo 6 realizzare i seguenti sottoprogrammi:

1. FUNCTION lenstr: restituisce la lunghezza di una stringa.
2. PROCEDURE concat: concatena due stringhe.
3. FUNCTION substr: restituisce l'indice della prima occorrenza della stringa b in una stringa a.
4. PROCEDURE copystr: copia da una stringa a in una stringa b a partire da n per lunghezza l.
5. PROCEDURE insstr: inserisce in una stringa a una stringa b a partire da n.
6. PROCEDURE delestr: cancella da una stringa a, a partire da n, l caratteri.

1. Utilizzando la struttura dati del problema 16 del capitolo 6 realizzare i sottoprogrammi dell'esercizio precedente.
2. Scrivere una function di tipo boolean che inserisca un elemento n in un vettore ordinato di numeri mantenendo l'ordinamento e segnalando se non c'è più spazio.

Abbiamo osservato che ogni procedure o function può avere definite al proprio interno costanti, tipi, variabili o addirittura altre procedure o function. Tutti questi oggetti esistono all'interno del sottoprogramma in esame, rappresentano cioè l'ambiente di lavoro. Solo le istruzioni di quel determinato sottoprogramma hanno accesso a tali oggetti. Nell'ambiente esterno non esistono. Questi oggetti sono detti locali. Però l'ambiente di lavoro di un sottoprogramma non è costituito solo dagli oggetti locali ma anche da tutti quegli oggetti, comprese procedure e function definite nel sottoprogramma in cui è inserito il sottoprogramma in esame. Se gli oggetti sono definiti a livello di programma principale allora vengono detti globali e sono a disposizione di qualunque sottoprogramma. Sottolineiamo inoltre che le variabili definite in un sottoprogramma perdono il loro contenuto tra una chiamata e l'altra.

PROGRAM caos( INPUT, OUTPUT );

VAR

PROCEDURE livello1;

VAR

FUNCTION livello2_a :REAL;

VAR

BEGIN { codice per livello2_a }

....

....

END;

PROCEDURE livello2_b;

VAR

BEGIN { codice per livello2_b }

....

....

....

END;

BEGIN { codice per livello 1 }

....

....

END;

BEGIN { programma principale }

....

....

....

END.

Le variabili a0, b0, c0 sono definite nel programma principale, sono globali e fanno parte dell'ambiente di tutti i sottoprogrammi.

Le variabili a1, b1, c1 sono definite in livello1, fanno parte dell'ambiente di livello1 e di quello di livello2_a e livello2_b.

Le variabili definite in livello2_a fanno parte solo dell'ambiente di livello2_a così come quelle definite in livello2_b appartengono all'ambiente di livello2_b.

Si potrebbe verificare un conflitto di nome quando una variabile locale ha lo stesso nome di una variabile definita nell'ambiente superiore. In questo caso il Pascal applica la regola che l'ultima definita è quella accessibile.

Esempio.

PROGRAM caos1( INPUT, OUTPUT );

VAR

a, b : REAL;

PROCEDURE uno;

VAR

a1, b : CHAR;

BEGIN { codice per uno }

....

....

END;

BEGIN { programma principale }

....

....

END.

Tra le variabili locali di uno compare la variabile b che ha lo stesso nome della variabile b definita a livello globale. La variabile globale b non appartiene allora all'ambiente di uno.

Prima di chiudere il paragrafo sottolineiamo due aspetti molto importanti di quanto abbiamo detto:

• le variabili globali possono essere utilizzate come variabili di output per una procedura. E` però importante non abusare di questo meccanismo per non incorrere in spiacevoli errori soprattutto quando si sta imparando a programmare.
• le variabili locali sono accessibili solo localmente, quindi sono protette da accessi indesiderati da parte di altri sottoprogrammi. Sarà quindi possibile scrivere dei sottoprogrammi senza conoscere l'ambiente nel quale il sottoprogramma verrà utilizzato. Ad esempio possiamo sviluppare tutte le funzioni elementari per il trattamento delle stringhe senza conoscere l'ambiente nel quale verranno utilizzate.

Esempi.

1. Verificare il funzionamento dei seguenti programmi:

In a la procedura uno utilizza la variabile globale x incrementandola. Alla fine x varrà due.

In b due utilizza il parametro formale x che è di tipo diverso dalla variabile globale x. Nella procedura due non è possibile fare riferimento alla variabile globale x. La stampa di x in due produrrà a.

In c dopo la chiamata di tre la variabile x conterrà tre. Un uso simile delle variabili è vivamente sconsigliato.

In d la variabile x conterrà due dopo la chiamata di quattro.

Rispondere alle seguenti domande:

1. PROCEDURE esempio( x:INTEGER );

BEGIN

x:=x+1;

WRITELN( x )

END;

se si richiama la procedura esempio

a:=1;

esempio( a );

WRITELN( a );

l'output sarà:

1 2

1 1

2 2

2 1

 

2. PROCEDURE scambio( VAR x,y:INTEGER );

BEGIN

x:=y

END;

se si richiama la procedura scambio

a:=1; b:=3;

scambio( a, b );

WRITELN( a:2, b:2 );

l'output sarà:

1 3

3 1

3 3

1 1

 

3. PROCEDURE inverti( x, y:INTEGER );

VAR

z :INTEGER;

BEGIN

z:=x; x:=y; y:=z

END;

se si richiama la procedura inverti

a:=1; b:=3;

inverti( a, b );

WRITELN( a );

WRITELN( b );

l'output sara':

1 3

3 1

1 1

3 3

 

4. PROCEDURE inverti( VAR a, b:INTEGER );

BEGIN

z:=a; a:=b; b:=z

END;

se si richiama la procedura inverti

z:=5; a:=1; b:=2;

inverti( b, a );

WRITELN( z, a, b );

l'output sarà:

1 1 2

5 1 2

2 2 1

5 2 1

 

5. PROCEDURE incremento( VAR a:INTEGER; b:INTEGER );

VAR

i:INTEGER;

BEGIN

FOR i:=1 TO 100 DO

vet[i]:=i;

a:=vet[1]+vet[3];

b:=vet[5]

END;

se si richiama la procedura incremento

FOR i:=1 TO 100 DO

vet[i]:=0;

a:=1; b:=3;

incremento( a, b );

WRITELN( a, b, vet[7] );

l'output sarà:

1 3 0

1 3 7

4 5 0

4 3 7

 

6. PROCEDURE incremento( VAR x:vettore );

VAR

vet :VETTORE;

i :INTEGER;

BEGIN

FOR i:=1 TO 100 DO

vet[i]:=x[i]+1

END;

se si richiama incremento

FOR i:=1 TO 100 DO

vet[i]:=i;

a:=vet[1]; b:=vet[3];

incremento( vet );

a:=vet[1]; b:=vet[3];

WRITELN( a, b );

l'output sarà:

1 3

2 4

0 0

Nessuna delle precedenti

 

7. PROCEDURE inverto( VAR x:INTEGER; y:INTEGER );

VAR

z:INTEGER;

BEGIN

z:=x;

WRITELN( z:2 );

x:=y; y:=z

END;

se si richiama la procedura inverto

z:=1; a:=2; b:=3;

inverto( a, b );

WRITELN( a:2, b:2 );

l'output sarà:

1 3 3

2 3 2

2 3 3

1 3 2

 

8. PROCEDURE inverto( VAR x, y:vettore );

VAR

z,

i:INTEGER;

BEGIN

FOR i:=1 TO 100 DO BEGIN

z:=x[i]; x[i]:=y[i]; y[i]:=z

END

END;

se si richiama la procedura inverto

FOR i:=1 to 100 DO BEGIN

a[i]:=i; b[i]:=i+3

END;

inverto( a, b )

WRITELN( a[2], b[1] );

l'output sarà:

1 5

5 1

1 1

5 5

 

9. PROCEDURE inverto( VAR x, y:vettore );

VAR

z:vettore;

i:INTEGER;

BEGIN

FOR i:=1 TO 100 DO

z[i]:=x[i];

FOR i:=1 TO 100 DO

x[i]:=y[i];

FOR i:=1 TO 100 DO

y[i]:=z[i]

END;

se si richiama la procedura inverto

FOR i:=1 TO 100 DO BEGIN

a[i]:=i;

b[i]:=i+3

END;

inverto( a, b );

WRITELN( a[1], b[1] );

l'output sarà:

1 4 4 1

1 1

4 4

 

10. PROCEDURE esempio( a, b:INTEGER );

Spesso un sottoprogramma deve effettuare controlli sulla correttezza dei dati in ingresso prima di svolgere il proprio compito. Se i dati sono corretti procede. Il programmatore deve comunque sapere se l'operazione richiesta è andata a buon fine e certamente non basta un messaggio.

Esempio 1: scrivere una funzione che calcoli la radice di un numero.

Abbiamo risolto questo problema nel capitolo 5. Riprendiamo l'algoritmo e costruiamo la function radice che avuto in ingresso un numero calcola la radice quadrata.

FUNCTION radice( v:REAL ) :REAL;

CONST

precisione = 1e-10;

VAR

BEGIN

y:= 1;

REPEAT

x:= y;

y:= ( x * x + v ) / (2 * x)

UNTIL abs (x - y) < precisione;

radice:=y

END;

Il calcolo della radice quadrata può avvenire solo se il numero v è positivo. Scrivere però un semplice messaggio di errore non è sufficiente:

FUNCTION radice( v:REAL ) : REAL;

...

BEGIN

IF v<0 THEN WRITELN('Errore nei dati')

ELSE

...

...

END;

L'operatore riceverà il messaggio di errore ma il programma che ha richiesto questa operazione non potrà in alcun modo saperlo e continuerà come nulla fosse. Nel caso esaminato si può risolvere il problema con questa considerazione: poichè il risultato della funzione radice sarà sempre un numero positivo potremmo usare un numero negativo, ad esempio -1, per segnalare l'eventuale errore.

FUNCTION radice( v:REAL ) :REAL;

CONST

precisione = 1e-10;

VAR

x, y : REAL;

BEGIN

IF v<0 THEN radice:=-1

ELSE BEGIN

y:= 1;

REPEAT

x:= y;

y:= ( x * x + v ) / (2 * x)

UNTIL abs (x - y) < precisione;

radice:=y

END

END;

Il programma chiamante potrà controllare il risultato e se ottiene -1 saprà che è avvenuto un errore.

Non sempre è possibile utilizzare dei valori per segnalare l'errore. Vediamo il seguente esempio.

Esempio 2: dato un vettore v e un intero p scrivere un sottoprogramma che restituisca v[p].

Supponiamo che la struttura dati sia la seguente:

CONST

dim=100;

TYPE

vettore=ARRAY[0..dim] OF INTEGER;

VAR

vet:vettore;

ris:INTEGER;

v[0] conterrà la dimensione del vettore. Se p<1 OR p>v[0] allora errore.

FUNCTION valore( v:vettore; p:INTEGER; VAR r:INTEGER ):BOOLEAN;

VAR

ok :BOOLEAN;

BEGIN

ok:=(p>=1) AND (p<=v[0]);

IF ok THEN r:=v[p];

valore:=ok;

END;

La chiamata sarà:

IF valore( vet, 5, ris ) THEN

{ utilizza ris }

...

Questa soluzione del problema può diventare molto pesante per il programmatore. Supponiamo di avere diverse procedure che vengono richiamate sequenzialmente, ciascuna con la possibilità di non svolgere il compito previsto per qualche errore. Il programma principale sarà:

BEGIN

proc1( ..... );

IF NOT errore THEN BEGIN

proc2( ... );

IF NOT errore THEN BEGIN

proc3( ... );

IF NOT errore THEN BEGIN

proc4( ... );

IF errore THEN

messaggio;

END ELSE

messaggio

END ELSE

messaggio

END ELSE

messaggio

END.

Già con il richiamo di quattro procedure il programma diventa illeggibile e molto pesante per il programmatore con il proliferare di controlli e di messaggi. Si può allora definire una nuova procedura per la gestione dell'errore, richiamata ogni volta si presenterà un errore grave, che svolgerà tutti i compiti associati all'errore e interromperà l'esecuzione del programma. Ad esempio

PROCEDURE errore( s:messaggio );

BEGIN

WRITELN('ERRORE: ',s);

GOTO 999

END;

dove

- messaggio=PACKED ARRAY[1..50] OF CHAR;

- GOTO 999 è il salto alla label 999, assegnata all'ultima istruzione del programma. La label 999 deve essere dichiarata in testa al programma, insieme alla variabili, tipi e costanti utilizzando la parola chiave LABEL seguita dall'elenco.

Esempio 3: risolvere il problema proposto nell'esempio 2.

FUNCTION valore( v:vettore; p:INTEGER ):INTEGER;

BEGIN

IF (p<1) OR (p>v[0]) THEN errore('ERRORE: fuori intervallo');

valore:=v[p];

END;

Il programma principale dovrà avere la seguente label

PROGRAM principale( INPUT, OUTPUT );

LABEL 999;

....

....

BEGIN { principale }

...

...

999: END.

OSSERVAZIONE: in alcune implementazioni del Pascal non è possibile eseguire in un sottoprogramma il GOTO ad una label definita fuori. In questo caso è sicuramente disponibile una istruzione HALT che, quando eseguita, blocca l'esecuzione del programma.

7.7 Ricorsione.

Uno strumento particolarmente potente in matematica è il principio di induzione: lo schema di induzione permette di definire funzioni aventi come dominio i naturali e come immagine un generico insieme:

f: N -> I

Lo schema di induzione è il seguente:

- si definisce la base di induzione, cioè il valore di f(0).

- si definisce la funzione per k+1, supponendo di averla già definita per k.

Esempio. Vogliamo dimostrare che 1+2+3+4+..+n = n * (n+1) /2

Per n = 1 si ha 1=1.

Supponiamo vero per n:

1+2+3+..n+n+1 = n * (n+1)/2 + (n+1) = (n^2 + 3n + 2) / 2 = (n+1)*(n+2)/2

Il principio di induzione è molto importante in programmazione dove però si preferisce parlare di definizioni ricorsive: una procedura, una funzione, un oggetto viene detto ricorsivo se esso comprende parzialmente se stesso. Una procedura viene detta direttamente ricorsiva se contiene un riferimento esplicito a se stessa; se contiene un riferimento ad una altra procedura che a sua volta richiama la prima allora è detta indirettamente ricorsiva.

Esempio 1: calcolare il fattoriale di n.

Il fattoriale di n è:

1 se n=0,

n * fattoriale di n-1 se n > 0.

Applicando la definizione avremo:

FUNCTION fatt( n:INTEGER ) :INTEGER;

BEGIN

IF n = 0 THEN fatt:=1

ELSE fatt:= n * fatt(n - 1)

END;

Esempio 2: calcolare n^m.

Soluzione 1.

Per definizione abbiamo che n^m è:

1 se m=0

n * n^(m-1) se m > 0

Applicando la definizone abbiamo:

FUNCTION exp( n:REAL; m:INTEGER ):REAL;

BEGIN

IF m = 0 THEN exp:=1

ELSE exp:= n * exp(n,m - 1)

END;

Soluzione 2.

Per definizione abbiamo che n^m è:

1 se m=0

(n^(m div 2))^2 se m è pari

n * n^(m-1) se m è dispari

Applicando la definizone abbiamo:

FUNCTION quickesp (x:REAL ; y:INTEGER):REAL;

FUNCTION square(x:REAL):REAL;

BEGIN

square:=x*x

END;

BEGIN

IF y=0 THEN quickesp:=1

ELSE

IF (y mod 2) = 0 THEN quickesp:=square (quickesp (x, y div 2))

ELSE quickesp:= x * quickesp(x, y-1)

END;

Esempio 3: calcolare la somma degli interi compresi tra x e y.

La somma degli interi tra x e y sarà:

0 se x> y

x + somma degli interi compresi tra x+1 e y

Allora avremo:

FUNCTION sommint(x:INTEGER; y:INTEGER):INTEGER;

BEGIN

IF x > y THEN sommint:= 0

ELSE sommint:= x + sommint(x+1,y)

END;

Esempio 4: controllare se un numero è pari o dispari.

Se consideriamo che

0 è pari

un numero m è pari se m-1 è dispari

un numero m è dispari se m-1 è pari

avremo che:

FUNCTION dispari(x:INTEGER):BOOLEAN; forward;

FUNCTION pari (x:INTEGER):BOOLEAN;

BEGIN

IF x = 0 THEN pari:=true

ELSE pari:= dispari(x-1)

END;

FUNCTION dispari (x:INTEGER):BOOLEAN;

BEGIN

IF x = 0 THEN dispari:= false

ELSE dispari:= pari(x-1)

END;

OSSERVAZIONE: il termine forward nella definizione di dispari significa che il corpo della funzione verrà definito successivamente.

Esempio 5: calcolare il m.c.d tra due numeri.

Il massimo comun divisore tra due numeri x e y si può così definire:

se y = 0 sarà x

altrimenti sarà uguale al m.c.d. tra y e il resto tra x diviso y

Allora avremo:

FUNCTION mcd(x:INTEGER; y:INTEGER):INTEGER;

BEGIN

IF y = 0 THEN mcd:=x

ELSE mcd:=mcd(y, x mod y)

END;

Esempio 6: calcolare il massimo tra gli elementi di un vettore.

Il massimo tra gli elementi di un vettore si può così definire:

se il vettore ha un solo elemento il massimo è l'elemento stesso

altrimento è il maggiore tra l'ultimo e il massimo dei precedenti.

In base a questa definizione avremo:

FUNCTION magvet(v:vettore; n:INTEGER):REAL;

FUNCTION mag(x:REAL;y:REAL):REAL;

BEGIN

IF x > y THEN

mag:=x

ELSE

mag:=y

END;

BEGIN

IF n=1 THEN

magvet:=v[1]

ELSE

magvet:= mag(v[n], magvet(v,n-1))

END;

dove

vettore=ARRAY[1..dim] OF REAL;

n è la dimensione di v:vettore

Esempio 7: calcolare la somma degli elementi di un vettore.

Se la dimensione del vettore = 0 la somma è 0

altrimenti sarà uguale a v[n] + somma dei precedenti.

FUNCTION somm(v:vettore; n:INTEGER):REAL;

BEGIN

IF n = 0 THEN somm:=0

ELSE somm:=v[n] + somm(v,n-1)

END;

Esercizi Usando funzioni ricorsive calcolare:

a- il prodotto degli elementi di un vettore.

b- il minimo di un vettore.

c- la media aritmetica degli elementi di un vettore.

d- il prodotto scalare di due vettori.

e- la rappresentazione ottale di un numero intero.

f- la somma degli elementi pari di un vettore di interi.

g- il prodotto degli elementi di posizione pari di un vettore.

h- il numero di elementi negativi di un vettore.

7.8 Scomposizione dell'algoritmo.

Dagli esempi fin qui esposti risulta chiaro che la costruzione di un programma è un processo complesso, che in generale non può essere affrontato globalmente. Si passa attraverso fasi di analisi seguite da momenti realizzativi. La soluzione finale non è mai unica, e spesso si è costretti a scegliere tra diverse possibilità. Alcune scelte fatte in precedenza potrebbero rivelarsi inopportune o addirittura errate. Allora è necessario ricominciare dal punto precedente rianalizzando la situazione. La ricerca dell'algoritmo risolutivo può mettere in evidenza errori compiuti durante la definizione del problema o durante la scelta delle strutture dati. Ed anche lo sviluppo dell'algoritmo non è mai una operazione lineare ma avviene in diversi tempi cercando di scomporre il problema in sottoproblemi più semplici. Ciascuna scomposizione deve verificare le seguenti condizioni:

1- la soluzione dei sottoproblemi deve condurre alla soluzione del problema generale

2- le azioni da eseguire per risolvere il sottoproblema devono essere possibili

3- la suddivisione deve dar luogo a sottoproblemi più semplici in base agli strumenti disponibili

Vediamole nei dettagli.

1- Non basta dire che un problema è stato scomposto per essere sicuri che si è più vicini alla soluzione. E` un'affermazione banale ma spesso si verifica che nella ricerca di un algoritmo risolutivo si scomponga il problema in sottoproblemi allontanandosi dalla soluzione. Ad esempio pensiamo al problema del massimo di un vettore. Una possibile scomposizione potrebbe essere:

ordina il vettore in ordine decrescente

il massimo è il primo elemento

Non ci si è assolutamente avvicinati alla soluzione anche perchè alcuni algoritmi di ordinamento prevedono la ricerca del massimo.

2- Anche questa affermazione è ovvia. Se scompongo un problema in sottoproblemi e per la soluzione di uno di questi debbono essere svolte azioni impossibili non abbiamo sicuramente migliorato le cose. Vediamo questo con un esempio:

In un grande cortile recintato ci sono alcuni bambini che giocano alla palla. L'accesso al cortile è permesso da una porta. Durante il gioco la palla finisce fuori dal recinto, vicino alla cancellata, dalla parte opposta rispetto alla porta. Bisogna reuperarla. Pensando di fare prima uno dei bambini risolve il problema in questo modo.

Corro verso la cancellata dove vedo la palla

Supero la cancellata

Recupero al palla e ritorno

La scomposizione del problema sembra perfetta. Ma se la cancellata non si può superare il bambino non riuscirà mai a raggiungere la palla.

3- Gli strumenti disponibili per la soluzione di un problema sono dati dal linguaggio di programmazione. Ma quello che può risultare semplice in un linguaggio potrebbe essere complicato in un altro. Oppure potrebbero esserci complicazioni facilmente risolvibili con altre scomposizioni. Anche affrontando problemi molto semplici ci si può rendere conto di questo. Ad esempio nel risolvere il problema proposto all'inizio del capitolo, dobbiamo affrontare la gestione della situazione di errore nella procedura di somma, poichè i vettori potrebbero essere di dimensione diversa. Ma con una piccola modifica nell'algoritmo iniziale si può semplificare notevolmente il problema.

BEGIN

leggi il numero n di componenti

leggi le n componenti di a

leggi le n componenti di b

leggi le n componenti di c

calcola la somma

scrivi il risultato

END.

che tradotto sarà

BEGIN

REPEAT

WRITE( 'Numero componenti vettori ' );

READLN( n );

UNTIL (n>0) AND (n<=dim);

new_leggi_vet( a, n );

new_leggi_vet( b, n );

new_leggi_vet( c, n );

new_somma_vet( a, b, c, s, n );

write_vet( r, n_r )

END.

PROCEDURE new_leggi_vet( VAR x:vettore; n:INTEGER );

VAR

i:INTEGER;

BEGIN

FOR i:=1 TO n DO BEGIN

WRITELN('Posizione = ',i);

READLN( x[i] );

END;

END;

PROCEDURE new_calcola_somma( a, b, c:vettore; VAR r:vettore; n:INTEGER );

VAR

i:INTEGER;

BEGIN

FOR i:=1 TO n DO

r[i]:=a[i]+b[i]+c[i]

END;

Il metodo di approccio allo sviluppo di algoritmi descritto è detto top-down. Ma si può seguire anche un metodo opposto che prevede di partire dal dettaglio costruendo programmi semplici, collegandoli tra loro per ottenere programmi più sofisticati sino ad ottenere il programma finale. Tale approccio è detto bottom-up. In genere nella costruzione di un nuovo algoritmo si utilizza un approccio top-down, mentre nell'adattare un algoritmo ad un nuovo problema si preferisce il metodo bottom-up. Questo significa anche che, nella prassi comune, poichè un nuovo problema una volta scomposto in sottoproblemi porta inevitabilmente ad avere analogie con problemi già risolti, il motodo di risoluzione sarà spesso inizialmente top-down ma scendendo nei dettagli diventerà bottom-up poichè si cercherà di adattare algoritmi "vecchi" alle nuove esigenze.