Ricorsione o loop while

La ricorsione non è intrinsecamente migliore o peggiore dei cicli - ognuno presenta vantaggi e svantaggi e anche quelli dipendono dal linguaggio di programmazione (e dall'implementazione).

Tecnicamente, i loop iterativi si adattano meglio ai sistemi di computer tipici a livello di hardware: a livello di codice macchina, un ciclo è solo un test e un salto condizionato, mentre la ricorsione (implementata in modo ingenuo) comporta il push di uno stack frame, il salto, il ritorno, e tornando indietro dalla pila. OTOH, molti casi di ricorsione (specialmente quelli che sono banalmente equivalenti ai loop iterativi) possono essere scritti in modo tale che lo stack push / pop possa essere evitato; questo è possibile quando la chiamata alla funzione ricorsiva è l'ultima cosa che accade nel corpo della funzione prima di tornare, ed è comunemente nota come ottimizzazione della chiamata di coda (o ottimizzazione della ricorsione di coda ) . Una funzione ricorsiva ottimizzata in coda è per lo più equivalente a un loop iterativo a livello di codice macchina.

Un'altra considerazione è che i loop iterativi richiedono aggiornamenti di stato distruttivi, il che li rende incompatibili con la semantica di linguaggio pura (senza effetti collaterali). Questo è il motivo per cui i linguaggi puri come Haskell non hanno affatto costrutti di loop, e molti altri linguaggi di programmazione funzionale ne mancano completamente o li evitano il più possibile.

Il motivo per cui queste domande appaiono così tanto nelle interviste, però, è perché per rispondere a queste domande è necessaria una conoscenza approfondita di molti concetti vitali di programmazione: variabili, chiamate di funzioni, scope e, naturalmente, loop e ricorsione -, e devi portare la flessibilità mentale al tavolo che ti consente di affrontare un problema da due angoli radicalmente diversi e spostarti tra le diverse manifestazioni dello stesso concetto.

L'esperienza e la ricerca suggeriscono che esiste una linea che separa le persone che hanno la capacità di comprendere variabili, indicatori e ricorsività e quelli che non lo fanno. Quasi tutto il resto nella programmazione, inclusi framework, API, linguaggi di programmazione e casi limite, può essere acquisito attraverso lo studio e l'esperienza, ma se non si riesce a sviluppare un'intuizione per questi tre concetti chiave, non si è idonei a diventare programmatori. La traduzione di un semplice loop iterativo in una versione ricorsiva riguarda il modo più rapido di filtrare i non programmatori - anche un programmatore piuttosto inesperto può farlo in 15 minuti, ed è un problema molto indipendente dalla lingua, quindi il candidato può scegliere una lingua di loro scelta invece di inciampare sulle idiosincrasie.

Se ricevi una domanda come questa in un'intervista, è un buon segno: significa che il potenziale datore di lavoro cerca persone che possono programmare, non persone che hanno memorizzato il manuale di uno strumento di programmazione.

Dipende.

• Alcuni problemi sono molto suscettibili alle soluzioni ricorsive, ad es. quicksort
• Alcune lingue in realtà non supportano la ricorsione, ad es. FORTRAN precoci
• Alcune lingue assumono la ricorsione come mezzo principale per il looping ad es. Haskell

Vale anche la pena notare che il supporto per la ricorsione di coda rende i loop ricorsivi e iterativi equivalenti, ovvero la ricorsione non fa Devo sempre perdere la pila.

Inoltre, un algoritmo ricorsivo può sempre essere implementato iterativamente utilizzando uno stack esplicito .

Infine, noterei che una soluzione a cinque linee è probabilmente sempre migliore di una linea 100 (assumendo che siano effettivamente equivalenti).

Non esiste una definizione universalmente condivisa di "migliore" quando si parla di programmazione, ma intendo dire "più facile da mantenere / leggere".

La ricorsione ha un potere più espressivo rispetto ai costrutti iterativi del ciclo: lo dico perché un ciclo while è equivalente a una funzione ricorsiva della coda e le funzioni ricorsive non devono necessariamente essere ricorsive in coda. I costrutti potenti di solito sono una cosa negativa perché ti permettono di fare cose che sono difficili da leggere. Tuttavia, la ricorsione ti dà la possibilità di scrivere loop senza usare la mutabilità e secondo me la mutabilità è molto più potente della ricorsione.

Quindi, dal basso potere espressivo all'elevata potenza espressiva, i costrutti ciclici si impilano in questo modo:

• Funzioni ricorsive di coda che utilizzano dati immutabili,
• Funzioni ricorsive che utilizzano dati immutabili
• Cicli mobili che utilizzano dati mutevoli,
• Funzioni ricorsive di coda che utilizzano dati mutevoli,
• Funzioni ricorsive che utilizzano dati mutevoli,

Idealmente, dovresti usare i costrutti meno espressivi che puoi. Ovviamente, se la tua lingua non supporta l'ottimizzazione delle chiamate tail, ciò potrebbe anche influenzare la scelta del costrutto di looping.

La ricorsione è spesso meno ovvia. Meno ovvio è più difficile da mantenere.

Se scrivi for(i=0;i<ITER_LIMIT;i++){somefunction(i);} nel flusso principale, rendi perfettamente chiaro che stai scrivendo un ciclo. Se scrivi somefunction(ITER_LIMIT); non rendi davvero chiaro cosa accadrà. Visualizzazione solo del contenuto: quella somefunction(int x) chiama somefunction(x-1) indica che si tratta di un ciclo che utilizza le iterazioni. Inoltre, non è possibile inserire facilmente una condizione di escape con break; da qualche parte a metà delle iterazioni, è necessario aggiungere un condizionale che verrà passato completamente indietro o generare un'eccezione. (e le eccezioni aggiungono di nuovo complessità ...)

In sostanza, se è una scelta ovvia tra iterazione e ricorsione, fai la cosa intuitiva. Se l'iterazione fa il lavoro facilmente, il salvataggio di 2 righe raramente vale il mal di testa che potrebbe creare nel lungo periodo.

Ovviamente se ti salva 98 righe, è una questione completamente diversa.

Ci sono situazioni in cui la ricorsione si adatta semplicemente perfettamente, e non sono davvero rare. Attraversamento di strutture ad albero, reti con collegamenti multipli, strutture che possono contenere un proprio tipo, matrici frastagliate multidimensionali, sostanzialmente tutto ciò che non è né un vettore diretto né una serie di dimensioni fisse. Se attraversi un percorso noto, dritto, esegui l'iterazione. Se ti immergi nello sconosciuto, recurse.

In sostanza, se somefunction(x-1) deve essere chiamato da dentro più di una volta per livello, dimentica le iterazioni.

... Scrivere in modo iterativo le funzioni per le attività meglio eseguite dalla ricorsione è possibile ma non piacevole. Ovunque tu usi int , hai bisogno di qualcosa come stack<int> . L'ho fatto una volta, più come esercizio che per scopi pratici. Posso assicurarti che una volta affrontato questo compito non avrai dubbi come quelli che hai espresso.

Come al solito, questo è inarrestabile in generale perché ci sono altri fattori, che in pratica sono ampiamente diseguali tra i casi e non uguali tra loro all'interno di un caso d'uso. Ecco alcune delle pressioni.

• Il codice breve ed elegante è in generale superiore al codice lungo e complesso.
• Tuttavia, l'ultimo punto è in qualche modo invalidato se la tua base di sviluppatori non ha familiarità con la ricorsione e non vuole / non può imparare. Potrebbe persino diventare un negativo piuttosto che un positivo.
• La ricorsione può essere dannosa per l'efficienza se avrai bisogno di chiamate profondamente annidate nella pratica e non puoi usare la ricorsione di coda (o il tuo ambiente non può ottimizzare la coda ricorsione).
• Anche la ricorsione è cattiva in molti casi se non è possibile memorizzare correttamente i risultati intermedi nella cache. Ad esempio, l'esempio comune di utilizzare la ricorsione ad albero per calcolare i numeri di Fibonacci esegue orribilmente male se non si memorizza nella cache. Se fai il cache, è semplice, veloce, elegante e del tutto meraviglioso.
• La ricorsione non è applicabile ad alcuni casi, tanto quanto l'iterazione negli altri, e assolutamente necessaria in altri ancora. Di solito non si ricorre affatto alla ricorsione attraverso lunghe catene di regole aziendali. Iterare attraverso i flussi di dati può essere fatto utilmente con la ricorsione. L'iterazione su strutture di dati dinamici multidimensionali (ad esempio labirinti, alberi di oggetti ...) è praticamente impossibile senza ricorsione, esplicita o implicita. Nota che in questi casi, la ricorsione esplicita è molto migliore di quella implicita - niente è più doloroso della lettura di codice dove qualcuno ha implementato il proprio stack ad-hoc, incompleto e buggy all'interno della lingua solo per evitare la paura R -word.

La ricorsione riguarda la ripetizione della chiamata alla funzione, il ciclo consiste nel ripetere il salto da inserire nella memoria.

Dovrebbe essere menzionato anche riguardo allo stack overflow - link

Dipende davvero dalla praticità o dal requisito:

Se usi il linguaggio di programmazione Python , supporta la ricorsione, ma per impostazione predefinita esiste un limite per la profondità di ricorsione (1000). Se supera il limite, riceveremo un errore o un'eccezione. Questo limite può essere modificato, ma se lo facciamo potremmo sperimentare situazioni anomale nella lingua.

In questo momento (numero di chiamate più della profondità di ricorsione), dobbiamo preferire i costrutti del ciclo. Voglio dire, se la dimensione dello stack non è sufficiente, dobbiamo preferire i costrutti del ciclo.

Utilizza il modello di progettazione della strategia.

• La ricorsione è pulita
• I loop sono (discutibilmente) efficienti

A seconda del carico (e / o di altre condizioni), scegline uno.