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

fc-dev (16450 points)
12 20 34
asked Dec 11, 2019 in HW8 obbligatorio by fc-dev (16,450 points)
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) ?

1 Answer

LucianoBlasetti (800 points)
2 2 6
answered Dec 12, 2019 by LucianoBlasetti (800 points)
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).
fc-dev (16450 points)
12 20 34
commented Dec 12, 2019 by fc-dev (16,450 points)
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.
a
a.pietroluongo (11250 points)
15 38 131
commented Dec 12, 2019 by a.pietroluongo (11,250 points)
Anche a me l'algoritmo iterativo è più lento di quello ricorsivo.