Il fattoriale di un numero naturale e' definito dalla seguente relazione di ricorrenza:
E' relativamente semplice scrivere una funzione Pascal ricorsiva che il fattoriale di n (si tratta sostanzialmente di tradurre da "notazione matematica" a Pascal).
{AI: n>=0}
{AF: restituisce n!}
function fatt (n:integer):longint;
begin
if n=0 then fatt:=0
else fatt:=n*fatt(n-1);
end;
La funzione ricorsiva ha un inconveniente:
il numero massimo di record di attivazione presenti contemporaneamente sullo stack (complessita' computazionale in spazio) e' lineare in n. Per rendersi conto di cio', e' sufficiente disegnare l'albero delle chiamate della funzione fatt(n), ad es. per n=5.
I numeri di Fibonacci sono definiti dalla relazione di ricorrenza:
E' relativamente semplice scrivere una funzione Pascal ricorsiva che calcoli l'n-esimo numero di Fibonacci (si tratta sostanzialmente di tradurre da "notazione matematica" a Pascal).
{AI: n>=0}
{AF: restituisce l'n-esimo numero di Fibonacci}
function fib (n:integer):longint;
begin
if n=0 then fib:=0
else if n=1 then fib:=1
else fib:=fib(n-1)+fib(n-2)
end;
La funzione ricorsiva ha un inconveniente: ogni chiamata della funzione con argomento n>1 causa due successive chiamate ricorsive, ovvero: il numero totale di chiamate (complessita' computazionale in tempo) cresce esponenzialmente rispetto al valore del parametro n.
Il numero massimo di record di attivazione presenti contemporaneamente sullo stack (complessita' computazionale in spazio) e' lineare in n. Per rendersi conto di cio', e' sufficiente disegnare l'albero delle chiamate della funzione fib(n), ad es. per n=5.
{AI: n>=0}
{AF: restituisce l'n-esimo numero di Fibonacci}
{1<=i<=n+1, f=F(i), p=F(i-1)}
e quando i=n+1, p conterrra il valore cercato.
Possiamo quindi procedere con la scrittura del codice Pascal.
Per prima cosa scriviamo dello "pseudo-codice", ovvero codice Pascal in cui alcuni dettagli non sono sviluppati:
{AI: n>=0}
{AF: restituisce l'n-esimo numero di Fibonacci (F(n))}
function fib (n:integer):longint;
var
i:integer;
f,p:longint;
begin
f:=1; p:=0;
i:=1;
while i<=n do {1<=i<=n+1, f=F(i), p=F(i-1)}
begin
-- assegna F(i+1) a f, e F(i) a p
i:=i+1;
end;
end;
fib:=f;
end;
Possiamo ora raffinare lo pseudo-codice (nel fare cio' abbiamo introdotto una variable ausiliaria):
{AI: n>=0}
{AF: restituisce l'n-esimo numero di Fibonacci (F(n))}
function fibI (n:integer):longint;
var
i:integer;
f,p:longint;
aux:longint; {variabile ausiliaria}
begin
f:=1; p:=0;
i:=1;
while i<=n do {1<=i<=n+1, f=F(i), p=F(i-1)}
begin
aux:=f;
f:=f+p;
p:=aux;
i:=i+1;
end;
fib:=f;
end;
Per migliorare la leggibilita' del codice e' consigliabile rimpiazzare il "while" con un "for":
{AI: n>0}
{AF: restituisce l'n-esimo numero di Fibonacci (F(n))}
function fibI (n:integer):longint;
var
i:integer;
f,p:longint;
aux:longint; {variabile ausiliaria}
begin
f:=1; p:=0;
for i:=1 to n do {1<=i<=n+1, f=F(i), p=F(i-1)}
begin
aux:=f;
f:=f+p;
p:=aux;
end;
fib:=f;
end;
Osserviamo poi che (siccome F(n-1)=F(n)-F(n-2)) possiamo eliminare la variabile ausiliaria aux, migliorando ulteriormente la leggibilita del codice.
{AI: n>=0}
{AF: restituisce l'n-esimo numero di Fibonacci (F(n))}
function fibI (n:integer):longint;
var
i:integer;
f,p:longint;
begin
f:=1; p:=0;
for i:=1 to n do {1<=i<=n+1, f=F(i), p=F(i-1)}
begin
f:=f+p;
p:=f-p;
end;
fib:=f;
end;
La complessita' computazionale in tempo della versione iterativa e' lineare in n.
Il numero massimo di record di attivazione presenti contemporaneamente sullo stack (complessita' computazionale in spazio) e' costante.
const
MAX=100; {MAX>=2}
type
vett = array[0..MAX-1] of longint;
{AI: 1<=n<=MAX-1}
{AF: f[0..n-1] contiene i numeri di Fibonacci F(0),...,F(n-1)}
procedure fibArr (f:vett; n:integer);
var
i:integer;
begin
f[0]:=0; f[1]:=1;
for i:=2 to n-1 do {2<=i<=n, f[0..i-1] contiene F(0),...,F(i-1)}
f[i]:=f[i-1]+f[i-2];
end;