È possibile che un algoritmo iterativo sia più lento di uno ricorsivo?

Question

Ho fatto un paio di prove per cercare di riscrivere il mio programma in modo iterativo piuttosto che ricorsivo nella speranza di ottenere tempi minori, eppure il tempo è aumentato nonostante la logica sia la stessa...
All'inizio avevo dato la colpa alla lentezza della modifica dello stack in cui tenevo i controlli da fare, però mi sono reso conto che pur preallocando lo stack il tempo resta comunque più alto...

Ora, al di la del fatto che la ricorsione serve comunque per passare l'esercizio: è possibile che un algoritmo iterativo sia più lento di uno ricorsivo (assumendo che entrambi abbiano gli stessi identici controlli) ?

Answer 1

In Python direi proprio di no, l'iterazione dovrebbe essere sempre più veloce della ricorsione perchè quest'ultima richiede l'allocazione di uno stack frame ad ogni chiamata. Alcuni compilatori riescono a riconoscere le ricorsioni "di coda" (tail recursion), cioè quelle in cui la chiamata a se stessa della funzione compare alla fine della funzione. In questo caso il compilatore riesce ad eliminare la ricorsione in fase di compilazione sostituendola con l'equivalente forma iterativa, risparmiando quindi sulle allocazioni dello stack frame (ma non è il caso di python).

Mi viene il dubbio che la versione iterativa che hai implementato, pur svolgendo lo stesso tipo di controlli della versione ricorsiva, non interrompa in modo efficiente l'iterazione al verificarsi della prima condizione utile di uscita (è solo una supposizione, non potendo vedere il codice).

Comments

C'è un return pari pari a quello che c'è nella versione ricorsiva, il codice è praticamente lo stesso, e se trova una lettera diversa da quella che dovrebbe trovare semplicemente non aggiunge i controlli per le lettere successive allo stack.
Ho provato a fare delle stampe dei controlli in entrambe le versioni, e l'output su console coincide.

---

Anche a me l'algoritmo iterativo è più lento di quello ricorsivo.