Newsgroup: it.comp.lang.c++
Titolo: Tail recursion

Datemi una buona ragione del perche' in C++ non e' supportata la ricorsione
tail.
Risposte del tipo: "La tail recursion e' una tecnica di programmazione non
strettamente essenziale" non verrano tenute in considerazione! :)
Roberto

strettamente essenziale" non verrano tenute in considerazione! :)
Mi pare giusto...
Pero` e` anche vero che in generale la ricorsione
viene usata poco (rispetto ai casi normali) in particolare quella di 
coda e` un po' rara.
Paolo
-----------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
-----------------------------------------------

 strettamente essenziale" non verrano tenute in considerazione! :)
Cos'è la "tail recursion"?
EMG

 tail.
E chi ti dice che non e' supportata?
Alcuni compilatori ottimizzano la tail recursion, 
altri no (lo standard non obbliga i compilatori
a ottimizzare).
Se vuoi sapere perche' alcuni compilatori non 
ottimizzano e trattano la tail recursion come una
ricorsione normale, lo devi chiedere a chi ha scritto
il compilatore (alcune ipotesi: per fare meno fatica,
tanto sono pochi a notare la differenza, ...)
Se vuoi un compilatore che ottimizza la tail recursion,
prova il gcc (free).
	Mauro

Cos'è la "tail recursion"?
Letteralmente "ricorsione di coda". In sostanza e` un caso particolare
di ricorsione in cui la chiamata ricorsiva e` fatta come ultima 
istruzione della funzione. In questo caso e` molto facile eliminare
a compile-time la chiamata ricorsiva... un po' come lo srotolamento
dei loop.


> Cos'è la "tail recursion"?
Scherzi?
--
Alessandro Monti

 Cos'è la "tail recursion"?
Per sapere cos'e' la tail recursion, devi sapere cos'e' la tail
recursion.
(Non ti sto prendendo in giro, e' solo un esempio :-)
Piu' seriamente, una procedura ricursiva e' una che richiama se'
stessa, con l'eccezione di uno o piu' "casi base" trattati a parte; il
famoso esempio del fattoriale e'
unsigned int fact(unsigned int n) {
  if (n == 0) return 1;
  return n*fact(n-1);
}
ove il caso base e' quello che corrisponde a n==0, e che interrompe la
ricursione (si dice cosi' in italiano?).  Questa e' una funzione
ricursiva, ma _non_ tail-ricursiva: queste ultime sono quelle funzioni
in cui non ci sono piu' operazioni che aspettano di essere compiute
all'atto dell'uscita da una ricursione, ma in cui viene ritornato come
valore finale quello dell'ultima ricursione (e, nell'esempio di sopra,
c'e' ancora una moltiplicazione da fare).
La stessa procedura puo' essere scritta in modo tail-ricursiva cosi':
unsigned int fact1(unsigned int n, unsigned int last) {
  if (n == 1) return last;
  return fact1(n-1, n*last);
}
unsigned int fact(unsigned int n) {
  return fact1(n, 1);
}
in cui la parte ricursiva e' stata spostata in un altra funzione
(fact1), che e' tail-ricursiva perche' restituisce a fact il valore
dell'ultima ricursione senza ulteriori operazioni, questo a spesa
dell'introduzione di una variabile in piu' (last, che in sostanza e'
il numero delle ricursioni).
A questo punto, perche' sono carine le tail-ricursioni?  Perche'
possono essere convertite in iterazioni in modo automatico, e questa
operazione puo' essere fatta di nascosto dal compilatore per eliminare
il peso dei richiami a funzione.  Infatti la forma generale e':
F(x) {
  if ( P(x) ) return G(x);
  return F( H(x) );
}
che e' equivalente a:
F(x) {
  while ( !P(x) ) {
    x = H(x);
  }
  return G(x);
}
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it

 Scherzi?
Perché, devo sapere tutto? :-)))
EMG

 Perché, devo sapere tutto? :-)))
Certo che no, ma leggendo altri tuoi post mi è sembrato che sapessi cose
(IMO) molto più complesse, per cui ho pensato fossi ironico. Sono felice di
scoprire che non sono l'unico essere umano su questo NG :-)
--
Alessandro Monti

Penso che il motivo fondamentale sia che la ricorsione in generale e la
tail recursion in particolare sono tecniche che non rivestono importanza
particolare per il C++ e quindi i produttori di compilatori non
ritengono di ottenere vantaggi di mercato nell'ottimizzarle. Questo a
differenza ad esempio del Lisp dove la tail recursion e' una tecnica
fondamentale e non sarebbe pensabile fornire un interprete non in grado
di ottimizzarla. Forse non e' un caso che l'unico esempio presentato di
compilatore che elimina la tail recursion (gcc) e' realizzato da un
gruppo che storicamente con il lisp ha avuto parecchio a che fare...
Ciao,
Nicola