|
Linguaggio Pascal |
||
|
per collaborazioni, commenti, critiche, e altro contattateci alla e-mail: clubinfo@libero.it risponderemo al più presto! |
||
Quinta lezione
11.1 Funzioni
11.2 Procedure
11.3 Esempi
12 Ricorsione
Pagina principale | Lezione precedente | Prossima lezione
L'uomo, nel suo normale modo di agire, dopo
aver analizzato il problema in generale, individua i sottoproblemi e li affronta
uno per volta, fino alla loro completa risoluzione.
Per seguire questo tipo di logica, si rende necessario uno strumento che, da un
certo punto in poi, ci permetta di "sganciarci" dal contesto generale
per sviluppare separatamente, e in modo il più possibile indipendente, i
singoli nodi di difficoltà.
A tale scopo suddivideremo l'intero programma in:
programma principale;
sottoprogrammi.
A sua volta, il Pascal, permette di suddividere i sottoprogrammi in:
funzioni (function);
procedure (procedure).
Per quanto riguarda la struttura di questo corso, continueremo per ora a considerare il programma come l'insieme di programma principale + sottoprogrammi. In una fase successiva si procederà nell'analisi dl sottoprogramma specifico, considerandolo come un programma a sé stante.
In matematica, una funzione è una legge che, in base ai valori
assunti da uno o più argomenti, fornisce uno ed un solo risultato (valore della
funzione).
Ad esempio nella relazione:
f(x) = 3x + 2
f è il nome della funzione e x è l'argomento.
Notiamo che nella relazione, all'argomento x non è associato alcun
valore specifico; x è quindi un parametro formale, usato
per definire la regola per il calcolo della funzione. Per effettuare il calcolo
di f, occorre pertanto associare a x un preciso valore (valore
attuale).
Ad esempio assegnando a x il valore 3 si ottiene:
f(3) = 11
Lo schema generale di un programma che prevede la definizione di funzioni è il seguente:
program nome_programma;
var ...
...
function nome_funzione(param1,
param2, ...): tipo_del_risultato;
var...
...
begin
...
corpo della
funzione
...
end;
begin
...
corpo del programma contenente la
chiamata della funzione
...
end.
Analizziamo le varie parti:
nome_funzione rappresenta il nome associato alla funzione;
param1, param2, ... sono la descrizione dei parametri formali espresse attraverso nome e tipo;
tipo_del_risultato è il tipo del valore associato alla funzione.
La parte dichiarativa (all'interno della funzione), contiene la definizione di tutte le variabili usate all'interno della funzione, fatta eccezione per quelle già definite come parametri formali. Sulla cosiddetta visibilità (in inglese scope) torneremo dopo con alcuni esempi.
All'interno del corpo del programma principale, deve essere presente la chiamata della funzione, attraverso il suo nome seguito dalla lista dei parametri attuali, che devono essere nello stesso ordine (della dichiarazione) e dello stesso tipo.
La procedura, così come la funzione, permette di isolare e di risolvere separatamente alcune parti del problema generale.
Una procedura viene invocata attraverso il suo nome, ma ad essa
non viene associato alcun valore. Come nelle funzioni, il dialogo tra programma
chiamante e procedura, avviene attraverso una lista di parametri.
Nel caso di procedure, la lista di parametri riveste un ruolo fondamentale, in
quanto attraverso questa, è possibile lo scambio di più valori. Entriamo con
maggiore dettaglio in questo meccanismo:
Come già detto, all'atto della chiamata della procedura, i parametri attuali prendono il posto dei parametri formali. Questa sostituzione può avvenire in due modi:
per valore
per riferimento
Nel passaggio per valore, il valore del parametro attuale (ad
esempio x) viene passato al parametro formale (ad esempio y). La
procedura quindi lavorando con y, non può in alcun modo modificare x.
Nel passaggio per riferimento, qualsiasi operazione effettuata su y si
ripercuote su x, in quanto viene effettuato un legame tra i due
parametri.
Ecco che, se vogliamo avere un output anche dalla procedura,
basterà passare i parametri per riferimento.
Ma come si fa ad indicare questo diverso approccio in Pascal?
Per attivare il passaggio per riferimento, sarà sufficiente far precedere la lista dei parametri dalla parola chiave var.
procedure nome_procedura(param1,
param2, ...
var param10, param11,... );
Lo schema generale di un programma che prevede la definizione di procedure è il seguente:
program nome_programma;
var ...
...
procedure nome_procedura(param1,
param2, ...
var param10, param11,... );
var...
...
begin
...
corpo della
procedura
...
end;
begin
...
corpo del programma contenente la
chiamata della procedura
...
end.
Ecco un esempio di scope delle variabili:
program visibilita;
uses crt;
var x : integer;
procedure nasconde;
var x: integer;
begin
writeln('procedura
"nasconde", prima dell"assegnamento x = ',x);
x:= 10;
writeln('procedura
"nasconde", dopo l"assegnamento x = ',x);
end;
procedure non_nasconde;
begin
writeln('"non_nasconde", prima x = ',x);
x:= 100;
writeln('procedura"non_nasconde",
dopo x = ',x);
end;
begin
clrscr;
writeln('programma principale, prima x = ',x);
x:= 1;
writeln('programma principale, dopo x = ',x);
nasconde;
non_nasconde;
repeat until keypressed;
end.
L'output di questo codice è del tipo:
programma principale,
prima x = 0
programma principale, dopo x = 1
procedura "nasconde", prima dell"assegnamento x =
23415
procedura "nasconde", dopo l"assegnamento x =
10
procedura "non_nasconde", prima dell"assegnamento x = 1
procedura "non_nasconde", dopo l"assegnamento x = 100
Il commento di questi risultati è piuttosto
semplice:
La prima cosa da far notare è che la variabile x all'interno del
programma principale e la x della procedura "non_nasconde" sono
la stessa, contrariamente alla x della procedura "nasconde",
che è proprio un'altra variabile.
Un'altra cosa da far notare è che i valori di x prima dell'assegnamento nel
programma principale e nella procedura "nasconde", sono valori casuali
che corrispondono al contenuto della locazione di memoria in cui sono state
allocate le variabili. Proprio questo è il motivo dell'importanza di resettare
le variabili prima del loro uso.
Osservazione: All'interno del nome della procedura non_nasconde è presente il carattere "_" (leggi underscore) perché nel nome (di variabile, di procedura, di funzione, di programma, ...) non possono essere presenti degli spazi.
Una funzione al cui interno è presente una chiamata a se stessa è detta
ricorsiva.
Un tipico esempio di funzione ricorsiva è quella usata per
calcolare il fattoriale di un intero positivo:
function fattoriale(n: integer): integer;
begin
if n = 1 then
fattoriale := 1
else
fattoriale := n * fattoriale(n-1);
end;
Il fattoriale di un numero n è il prodotto dei primi n numeri interi, ad esempio il fattoriale di 4 (che si indica con 4!) è: 1 * 2 * 3 * 4 = 24
Nella funzione fattoriale abbiamo due casi: il fattoriale di 1 è 1. Per gli altri numeri si sfrutta la proprietà che !n = n * (n-1)!
Attenzione: la condizione n = 1 si chiama "base di ricorsione" e rappresenta la condizione di uscita. Questa garantisce che il processo di ricorsione abbia una fine.
Come già visto nell'esempio della terza lezione (in cui abbiamo calcolato il fattoriale con il ciclo for), tutti i risultati ottenuti mediante funzioni ricorsive possono essere ottenuti mediante funzioni non ricorsive, che in genere sono molto più complesse. Il vantaggio di usare la ricorsione è che determinati problemi trovano in essa una soluzione elegante, chiara e semplice. Vedremo ad esempio per le liste, gli alberi e le strutture dinamiche in genere come questa affermazione sia veritiera. Tuttavia la ricorsività non è una manna. Una funzione ricorsiva è un'arma a doppio taglio. Se infatti una funzione ricorsiva è costruita male mostrerà subito i suoi limiti. In genere il problema connesso con la ricorsività è la facilità con cui il processo termina la memoria del computer, per quanto grande essa sia.
Per chiarire questo concetto vediamo come viene gestita una chiamata di funzione ricorsiva. Introduciamo brevemente il concetto di stack o pila. Uno stack è una zona di memoria del computer in cui vengono memorizzati dei dati, uno sopra l'altro, proprio come se fosse una pila di libri. Finché c'è spazio si può aggiungere un libro, ma se il libro viene ricoperto, bisogna aspettare di prendere tutti i libri che stanno sopra prima di prendere quello.
Supponiamo che il libro giallo sia il dato che ci interessa. Lo poniamo nello stack. Questo viene ricoperto da altri dati; prima di prelevarlo dobbiamo essere sicuri che i libri aggiunti siano stati tolti.
Ma a che serve? Quando in Pascal viene richiamata una funzione si fa ricorso allo
stack. Supponiamo che il processore stia eseguendo le istruzioni di una
funzione. Si dice che il sistema si trova in un determinato contesto, con certe
variabili che assumono certi valori. Adesso però il processore incontra una
chiamata di funzione. Tutti i dati e le variabili attuali temporaneamente non
servono più perché come sappiamo ogni funzione ha il suo ambiente locale.
Tuttavia non devono essere dimenticate perché quando la funzione terminerà
dovranno essere ripristinati. Quindi immaginiamo di impacchettare queste
variabili e di metterle nello stack (nel quadretto giallo, figura 2).
Nella
funzione invocata ci sono nuove variabili e nuovi valori per queste. Supponiamo
che anche qui ci sia una chiamata ad una terza funzione. Allora per una seconda
volta tutte le variabili locali vengono impacchettate e messe nello stack
(figura 3). Quando la terza funzione termina, dallo stack vengono prelevate le
variabili "congelate" che vengono ripristinate come se nulla fosse successo
(figura 4). Lo stesso avviene quando anche la seconda funzione termina: si
ripristina dallo stack le variabili relative all'ambiente iniziale (figura
5).
Questa introduzione ci è servita per spiegare che ogni chiamata di funzione genera una certa occupazione di memoria nello stack. Quando la funzione termina questa memoria viene liberata.
Analizziamo questa funzione ricorsiva
function ricorsione;
begin
ricorsione;
end
essa richiama se stessa, e poi se stessa e così via all'infinito. Non esiste
alcuna possibilità che essa termini. Dal punto di vista pratico invece essa
termina presto, ma con un bel segnale di errore di esaurimento della
memoria.
Infatti ad ogni successiva invocazione viene allocato dello spazio
nello stack, il quale non viene mai rilasciato. Anche il computer più dotato di
memoria terminerà in pochi secondi tutta la memoria a sua disposizione,
impedendo il proseguo delle operazioni.
A. Garavaglia, Petracchi "Laboratorio di Informatica", MASSON
Questo articolo è stato scaricato dal Club di informatica |