Quali sono i vantaggi della ricorsione rispetto all'iterazione? [duplicare]

Un esempio di iterazione è più utile della ricorsione: in un articolo di Dijkstra (la parte pertinente sono i primi due degli ultimi tre paragrafi), viene discusso un problema di teoria dei grafi. Qualcuno aveva trovato una soluzione ricorsiva e l'aveva pubblicata; e sembrava molto impressionante e difficile da capire. Dijkstra aveva lavorato con un mini-linguaggio che non aveva ricorsività, ha cercato di risolvere il problema e ha scoperto che c'era una soluzione semplice che comportava 4 stack separati che crescevano e si riducevano indipendentemente.

Un esempio di ricorsione è più utile dell'iterazione: la risoluzione del labirinto. Puoi risolvere un labirinto in modo ricorsivo procedendo ricorsivamente in ciascuna delle direzioni sinistra / avanti / destra di ogni passaggio. Mentre potresti farlo iterativamente usando una pila, sarebbe più brutto, mentre la soluzione ricorsiva è perfettamente chiara.

In generale, usa la ricorsione quando risolve il problema più chiaramente di qualsiasi alternativa ovvia.

Molte (ma non tutte) lingue usano uno stack per tenere traccia delle chiamate alle funzioni, così la ricorsione può usare tutto lo spazio e far crashare il programma - a seconda di quanti livelli in profondità la ricorsione va. Se si utilizza quel tipo di linguaggio, è possibile assicurarsi che la ricorsione non possa mai andare troppo in profondità, o ingrandire lo stack per essere abbastanza grande (se la lingua lo consente), o utilizzare un'alternativa alla ricorsione.

Nei linguaggi funzionali, la ricorsione è spesso l'impostazione predefinita e le cose che potrebbero essere espresse come loop for in altre lingue sono invece eseguite con ricorsione. Esistono modi per estrarre i pattern di iterazione di base in altre costruzioni che non sembrano né ricorsioni né loop, come le list comprehensions o le funzioni di ordine superiore che mappano e riducono (ovvero fold). Python ha una lista di comprensione, mappa e riduzione; Javascript ha una comprensione, una mappa e una riduzione degli array.

Spesso utilizzo la ricorsione quando non riesco a raggiungere l'immutabilità tramite iterazione. C'è qualcosa da dire sul tentativo di evitare l'immutabilità tutto il tempo - non è sempre l'approccio corretto, ma a volte può essere.

Facciamo un esempio banale che non mostra l'efficacia della ricorsione per cancellare la mutabilità: supponiamo che voglio programmare Conway's Game of Life, e ho due funzioni display e evolve (sto programmando questo nel kotlin per chiunque si chieda).

fun evolve(generation: Generation): Generation {
    // Create and return the next generation.
}

fun display(generation: Generation) {
    // Display the current generation.
}

Giusto abbastanza, e nel mio ruolo principale creo una generazione iniziale:

fun main(args: Array<String>) {
    val generationZero = Generation("xxx",
                                    "ooo",
                                    "xxx")
}

dove x e o rappresentano rispettivamente le cellule morte e quelle vive.

Ora voglio aggiornare e visualizzare continuamente le generazioni attuali e future:

 fun main(args: Array<String>) {
     val generationZero = Generation("xxx",
                                     "ooo",
                                     "xxx")

     var generationX = generationZero
     while (true) {
         display(generationX)
         generationX = evolve(generationX)
     }
 }

Questo è ok, e in un esempio così banale probabilmente non è un problema. Ma per motivi pratici vorrei che davvero non abbia mutabilità nel mio codice. Ho rifattorizzato il mio snippet di codice in questo:

fun runTheGameOfLife(generationX: Generation) {
    display(generationX)

    runTheGameOfLife(evolve(generationX))
}

Senza una condizione di terminazione, questo alla fine andrà in crash e brucerà, quindi potresti volerlo esaminare. Altrimenti, voilá! Ora hai un codice dolce e verificabile senza alcuna mutevolezza.

