[C] Ricorsione Tail / Non tail domanda su una funzione

[Maxcorrads]

Salve,
la seguente funziona ricorsiva è di tipo Tail o non tail?

Grazie mille.


int fun(int m, int n, int p)
{
if (m - n < p) return p;
else return fun(2,1,10) + fun(m,m+n,p);
}

[lupoxxx87]

Originariamente inviato da Maxcorrads

Salve,
la seguente funziona ricorsiva è di tipo Tail o non tail?

Grazie mille.


int fun(int m, int n, int p)
{
if (m - n < p) return p;
else return fun(2,1,10) + fun(m,m+n,p);
}

è non tail, in quanto fun(2,1,10) ha sempre lo stesso valore (ndr. 10) e quindi la puoi considerare come un parametro invece che come una inutile ricorsione spreca risorse.

[Maxcorrads]

Grazie per la risposta lampo, ne approfitto per chiedere la stessa cosa anche per questa funzione, che mi risulta essere Tail, mi potreste spiegare perchè?

int fun(int m, int n, int p)
{
if (m - n < p) return m+n;
else return fun(m,m+n,p) + fun(7,1,9);
}

[lupoxxx87]

se questa è tail, allora lo è anche quella di prima...

o lo sono entrambe o non lo è nessuna, visto che sono uguali...
comunque non-tail è una funzione che restituisce

return fun(m,m+n,p) + fun(7,1,9);

una chiamata a se stessa e un fattore...
forse avendo in questi due esempi delle somme non si può parlare di fattori ma di addendi, e quindi risultano essere tail entrambe... (in effetti il ragionamento ha senso)

se invece fosse stato così

return fun(m,m+n,p) * fun(7,1,9);

sarebbe stata non tail

[Maxcorrads]

Mmh ho il tuo stesso dubbio anche io, la questione è questa, le seguenti funzioni erano in un test di Fondamenti di Info. B all'università che ho svolto oggi, purtroppo non riesco a capire come mai una sia TAIL e l'altra no, in quanto il prof. mi ha detto che la prima è Non tail e la seconda si, purtroppo per motivi di tempo non sono riuscito a chiedere altro e con le vacanze di pasqua in mezzo volevo togliermi il dubbio fin da subito.

Grazie per la risposta.

[lupoxxx87]

bah...se i testi delle due funzioni sono giusti, non possono appartenere a due categorie diverse...

sia il DUA che la copertura delle condizioni è identica

[Maxcorrads]

Si i testi sono corretti, ho copiato direttamente dal PDF, comunque a questo punto resta valida l'ultima ipotesi si sarà confuso.
In tal caso molto bene, in quanto io ho scritto che è Tail, vedremo,

[DanieleC88]

Sarà... secondo me non sono tail recursive, poi forse sono scemo io.

[Maxcorrads]

Originariamente inviato da DanieleC88

Sarà... secondo me non sono tail recursive, poi forse sono scemo io.

No no non sei tu ad essere scemo, vorrei solo capire perchè è non tail o tail.

[lupoxxx87]

non-tail è una funzione che restituisce una chiamata a se stessa e un fattore...

[DanieleC88]

Originariamente inviato da lupoxxx87

non-tail è una funzione che restituisce una chiamata a se stessa e un fattore...

In generale ( http://en.wikipedia.org/wiki/Tail_recursion ) si tratta di una routine che come ultima cosa chiama se stessa. L'ideale sarebbe che chiami una sola volta se stessa come unica operazione finale: in questo modo il record d'attivazione della routine allocato sullo stack può essere riutilizzato per la prossima invocazione.