Newsgroup: it.comp.lang.pascal
Titolo: Funzioni ricorsive

Salve ragazzi, qualcuno mi saprebbe indicare una guida, dove si parli delle
funzioni ricorsive in Pascal? Visto che mi rimane ancora difficile capire
questo concetto :-(


Non so dove si possa trovare una guida ma visto che non ti ha ancora
risposto nessuno ( Dreadnaut che si fa sfugira un messagio che gli e
successo? ) provero io.
Una funzione ricorsiva e formata sostanzialmente da 2 pari. Il caso
base e quello ricorsivo ( facciamo un esempio vah )
Function Fat ( N : Byte ) : Longint;
Begin
  { sai cosa è un fattoriale? spero di si :D  cmq è un operatore ( ! )
    che prende il dato ( N ) e lo sottre ( N-1 ) e moltiplica finche
     N non diventa 1 ( che schifo di spiegazione ) ovvero 
    N! =  N*(N-1)*(N-2)*(N-3)*.....*4*3*2*1. Da notare che si puo'  
    fare N! =  N*(N-1)! questo ci serivira dopo ma  come ho detto ci 
    vuole un caso base ovvero la condizione di uscita
   e in questo caso è evidente che è N = 1 percui basta fare
 }
  if ( N = 1 )
   then Fat := N { va bene anche 1 ma N è + bello :D }
{ il caso ricorsivo e anche molto ( non a caso ho scelto il fattoriale
)  ed e proprio la proprieta dei fattoriali )
  else Fat := N * Fat ( N -  1 );
End;
ecco finito. (PS ho messo Byte per una precisa ragione ossia 
$FF! = 3,3508506849329791176526651237548e+504
che è ben oltre il "misero" longint ma questo è un altro discorso )
le funzioni ricorsive si prestano bene alle funzioni  matematiche (
come hai visto ) perke in pratica sono gia scritte ( :D ) ma c'è ne
sono anche altre ma apparte a quelle che si "prestano" tutte le
funzioni iterative possono essere fatte ricorsivamente ( come tutte le
funzioni ricorsive fatte iteratamente )
io non sono un fan delle funzioni ricorsive ( ok Dreadnaut lo è di
meno :D ) ma avolte sono comode fanno risparmiare parecchio lavoro
visto che alcune cose te lo chiedono in ginochio "Fammi in modo
ricorsivo" ma bisogna sempre tenre d'occhio il povero stack ogni
chiamata ricorsiva lascia nel sudetto stack un sacco di sporcizie (
esempio il punto di ritorno ) ora pensando che un punto di ritorno
occupa 2 e ogni paramento almeno 2 beh non ecedere troppo :D
Il Razziatore,
The Only Good Windows is an uninstalled Windows
-----------------------------------------------
E-MAILs : IlRazziat...@NOSPAMnetscape.net
ICQ     : 67552596
-----------------------------------------------
Founder of MediaPlayer Project
http://mpp.iwebland.com


beh guarda, abbiamo gia affrontato il discorso su questo newsgroup non
moltissimo tempo fa (e visto il numero di messaggi qui sopra dovrebbe essere
ancora accessibile il thread).
Ma ti riassumerò in breve:
un problema è ricorsivo quando è scomponibile in modo che per essere risolto
si possa applicare un procedimento tale che per essere portato a termine
richiami se stesso per risolvere un problema analogo di ordine inferiore.
Faccio un esempio per rendere al meglio questo concetto un po criptico:
l'elevamento a potenza.
2^0 = 1
2^1 = 2
2^2 = 2*2
2^3 = 2*2*2
2^4 = 2*2*2*2
ecc.
da sopra notiamo ad esempio che 2^4 = 2 * 2^3
2^3 = 2 * 2^2
2^2 = 2 * 2^1
2^1 = 2 * 2^0
2^0 = 1
se sostituiamo troviamo che 2^4 = 2 * 2 * 2 * 2 * 1 che è proprio 2^4.
Risolvendo la potenza in questo modo abbiamo pertanto che facciamo un
prodotto tra la base e la medesima potenza di ordine inferiore.
L'unico caso certo, che è poi ciò che fa terminare il nostro procedimento, è
l'esponente a 0 che in ogni caso da 1.
Abbiamo pertanto risolto l'elevamento a potenza in maniera ricorsiva. Ma
passiamo alla definizione formale:
 b^e = b * b^(e-1)    se e>0
 b^e = 1                    se e=0
e=0 sarà la nostra "condizione di uscita" ovvero quella condizione che causa
la terminazione del programma poiché l'eventualità che la rende vera ha due
fondamentali caratteristiche:
 a) si verificherà sicuramente a un certo punto dell'elaborazione
 b) il risultato è immediatamente correlabile ai parametri
a questo punto possiamo passare a codificarla in Pascal:
Procedure potenza(base:real; esponente:integer):real;
Begin
   If e=0 then potenza:=1
             else potenza:=potenza(base, esponente-1)
end;
come possiamo vedere il programma chiama se stesso un certo numero di volte
che dipende dai parametri, ad ogni successiva chiamata si dice che si apre
una nuova "istanza" della procedura. Tuttavia i parametri assumono un valore
differente per ciascuna istanza fino ad arrivare al momento in cui esponente
vale 0. Tale istanza terminerà immediatamente restituendo 1 che ai fini del
reiterato (o forse dovrei dire reistanziato) prodotto delle istanze
precedenti costituisce neutralità nel risultato. Scritta così è "ricorsiva
in coda" poiché l'istanza viene aperta come ultima operazione.
Avremmo potuto scriverla "ricorsiva in testa" così:
Procedure potenza(base:real; esponente:integer):real;
Begin
   If e>0 then potenza:=potenza(base, esponente-1)
             else potenza:=1
end;
in tal caso prima si apre l'istanza poi termina la procedura.
Intanto prova a digerire questa spiegazione, poi magari passiamo ad un
esempio più complesso ma forse prima avrai qualche domanda da fare.
a presto
Fabio

Pavel Checov wrote:
[cut]
chiaramente era una Function, non un Procedure, perdonatemi la svista