La ricorsione è un'istanza di essere "troppo intelligente" durante la programmazione?

8

Ho letto diversi libri e ho appreso attraverso l'esperienza che ottimizzare il codice fino al punto in cui è imperscrutabile, o trovare una soluzione estremamente rapida ma estremamente complessa a un problema non è auspicabile quando si lavora in team, o anche quando si stai lavorando da solo e devi capire la tua soluzione intelligente qualche tempo dopo.

La mia domanda è: la ricorsione dovrebbe essere trattata nello stesso modo? Il programmatore medio capisce facilmente la ricorsione e quindi si dovrebbe usarla impunemente, o il programmatore medio non capisce molto bene la ricorsione e si dovrebbe starne alla larga per il rendimento complessivo del team?

So che ci sono risposte semplici di "Ogni programmatore che non capisce la ricorsione non vale un granello di sale, quindi non preoccuparti per loro", ma mi stavo chiedendo se avessi avuto qualche esperienza nel mondo reale. vorrei condividere ciò che illuminerebbe la questione più dell'opinione che ho appena citato.

    
posta Macy Abbey 10.12.2010 - 04:20
fonte

7 risposte

21

Does the average programmer understand recursion easily and thus one should use it with impunity, or does the average programmer not understand recursion very well and one should stay away from it for the sake of overall team productivity?

Direi che il programmatore medio capisce perfettamente la ricorsione. In effetti, se il programmatore ha conseguito una laurea in Informatica o Ingegneria del software è praticamente garantito. Certo, ci sono alcuni programmatori molto al di sotto della media, ma non li vuoi nella tua squadra.

In questo caso, la distinzione tra un programmatore medio e un buon programmatore è sapere quando usare la ricorsione e quando no. E questo dipende dal problema risolto e dal linguaggio utilizzato per risolverlo.

  • Se si utilizza un linguaggio di programmazione funzionale, la ricorsione è una soluzione naturale ed efficiente per una vasta gamma di problemi. (Regole di ottimizzazione della ricorsione di coda!)

  • Se si utilizza un OO o un linguaggio procedurale semplice, la ricorsione può essere inefficiente e può essere problematica a causa dello stack overflow. Quindi in alcuni casi sceglieresti una soluzione iterativa piuttosto che una ricorsiva. Tuttavia, in altri casi, la soluzione ricorsiva è molto più semplice ed elegante che la soluzione iterativa (possibilmente più efficiente) sarebbe quella "troppo intelligente". (Ad esempio, se il problema richiede il backtracking, la costruzione o la camminata di alberi / grafici, ecc., La ricorsione è spesso più semplice.)

risposta data 10.12.2010 - 09:03
fonte
42

Alcuni problemi sono naturalmente ricorsivi. Presentarsi con una soluzione iterativa in questi casi può effettivamente essere più complesso e complesso rispetto a quelli ricorsivi. Un buon esempio è qualsiasi algoritmo che deve attraversare una struttura gerarchica ad albero, che è un compito non comune nella programmazione.

TL; Versione DR: No.

    
risposta data 10.12.2010 - 04:30
fonte
11

La ricorsione è un principio fondamentale nella maggior parte dei linguaggi di programmazione funzionale. L'iterazione (looping) nei linguaggi funzionali viene solitamente eseguita tramite ricorsione.

I linguaggi funzionali hanno visto un po 'di rinascita ultimamente, a causa della necessità di gestire elegantemente più core del processore; i linguaggi funzionali aiutano a raggiungere questo tipo di concorrenza fornendo modi per ragionare meglio sul tuo programma senza la complessità implicata nel bloccare le strutture mutabili.

    
risposta data 10.12.2010 - 04:33
fonte
11

Alcuni problemi, come camminare su una struttura ad albero (camminare, ad esempio, su un'intera struttura di directory, anziché cercare, ad esempio, un nodo B-Tree specifico), sono ideali per l'uso della ricorsione; gli equivalenti non ricorsivi spesso aggiungono semplicemente la complicazione di gestire il proprio stack.

In questi casi, la ricorsione è la soluzione migliore, più semplice e più facile da capire.

    
risposta data 10.12.2010 - 06:01
fonte
7

Direi ricorrere alla ricorsione dove è appropriato, ma cerca sempre modi per evitare la ricorsione esplicita.

Ad esempio, se trovi la necessità di attraversare manualmente una struttura ad albero, allora sì, dovresti usare la ricorsione. Se qualcuno è abbastanza stupido da non capire un attraversamento dell'albero ricorsivo, non farà né la testa né la coda della versione iterativa.

Ma l'opzione migliore è usare un iteratore che estrae la ricorsione nel punto in cui tutto ciò che vedi è "Eseguo questa operazione su tutto nella struttura".

    
risposta data 10.12.2010 - 04:32
fonte
3

La ricorsione, è il meccanismo più semplice dal punto di vista della pulizia del codice. Se la velocità è assolutamente essenziale, forse è possibile utilizzare una matrice 2D di parametri problema. Generare un processo figlia è quindi semplicemente aggiungere un altro elemento all'array. Una volta ho fatto un risolutore tridiagonale di assemblatori, il che è stato un grosso problema nel corso della giornata. Il contesto necessario per istanza era di 8 parole per livello e ciascun sottoproblema era un terzo della dimensione del precedente. Questa "biblioteca" era popolare solo perché superava tutte le altre implementazioni là fuori. Ma questa è una situazione piuttosto rara nella programmazione, quindi non devi soccombere a "ottimizzazione prematura", solo perché questa soluzione è disponibile. Ovviamente per alcune cose il suo terribile eccesso, come l'esempio della ricorsione 101 "calcola il fattoriale". Ma per la maggior parte delle app, è un modo davvero elegante per eliminare la complessità del codice sorgente.

Ho un semplice correttore ortografico che uso per un'app, (dove voglio dare suggerimenti sulla correzione di piccoli errori ortografici), dove computo la "distanza" tra due stringhe, che consente le cancellazioni e le aggiunte. Ciò porta a una struttura ad albero potenzialmente grande, e i rami sono tagliati in quanto ci interessano solo le partite ravvicinate. Con la ricorsione, le sue forse venti linee di codice (ho entrambe le versioni di Fortran e C). Penso che sarebbe complicato altrimenti. Diamine è stato molto più facile programmare / debug verificare, piuttosto che pensare a quell'albero!

    
risposta data 10.12.2010 - 05:35
fonte
0

Capisco ma non l'ho mai usato esplicitamente. Penso che chiunque si definisca un programmatore dovrebbe sapere o apprendere quanto è necessario sapere quali sono lo stack e l'heap. Ehi, tutti devono sapere come funziona min / max su tic-tac-toe, tramite ricorsione fantasia.

    
risposta data 10.12.2010 - 16:59
fonte

Leggi altre domande sui tag