Tieni presente che non sto promuovendo l'eliminazione della tutte mutabilità- che è sciocchezza del massimo grado, ma la ricorsione può semplificare e sradicare la mutabilità dove non è necessario né sicuro. Spetta a te determinare quali posizioni del tuo codice meritano di essere modificabili.

Prima di decidere, guardiamo le somiglianze e le differenze.

Iterazione è adatto a problemi in cui esiste un numero fisso di risultati parziali. Un esempio è sommare gli elementi di una matrice; abbiamo solo bisogno di un risultato parziale - la somma calcolata finora.

Implementazione: in iterazione abbiamo un ciclo. Pensa a 4 parti:

1. Una decisione di continuare o interrompere, basata su alcuni dati "di controllo", valutata come condizione logica.
2. Un corpo, dove il lavoro è finito. A volte, il corpo viene combinato con la parte successiva.
3. Un modo per cambiare i dati di "controllo". Spesso cambiando un contatore.
4. Un modo di richiamare il costrutto (in questo caso, il ciclo) di nuovo. Nei linguaggi in stile c questo è fornito da for, while o fa la sintassi.

La ricorsione è adatta a problemi in cui non conosciamo quanti risultati parziali ci saranno. Un esempio è dove stiamo sommando gli elementi di un albero binario (che non ha collegamenti ai nodi genitore) - dobbiamo mantenere la somma calcolata finora e essere in grado di risalire l'albero. L'ascensione dell'albero (andando al genitore del nodo) viene fatta naturalmente in una soluzione ricorsiva; torniamo alla chiamata precedente. Lo stack di chiamate sta mantenendo i nostri risultati parziali per noi.

Implementazione: nella ricorsione abbiamo una funzione (a volte diverse). Hanno le stesse 4 parti:

1. Una decisione di continuare o fermarsi, basata su alcuni dati "di controllo", valutata come condizione logica. I dati di controllo vengono solitamente passati alla funzione come parametro (s).
2. Un corpo, dove il lavoro è finito. A volte, il corpo viene combinato con la parte successiva.
3. Un modo per cambiare i dati di "controllo". A volte cambiando un contatore, spesso cambiando quale nodo di una struttura dati è "corrente".
4. Un modo di invocare di nuovo il costrutto (in questo caso, la funzione) - ciò significa chiamare la funzione (e ricordare di passare i dati "controllanti" modificati).

Quindi sono molto simili. Tuttavia, una caratteristica della ricorsione è stata omessa: una funzione può restituire un valore. Ciò significa che un risultato parziale può essere restituito al chiamante. Questa è una parte fondamentale di molte soluzioni ricorsive.

Motivi per cui scegliere

1. Stile e supporto della lingua. Se lavori in un linguaggio di programmazione funzionale (come un dialetto Lisp, Haskell, Erlang, Scala, ecc.), la ricorsione è il modo naturale di partire. Se la tua lingua non supporta bene la ricorsione, puoi essere costretta a produrre una soluzione iterativa. In alcuni problemi, ciò può comportare la creazione e la gestione del proprio stack di risultati parziali.
2. Problema o struttura della soluzione. Alcuni problemi o soluzioni si inseriscono naturalmente in un'implementazione iterativa o ricorsiva. L'esempio di somma di array è un adattamento naturale per una soluzione iterativa. Ma i problemi in cui la nostra soluzione è come "trovare una parte del problema che posso risolvere, risolverlo e fare di nuovo la stessa cosa" sono una scelta naturale per una soluzione ricorsiva.
3. Prestazioni o limiti di spazio. Le soluzioni ricorsive possono consumare più spazio e tempo del processore rispetto alle soluzioni iterative. I compilatori, gli ottimizzatori e la programmazione intelligente possono aiutare, ma ci sono ancora casi in cui dobbiamo forzare una soluzione ricorsiva per essere iterativa. Finché non sappiamo di avere un problema, stiamo meglio seguendo la soluzione naturale e di facile lettura.

