Qual è una differenza pratica tra un loop e la ricorsione

Question

Attualmente sto lavorando in PHP, quindi questo esempio sarà in PHP, ma la domanda si applica a più lingue.

Sto lavorando a questo progetto con un mio demone, e come sempre siamo stati ostacolati da un grosso problema. Ora siamo andati entrambi a casa, non siamo riusciti a risolvere il problema. Quella sera entrambi abbiamo trovato la soluzione, solo che ho usato un ciclo per affrontare il problema, e ha usato la ricorsione.

Ora volevo dirgli la differenza tra il ciclo e la ricorsione, ma non sono riuscito a trovare una soluzione in cui è necessario ricorrere su un ciclo normale.

Sto per fare una versione semplificata di entrambi, spero che qualcuno possa spiegare come uno è diverso dall'altro.

prego di perdonarmi per eventuali errori di codifica

Il loop:

printnumbers(1,10); 

public function printnumbers($start,$stop) 
{ 
    for($i=$start;$i<=$stop;$i++) 
    { 
     echo $i; 
    } 
} 

Ora il codice di cui sopra semplicemente stampa i numeri.

Ora facciamo questo con la ricorsione:

printnumbers(1,10); 

public function printnumbers($start,$stop) 
{ 
    $i = $start; 
    if($i <= $stop) 
    { 
     echo $i; 
     printnumbers($start+1,$stop); 
    } 
} 

Questo metodo di cui sopra farà la stessa cosa come il ciclo, ma poi solo con la ricorsione.

Qualcuno può spiegarmi cosa c'è di diverso nell'usare uno di questi metodi.

Answer 1

I loop e le ricorsioni sono in molti modi equivalenti. Non ci sono programmi che richiedono l'uno o l'altro, in linea di principio si può sempre tradurre da loop a ricorsione o viceversa.

Le ricorsioni sono più potenti nel senso che tradurre la ricorsione in un ciclo potrebbe richiedere uno stack da manipolare. (Prova ad attraversare un albero binario usando un loop e sentirai il dolore.)

D'altra parte, molte lingue (e implementazioni), ad es. Java, non implementano correttamente la ricorsione della coda. La ricorsione della coda è quando l'ultima cosa che fai in una funzione è chiamarti (come nel tuo esempio). Questo tipo di ricorsione non deve consumare alcuno stack, ma in molte lingue lo fanno, il che significa che non è sempre possibile ricorrere alla ricorsione.

Answer 2

Rispetto ai cicli, una chiamata di funzione ha il proprio overhead come allocare stack ecc. E nella maggior parte dei casi, i loop sono più comprensibili rispetto alle controparti ricorsive.

Inoltre, si finirà per utilizzare più memoria e si può anche esaurire lo spazio di stack se la differenza tra avvio e arresto è elevata e ci sono troppe istanze di questo codice in esecuzione contemporaneamente (il che può accadere quando si ottiene più traffico).

Answer 3

Bene, non conosco PHP ma la maggior parte delle lingue genera una chiamata di funzione (a livello macchina) per ogni ricorsione. Quindi hanno il potenziale per utilizzare un sacco di spazio nello stack, a meno che il compilatore non produca ottimizzazioni tail-call (se il tuo codice lo consente). I loop sono più "efficienti" in questo senso perché non aumentano lo stack. La ricorsione ha il vantaggio di essere in grado di esprimere alcuni compiti in modo più naturale però.

In questo caso specifico, da un punto di vista concettuale (piuttosto che implementativo), le due soluzioni sono totalmente equivalenti.

Answer 4

In generale, una funzione ricorsiva consumerà più spazio nello stack (poiché è in realtà un ampio insieme di chiamate di funzione), mentre una soluzione iterativa non lo farà. Ciò significa anche che una soluzione iterativa, in generale, sarà più veloce perché.

Non sono sicuro che se questo si applica a un linguaggio interpretato come PHP, è possibile che l'interprete possa gestirlo meglio.

Answer 5

Un ciclo sarà più veloce perché c'è sempre un sovraccarico nell'esecuzione di una chiamata di funzione extra.

Un problema con l'apprendimento della ricorsione è che molti degli esempi forniti (diciamo, fattoriali) sono esempi negativi di utilizzo della ricorsione.

Ove possibile, seguire un ciclo a meno che non sia necessario fare qualcosa di diverso. Un buon esempio di utilizzo della ricorsione è il loop su ciascun nodo in una struttura con più livelli di nodi figlio.

Answer 6

La ricorsione è un po 'più lenta (perché le chiamate di funzione sono più lente rispetto all'impostazione di una variabile) e utilizza più spazio nella maggior parte degli stack di chiamate delle lingue. Se si è provato a printnumbers(1, 1000000000), la versione ricorsiva potrebbe generare un errore fatale PHP o addirittura un errore 500.

Ci sono alcuni casi in cui la ricorsione ha senso, come fare qualcosa per ogni parte di un albero (ottenere tutti i file in una directory e le sue sottodirectory, o magari fare scherzi con un documento XML), ma ha il suo prezzo - in velocità, stack footprint e il tempo speso per assicurarsi che non si blocca più e più volte fino a quando si blocca. Se un loop ha più senso, è sicuramente la strada da percorrere.

Answer 7

Spesso, un problema è più semplice espresso utilizzando la ricorsione. Ciò è particolarmente vero quando parli di strutture di dati ad albero (ad es. Directory, alberi decisionali ...).

Queste strutture dati sono di natura finita, quindi il più delle volte elaborandole è più chiara con la ricorsione.

Quando la profondità dello stack è spesso limitata e ogni chiamata di funzione richiede un pezzo di stack e quando si parla di una struttura di dati potenzialmente infinita, si dovrà abbandonare la ricorsione e tradurla in iterazione.

I linguaggi particolarmente funzionali sono efficaci nella gestione della ricorsione "infinita". Le lingue imperative sono focalizzate su cicli simili a iterazioni.

Answer 8

Non hai davvero bisogno di ricorsione per una struttura piatta come quella. Il primo codice che ho mai usato per la ricorsione riguarda la gestione dei contenitori fisici. Ogni contenitore potrebbe contenere elementi (un elenco di essi, ciascuno con pesi) e/o più contenitori, che hanno un peso. Avevo bisogno del peso totale di un contenitore e di tutto ciò che conteneva. (Lo usavo per prevedere il peso di grandi zaini pieni di attrezzature da campeggio senza imballarli e pesarli.) Questo era facile da fare con la ricorsione e sarebbe stato molto più difficile con i loop. Ma molti tipi di problemi che naturalmente si adattano a un approccio possono anche essere affrontati con l'altro.

Answer 9

Overflow dello stack.

E no, non intendo un sito Web o qualcosa del genere. Intendo un "overflow dello stack".