Newsgroup: it.comp.lang.c++
Titolo: RICORSIONE

cos'è, a cosa serve, come si implementa e in che programmi può
ritornare convegnente.
grazie
credici
cre...@infinito.it

ritornare convegnente.
Ehm... "conveniente"...
La ricorsione e' quella caratteristica tipica delle funzioni che
richiamano se stesse.
Si adatta bene per la trattazione di strutture dati a loro volta
definibili ricorisvamente (alberi, liste, ecc...).
E' utile quando si vogliono svolgere operazioni identiche, nidificate
l'una dentro l'altra, senza conoscere, appunto, quale numero possano
raggiungere.
--
Andrea Laforgia (ICQ 87230455)

 wrote
| On Wed, 06 Sep 2000 18:45:37 GMT, 
cre...@infinito.it
 (credici) wrote:
|
| >cos'è, a cosa serve, come si implementa e in che programmi può
| >ritornare convegnente.
|
| Ehm... "conveniente"...
e lo e' solo quando viene richiamata poche volte: ciuccia la RAM che e' una
meraviglia.

meraviglia.
Gia' (lo stack per la precisione), ma a volte e' anche dovuto
all'incapacita' del programmatore di ottimizzare il passaggio di
parametri.


La ricorsione è uno strumento molto potente anche se pericoloso.
Praticamente la "ricorsione" consente ad una funzione di richiamare se
stessa.
Se in C hai una funzione tipo:
int pippo (int a)
{
    //codice della funzione...
    int pippo (a/2)
}
eventualmente la funzione pippo può usare più chiamate verso se stessa e su
diversi argomenti.
Quando una funziona chiama se stessa il controllo passa alla nuova funzione.
Quando quest'ultima finisce (per un blocco programma tipo condizione non
verificata while etc etc) il controllo passa alla funzione che ha chiamato
(la prima pippo per capirci) che riprende ad eseguire dalla riga successiva
alla chiamata di se stessa.
E' utile usare la ricorsione perchè spesso i programmi in forma ricorsiva
sono più brevi, più leggibili e meno pesanti in termini di risorse.
Purtroppo non è così semplice usarla. Pensa che linguaggi funzionali come
l'ML possono usare soltanto la ricorsione per programmare.
Se hai bisogno di altro scrivimi.
--
Roberto De Giuli
rod...@tin.it
***
Ghostbusters Italian unofficial fansite:
http://members.xoom.it/DeGiuliR/
***

l'ML possono usare soltanto la ricorsione per programmare.
Non ho capito... ;-(
Luc.

Sě, scusami, in effetti non sono stato chiaro su questo punto (spero che sul
resto sě ^_^).
L'ultimo era solo un esempio. L'ML č un linguaggio funzionale, interpretato
in genere, che non ha neppure vere e proprie variabili e la ricorsione č lo
strumento principale per programmare. Ma era solo un esempio, non ha nessun
tipo di attinenza con questo NG
ciao
--
Roberto De Giuli
rod...@tin.it
***
Ghostbusters Italian unofficial fansite:
http://members.xoom.it/DeGiuliR/
***
"Luc" <TOGL...@nip1.it-TOGLI> wrote in message
news:u77hrs0clt4jaq3o0...@4ax.com...


Un esempio di uso della ricorsione è il calcolo del fattoriale:
int fattoriale(int x)
{
 if (x==0)
      return 1;
 else
      return x*fattoriale(x-1);
}
lgiu...@komodo.ing.unico.it

meraviglia.
Vero, pero` dipende anche da come e` fatto il programma... A volte poi
non costa nulla (ricorsione di coda).
Paolo
-------------------------------------------
  Paolo Marotta
 
http://web.tiscalinet.it/paolo_marotta/
-------------------------------------------

Magari con un controllo per evitare chiamate su parametri negativi...
altrimenti non termina!   ;-)