La ricorsione in molti casi è molto più semplice e molto più facile da capire rispetto all'iterazione. Spesso puoi risolvere un problema che normalmente richiederebbe la ricorsione di circa 50 righe di codice in sole 10 righe. Ovviamente ogni problema che può essere risolto con la ricorsione può essere risolto con l'iterazione e si può ottenere un risultato migliore, ma in molti casi è un approccio molto più brutto (se si desidera riscrivere la soluzione ricorsiva). Controlla Hanoi tower algorithm per verificare quanto può essere bello l'approccio ricorsivo. :)

La pratica. Se scegli la ricorsione o l'iterazione dovrebbe dipendere dalla natura del problema che stai cercando di risolvere.

Iterazione e ricorsione sono due tecniche per gestire collezioni di oggetti. Quale usi dipende dalla natura della collezione. L'iterazione si adatta alle collezioni flat come array e mappe hash; la ricorsione si adatta a collezioni annidate come strutture di dati dell'albero. Nota che una raccolta può essere fisica, come la struttura dei dati dell'albero, oppure può essere virtuale, come l'insieme di tutti i quadrati magici 4x4.

Per dirla in altro modo, se risolvere un problema può essere risolto risolvendo una serie di sotto-problemi dello stesso tipo, allora si consiglia la ricorsione. Se il problema può essere risolto direttamente, senza scomporlo in sotto-problemi annidati, viene richiesta l'iterazione.

A volte un problema può essere risolto in entrambi i modi. Qui, la tua scelta dipenderà dal giudizio professionale: quanto è complessa ogni soluzione? Quanto è difficile (e quindi, come incline al difetto) codificare? Quanto è efficiente l'algoritmo? Quale di questi fattori è più importante? Supponi di voler scrivere codice per ordinare gli elementi di un array. Qui ci sono due scelte per gli algoritmi:

• Ordinamento inserzione lineare è una semplice soluzione iterativa: un ciclo esterno attraversa l'array visitando ogni elemento da inserire posto; un anello interno fa scorrere quell'elemento nel punto corretto nel (crescente) sezione ordinata della lista.
• Quicksort funziona in modo ricorsivo: riorganizza gli elementi della lista per suddividerli in due sotto-liste, la prima con tutte le elementi più piccoli di un valore "pivot" e il secondo con tutti elementi più grandi del pivot (questo è un processo lineare); allora chiama se stesso una volta su ciascuno dei due sotto-elenchi per ordinarli in posizione.

L'ordinamento di inserimento lineare è semplice da programmare e convalidare, ma ha prestazioni terribili per array di grandi dimensioni. Quicksort richiede più attenzione per programmare, ma funziona bene su array di grandi dimensioni.

La teoria. La ricorsione è una tecnica più generale e più concettualmente potente dell'iterazione. La teoria alla base della ricorsione è un po 'più profonda, il che significa che ci vuole più sforzo per "dimostrare" che un algoritmo ricorsivo è corretto, rispetto a uno iterativo. Ma a causa di questa generalità, ci sono problemi che hanno soluzioni ricorsive dirette ma non hanno semplici soluzioni iterative.

Considera l'iterazione come un coltello multiuso e la ricorsione come una spada. La spada è più versatile ma richiede più abilità e sforzo per impugnare. Se hai un nodo gordiano di un problema da risolvere, la spada è l'unica cosa che farà. Tuttavia, per la maggior parte dei problemi che potresti incontrare, il programma di utilità manterrà il lavoro svolto e lo farà in modo più rapido e semplice.

La realtà. In molti anni di lavoro nel cosiddetto mondo reale (cioè non nel mondo accademico), ho visto due o tre esempi di codice che ricorre, mentre probabilmente ho visto mezzo millilione di istanze di codice che itera.