Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Guida Pascal - Appendice 11 La ricorsione

Guida Pascal

Capitolo 30° - Appendice 11 La ricorsione

<< Precedente Prossimo >>
La ricorsione è un particolare modo di usare procedure e funzioni, ed è utilizzata spesso per colcoli matematici complessi. Consiste nel richiamare, nel corpo di una procedure/funzione, la stessa procedure/funzione di cui si sta scrivendo il corpo.
Un esempio: il calcolo del fattoriale. Un numero intero positivo n di cui si voglia calcolare il fattoriale n! consiste nel moltiplicare ogni numero da 1 ad n: 1*2*3*4*5*...*(n-1)*n.
3!=1*2*3=6
4!=1*2*3*4=24

Program fatt;
uses crt;
var x:integer;

function Fattoriale(x:integer):longint;
begin
    if x=1 then
      Fattoriale:=1
    else
      Fattoriale:=x*Fattoriale(x-1);
end;

begin
    clrscr;
    write('Inserire un numero: ');
    readln(x);
    write('Il fattoriale di ',x,' è ',Fattoriale(x));
    readln
end.


Prima della spiegazione, è da notare che nei parametri di write e writeln si possono scrivere non solo stringhe e variabili, ma anche funzioni, in quanto quello che andrà scritto sarà un dato dello stesso tipo della funzione, quindi compatibile con i tipi di write e writeln.
Allora, la funzione Fattoriale, richiama sè stessa, in modo che ogni volta venga calcolato il fattoriale del numero precedente, tranne che nel caso in cui il parametro sia uno (ed in questo caso, ne siamo sicuri, il risultato sarà uno).
Il procedimento logico, supponendo che x immesso da tastiera sia 6 è:

x=6 immesso da tastiera:
Fattoriale(6)=6*Fattoriale(5) ma quant'è Fattoriale(5)?
Fattoriale(5)=5*Fattoriale(4) ma quant'è Fattoriale(4)?
Fattoriale(4)=4*Fattoriale(3) ma quant'è Fattoriale(3)?
Fattoriale(3)=3*Fattoriale(2) ma quant'è Fattoriale(2)?
Fattoriale(2)=2*Fattoriale(1) ma quant'è Fattoriale(1)?
Fattoriale(1)=1
Fattoriale(2)=2*1
Fattoriale(3)=3*(2*1)
Fattoriale(4)=4*(3*2*1)
Fattoriale(5)=5*(4*3*2*1)
Fattoriale(6)=6*(5*4*3*2*1)=720


La funzione entra sempre dentro ad un'altra isatanza di sè stessa, fino ad arrivare al caso in cui il risultato non dipenda dalla funzione, ma è dato, caso, che, in questa situazione, corrisponde a parametro=1. Una volta trovato il risultato certo, 'risale' per tutte le altre funzioni, dandoci il risultato finale.
In sostanza, è come una scatola cinese (non in senso matematico): prima ci si addentra nel centro, per trovare il dato certo, che non dipende da niente, poi, si risale attraverso tutte le istanze della funzione, arricchendo ogni volta il risultato, fino ad arrivare alla fine.
Questo procedimento è chiamato ricorsione.
<< Precedente Prossimo >>
A proposito dell'autore

Programmatore e analista .NET 2005/2008/2010 (in particolare C# e VB.NET), anche nell'implementazione Mono per Linux. Conoscenze approfondite di Pascal, PHP, XML, HTML 4.01/5, CSS 2.1/3, Javascript (e jQuery). Conoscenze buone di C, LUA, GML, Ruby, XNA, AJAX e Assembly 68000. Competenze basilari di C++, SQL, Hlsl, Java.