Ho scritto una semplice funzione di Fibonacci come esercizio in C++ (usando Visual Studio) per testare la ricorsione di coda e vedere come funziona.Ricorsione di coda C++ usando variabili a 64 bit
Questo è il codice:
int fib_tail(int n, int res, int next) {
if (n == 0) {
return res;
}
return fib_tail(n - 1, next, res + next);
}
int main()
{
fib_tail(10,0,1); //Tail Recursion works
}
quando ho compilato utilizzando la modalità di uscita ho visto il gruppo ottimizzato utilizzando l'istruzione JMP a dispetto di una chiamata. Quindi la mia conclusione è stata: la ricorsione della coda funziona. Vedi immagine qui sotto:
ho voluto fare alcuni test di performance aumentando la variabile di ingresso n nella mia funzione di Fibonacci. Ho quindi deciso di modificare il tipo di variabile, utilizzato nella funzione, da int a unsigned long long. Poi ho passato un gran numero come: 10e + 08
Questo è ora la nuova funzione:
typedef unsigned long long ULONG64;
ULONG64 fib_tail(ULONG64 n, ULONG64 res, ULONG64 next) {
if (n == 0) {
return res;
}
return fib_tail(n - 1, next, res + next);
}
int main()
{
fib_tail(10e+9,0,1); //Tail recursion does not work
}
Quando ho eseguito il codice di cui sopra ho ottenuto un'eccezione di overflow dello stack, che mi ha fatto pensare che la ricorsione in coda è stato non funziona. Ho guardato il montaggio e in effetti ho trovato questo:
Come si vede ora c'è un chiamata istruzioni mentre io aspettavo solo un semplice JMP. Non capisco il motivo per cui l'uso di una variabile da 8 byte disabilita la ricorsione della coda. Perché il compilatore non esegue un'ottimizzazione in questo caso?
Stai mirando a una piattaforma a 32 bit? –
sì, sto prendendo di mira Win32 – codingadventures
@JohnField È possibile fornire lo smontaggio della funzione VS generato con tipi lunghi lunghi? – rutsky