Newsgroup: it.comp.programmare
Titolo: Ricorsione ed iterazione

Allora: tralasciando i problemi di memoria cui puň andare in contro una 
funzione ricorsiva, questi č piů, meno o ugualmente efficiente come la 
sua controparte iterativa?
Saluti
-- 
Per l'e-mail rimuovere le maiuscole e gli underscore

 sua controparte iterativa?
Non c'č dubbio che una soluzione iterativa sia
piů veloce (e meno affamata di memoria) di una
ricorsiva: infatti la ricorsione si usa quando
*non si puň* usare l'iterazione.
Per esempio negli analizzatori sintattici dei
compilatori o nella derivazione simbolica, dove
per analizzare i termini e le istruzioni (tutti
diversi fra loro) si usano funzioni che chiamano
ricorsivamente se stesse.
In questo caso una soluzione iterativa sarebbe
forse possibile, ma infinitamente piů complessa
da scrivere e molto piů soggetta a contenere
errori. E inoltre non credo che sarebbe poi molto
piů efficiente: il vantaggio dell'iterazione č
il ripetere lo stesso codice esattamente N volte,
ma se il codice NON si ripete e non sai nemmeno
quant'č N allora sei obbligato a mettere una
serie di test (da eseguire a ogni passo) che
ti fanno perdere parecchio tempo.

 sua controparte iterativa?
In linea teorica qualunque funzione ricorsiva puo' essere trasformata in un
funzione iterativa. Il prezzo da pagare è doversi gestire esplicitamente uno
stack sul quale mettere tutte le informazioni che calcoli al passo k ma che
potrai utilizzare solo quando la ricorsione termina. Se lasci la funzione
definita ricorsivamente usi lo stack dei record di attivazione della
funzione ma il meccanismo è lo stesso.
Naturalmente ci sono dei casi particolari in cui si trova una soluzione
iterativa alternativa a quella ricorsiva o in cui lo stack puo' essere
sostituito con qualcos'altro (ad esempio nel fattoriale si sfrutta la
proprietà associativa della moltiplicazione tra interi per farne a meno).
Credo che dire in generale quale delle due funzioni sia piu' efficente (in
termini di velocità o di occupazione di memoria) dipenda dalla natura della
funzione stessa.
Se hai una buona implementazione degli stack, hai molte variabili locali e
parametri ma la ricorsione si basa solo su poche variabili, forse puoi
guadagnare qualcosa in velocità trasformando la funzione da ricorsiva ad
iterativa.
L'unico pericolo è che la funzione diventi incomprensibile. Ci sono molti
problemi (ad esempio il parsing di linguaggi) che hanno delle soluzioni che
sono "naturalmente" ricorsive e sono molto piu' semplici da programmare,
testare e modificare rispetto ad una soluzione "forzatamente" iterativa che
ti costringa a giocare con uno o piu' stack contemporaneamente.

 iterativa.
Sui processori moderni comunque una chiamata di procedura è sicuramente +
complessa da gestire che un ciclo, pertanto facilmente una funzione
iterativa riuscirà ad essere ottimizzata dal processore (migliore utilizzo
delle pipelines), mentre che io sappia le chiamate di procedura non sono
ottimizzate + di tanto (a parte magari il fatto che la funzione ricorsiva
potrebbe starci tutta nella cache e quella iterativa no).
Pertanto direi che a parità di condizioni quella iterativa potrebbe "girare"
parecchio più velocemente. Il discorso però della più o meno facile
implementazione a seconda del problema rimane ed è validissimo.
Ciao
Alessandro
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

Grazie a tutti, siete stati esaurienti.
