Italian community of Lazarus and Free Pascal Funzioni/procedure ricorsive
Per funzioni/procedure ricorsive si intendono
funzioni/procedure che al loro interno richiamano loro stesse. Questo
tipo di logica che viene chiamata logica ricorsiva permette un codice
più pulito e più facilmente leggibile. Prendiamo in considerazione
l'esempio principe per capire la ricorsione: il fattoriale.
{La funzione che permette la fatturazione di un numero} function Fatt(numero: integer): longint; begin if numero=1 then Fatt:=numero else Fatt:=(numero)*(Fatt(numero-1)); end;
Come si può vedere la funzione in questione si chiama Fatt e prende come parametro un numero intero. Ma se andiamo ad analizzare il codice possiamo trovare la seguente riga come anomala: Fatt:=(numero)*(Fatt(numero-1)); perché ritorniamo come valore la moltiplicazione del parametro per il risultato di una chiamata a se stessa. Cioè all'interno della funzione Fatt esiste una chiamata alla funzione Fatt. Questo modo di usare le funzioni/procedure è molto pulito e facile da interpretare, ma ad esempio rispetto ad un ciclo all'interno di una funzione occupa più spazio in memoria. Per creare delle buone funzioni/procedure ricorsive è necessario che le stesse non entrino in un ciclo infinito, per ciclo infinito si intende che non si verifica mai la condizione per uscire dal ciclo. Per esempio immaginiamo di aver dichiarato come variabile globale, quindi visibile anche all'interno di funzioni, un vettore lungo 50 celle di nome esempioric, e vogliamo sapere quante celle sono valorizzate con il numero 20; dovremmo scrivere la seguente funzione non ricorsiva:
function Conteggia20(): integer; var i: integer; cont: integer; begin cont:=0; for i:=0 to 49 do begin if (esempioric[i]=20) then begin cont:=cont+1; end; end; Conteggia20:=cont; end;
Così facendo abbiamo una funzione che cicla fino a fine vettore e ogni qual volta incontra un valore 20 all'interno del vettore incrementa di uno la variabile cont, che corrisponde al risultato che vogliamo ottenere. Ma questo non è l'unico modo per scrivere questa funzione, perché con la ricorsione possiamo ottenere:
function Conteggia20Ric(indice: integer): integer; begin if indice>=50 then Conteggia20Ric:=0 else begin if (esempioric[indice]=20) then Conteggia20Ric:=1+Conteggia20Ric(indice+1) else Conteggia20Ric:=Conteggia20Ric(indice+1); end; end;
Come si può evincere dall'esempio non esiste un ciclo all'interno della funzione stessa, ma semplicemente la funzione analizza il valore della prima cella e poi se non si trova all'ultima cella controlla tramite una chiamata a se stessa (e qui entra in gioco la ricorsione) il valore della cella successiva. C'è da notare anche una altra cosa che la seconda funzione scritta (quella ricorsiva) ha un parametro, che corrisponde alla cella del vettore che deve analizzare, quindi quando dal programma principale richiameremo la funzione bisogna passargli come parametro il valore 0. Vediamo ora l'esempio completo:
program project1;
{$mode objfpc}{$H+}
uses {$IFDEF UNIX}{$IFDEF UseCThreads} cthreads, {$ENDIF}{$ENDIF} Classes, SysUtils, CustApp { you can add units after this };
type
{ TMyApplication }
TMyApplication = class(TCustomApplication) protected procedure DoRun; override; public constructor Create(TheOwner: TComponent); override; destructor Destroy; override; procedure WriteHelp; virtual; end;
var esempioric: array[0..49] of integer; { vettore globale }
{ TMyApplication }
{ Funzione non ricorsiva che mi conta quanti 20 ci sono all'interno del mio vettore dichiarato globalmente } function Conteggia20(): integer; var i: integer; cont: integer; begin cont:=0; for i:=0 to 49 do begin if (esempioric[i]=20) then begin cont:=cont+1; end; end; Conteggia20:=cont; end; { Funzione ricorsiva che mi conta quanti 20 ci sono all'interno del mio vettore dichiarato globalmente } function Conteggia20Ric(indice: integer): integer; begin if indice>=50 then Conteggia20Ric:=0 else begin if (esempioric[indice]=20) then Conteggia20Ric:=1+Conteggia20Ric(indice+1) else Conteggia20Ric:=Conteggia20Ric(indice+1); end; end;
procedure TMyApplication.DoRun; var ErrorMsg: String; i: integer; begin // quick check parameters ErrorMsg:=CheckOptions('h','help'); if ErrorMsg<>'' then begin ShowException(Exception.Create(ErrorMsg)); Terminate; Exit; end;
// parse parameters if HasOption('h','help') then begin WriteHelp; Terminate; Exit; end;
{ add your program here }
for i:=0 to 49 do begin esempioric[i]:=i; end; esempioric[35]:=20; esempioric[36]:=20; { Nel mio vettore ho 3 valori a 20 } writeln('Con funzione non ricorsiva il risultato è: ', Conteggia20()); writeln('Con funzione ricorsiva il risultato è: ', Conteggia20Ric(0)); // stop program loop Terminate; end;
constructor TMyApplication.Create(TheOwner: TComponent); begin inherited Create(TheOwner); StopOnException:=True; end;
destructor TMyApplication.Destroy; begin inherited Destroy; end;
procedure TMyApplication.WriteHelp; begin { add your help code here } writeln('Usage: ',ExeName,' -h'); end;
var Application: TMyApplication;
{$IFDEF WINDOWS}{$R project1.rc}{$ENDIF}
begin Application:=TMyApplication.Create(nil); Application.Title:='My Application'; Application.Run; Application.Free; end.
Navigazione [0] PROGRAMMATORE ALZATI E CAMMINA CON LAZARUS [#] Forum |