Ricorsione Vs Loops

Question

che sto cercando di fare il lavoro con gli esempi sugli alberi come dato qui: http: // cslibrary. stanford.edu/110/BinaryTrees.html Questi esempi tutto risolvere i problemi tramite la ricorsione, mi chiedo se siamo in grado di fornire una soluzione iterativa per ognuno di loro, il che significa, possiamo sempre essere sicuri che un problema che può essere risolto con la ricorsione avrà anche una soluzione iterativa, in generale. Se no, quali ad esempio possiamo dare per mostrare un problema che può essere risolto solo con la ricorsione / iterazione?

-

Answer 1

L'unica differenza tra iterazione e ricorsione su un computer è se si utilizza il built-in pila o una pila definita dall'utente. Quindi sono equivalenti.

Answer 2

Nella mia esperienza, soluzione più ricorsiva può infatti essere risolto in modo iterativo.

E 'anche una buona tecnica per avere, come soluzioni ricorsive possono avere troppo grande un overhead in memoria e CPU consumi.

Answer 3

Dato che la ricorsione utilizza uno stack implicita su cui memorizza le informazioni su ogni chiamata, si può sempre implementare quella pila da soli ed evitare le chiamate ricorsive. Quindi sì, ogni soluzione ricorsiva può essere trasformata in un iterativo.

questa domanda per una prova.

Answer 4

ricorsione e iterazione sono due strumenti che, ad un livello fondamentale, fanno la stessa cosa: eseguire un'operazione ripetuta per un insieme definito di valori. Essi sono intercambiabili in quanto non v'è alcun problema che non può, in alcuni modo, essere risolto solo uno di loro. Ciò non significa, tuttavia, che non si può essere più adatto rispetto agli altri.

Answer 5

La ricorsione ha il vantaggio dove continuerà senza una fine nota. Un perfetto esempio di questo è un sintonizzato e filettato rapida Sort.

È possibile loop non deporre le uova aggiuntivi, ma è possibile generare nuove discussioni tramite ricorsione.

Answer 6

Come un "vecchio", cado di nuovo al mio ricordo di imparando che parser discesa ricorsiva sono più facili da scrivere, ma che stack-based, parser iterativi un rendimento migliore. Ecco un articolo che sembra supportare questa idea con metriche:

http :? option = com_content //www.texttoolkit.com/index.php & view = article & catid = 35% 3Atechnology & id = 60% 3Abeyond-recursive-discesa & Itemid = 55

Una cosa da notare è menzione dell'autore di sconfinamento dello stack di chiamate con discesa ricorsiva. An, implementazione iterativa stack-based può essere molto più efficiente delle risorse.