Stavo controllando link e ho visto che sulla sua implementazione di le implementazioni ricorsive e iterative della funzione fattoriale, l'iterativo in realtà richiede più tempo dato n = 1.000. Non riesco a capire perché (non spiega, ma dice che è un esercizio per il lettore). Mi dispiace per la mia novità in tutto questo.
I due programmi non sono equivalenti. La versione ricorsiva sta calcolando
(... ((1 * 2) * 3) * 4 ... * n)
mentre quello iterativo sta calcolando
(... ((n * (n-1)) * (n-2) ... * 1)
quindi le quantità intermedie crescono più rapidamente per la versione iterativa e il calcolo numerico grande è più veloce quando i numeri coinvolti sono piccoli (Computing 1000! senza big num non ha senso e dial dial dial in big num automaticamente).
Quando si rende iterativo un algoritmo ricorsivo, è necessario implementare esplicitamente lo stack che tiene traccia dei risultati. Questo atto aggiunge operazioni extra che riguardano lo spingere e scoppiare lo stack che l'algoritmo ricorsivo ottiene gratuitamente (beh non del tutto gratis ma le operazioni extra si sommano a più del costo della ricorsione).
Posso solo indovinare, non sono nemmeno sicuro se quei benchmark provengano dalla C o dal codice SBLC. La mia ipotesi è che il colpevole stia mutando la variabile. 1000! è un numero piuttosto grande, forse è più veloce popolare lo stack con le intermittenti e pulire più che creare una copia e sovrascrivere.
Leggi altre domande sui tag lisp recursion algorithms