Funzione Ricorsiva dubbio

[volpi92]

Salve a tutti,

ho la seguente funzione ricorsiva:

int fun(int m, int n)
{
int h;

h = m++;

if (m + n > 8) return m+h;

else return fun(3*m,n-1) - fun(m,3*n);
}

devo capire se è tail ricorsiva o no e motivare la risposta.

come posso procedere??? l'esame è domani e spero di chiarite il dubbio entro domani :)

(perchè io so che se il ritorno alla funzione stessa è preceduta da qualche operazione allora è non tail ricorsiva altrimenti se il return alla funzione stessa è sola allora è tail...) giusto???

grazie

[wingman87]

Puoi vedere wikipedia per una descrizione della ricorsione di coda e l'eliminazione. Non è fatto benissimo, però mi sembra che si capisca.
http://it.wikipedia.org/wiki/Algoritmo_ricorsivo#Ricorsione_in_coda

Le funzioni che hai postato non sono tail recursive perché le chiamate ricorsive non sono l'ultima istruzione: l'ultima istruzione è la differenza tra i risultati delle due chiamate.

Correggetemi se sbaglio... sono di fretta e non ci ho riflettuto abbastanza da essere sicuro al 100%

[banryu79]

Sono d'accordo con wingman87, quella funzione non è tail-recursive.
Il motivo l'ha ben spiegato wingman87.
Dato che l'ultima operazione della funzione non è la chiamata ricorsiva a se stessa, ma l'operazione di sottrazione tra i risultati prodotti dalla due chiamate ricorsive, la funzione non è tail-recursive.

I primi due paragrafi di questa pagina spiegano bene la cosa, anche se è in inglese: https://en.wikipedia.org/wiki/Tail_recursion