Scusa la mia ignoranza, ma cos'è una ricorsione di coda?


Come si puņ ottimizzare il passaggio dei parametri?

>(ricorsione di coda).
Scusa l'ignoranza, ma di cosa si tratta ?
-- 
La mia chiave pubblica per PGP e GPG la trovi qua:
http://web.tiscalinet.it/paolo_bernardi/pbkey.asc

 Scusa l'ignoranza, ma di cosa si tratta ?
Molto in breve: una procedura ricursiva e' una procedura che richiama
se stessa; se la chiamata si limita a restituire un valore che viene
immediatamente utilizzato senza cambiare lo stato interno della
procedura, la ricursione si chiama tail-recursive.  E' interessante
perche' esistono dei meccanismi automatici che trasformano una
tail-recursion in un loop, quindi calcolando il risultato in modo
iterativo e con risparmio di stack e tempo di cpu.  Il fattoriale e'
un esempio.
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it


wrote:

Un caso particolare di ricorsione, quando la chiamata ricorsiva
e` l'ultima operazione della funzione.
Esempio:
long int fattoriale(long int n) {
  if (n<0) throw(10);
  if (n==0) return 1;
  return n*fattoriale(n-1);
}
In questo caso e` possibile ottimizzare eliminando di fatto la
ricorsione.
Il C++ non prevede questa ottimizzazione (che io sappia).



Lo so che sono pignolo :-), però se invece di if (x==0) scrivi if
(x==1) ti risparmi una chiamata alla funzione e il programma funziona
lo stesso.
Antonio Cuni
ICQ: 82732649

lo stesso.
So di essere anche piu' pignolo... ma il fattoriale di 0 e' definito
essere 1 e la funzione che confronta con 1 si pianterebbe in questo
caso... ;-)
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff


E' vero, ma allora bisogna anche implementare un controllo per vedere
se il numero è negativo...
Antonio Cuni
ICQ: 82732649

se il numero è negativo...
Quello sarebbe meglio ancora, ma in questo caso la funzione dovrebbe
generare una exception di dominio e non restituire un valore (se si
sta parlando del fattoriale "classico").
Alcune volte pero' e' sensato lavorare con funzioni che sono invece
autorizzate a fare casino se ricevono parametri insensati (basta che
ovviamente la cosa sia chiarita nella documentazione).
Il valore 0 per il fattoriale pero' non e' un valore fuori dominio
o una stranezza... 0!=1 e basta... e' un numero come gli altri. La
versione che fa il test con 1 non si puo' definire una funzione
fattoriale; non sarebbe molto diversa da un qualcosa come una
funzione di radice che pero' si pianta se riceve 0 come input.
Tutto si puo' documentare e il nome "fattoriale" non e' protetto
da copyright, ma mentre un fattoriale che si blocca con f(-1) non
sorprenderebbe la maggior parte degli utenti un fattoriale che
si blocca con f(0) sarebbe piu' scomodo da usare.
Molte formule di calcolo combinatorio ad esempio funzionano
correttamente nei casi limite proprio perche' 0!=1. Ad esempio:
quanti gruppi distinti di 52 carte (senza contare l'ordine) puoi
estrarre da un mazzo di 52 carte ?
     52! / (52! * (52-52)!) = 1
Hai mai provato a scrivere un programma C++ che calcoli il fattoriale
con una precisione di cifre arbitraria ? E' interessante e per
esempio farebbe scoprire che 52! (il numero di possibili diverse
"mischiate" di un mazzo di carte) e' pari a :
80658175170943878571660636856403766975289505440883277824000000000000
// Off topic mode off


lo stesso.
Non funziona, perche` 0!==1, mentre fattoriale(0) andrebbe
in loop infinito.
In effetti se si vuole essere pignoli, dovremmo verificare come prima
cosa che l'argomento non sia negativo.


// Off topic mode off
Mi arrendo!!!! :-))))
Anto