In C# è una buona pratica utilizzare le funzioni ricorsive negli algoritmi?

Question

In molti linguaggi funzionali, l'utilizzo di una ricorsione è considerato una buona pratica. Penso che sia buono a causa del modo in cui il compilatore ottimizza il codice del linguaggio funzionale.

Tuttavia, è buona norma utilizzare la ricorsione in C# durante la creazione di un algoritmo? È corretto dire in merito a C#, che gli algoritmi ricorsivi comporteranno un aumento notevole dello stack (se la quantità di chiamate è molto grande) e questo non sarà affatto veloce e potrebbe comportare un sovraccarico dello stack. O ci sono anche alcuni eventi di ottimizzazione per rendere efficienti le funzioni ricorsive?

Sarei grato se tu dessi qualche paragone (velocità, memoria, leggibilità) tra algoritmi che usano la ricorsione in linguaggi funzionali e C#.

Answer 1

Non utilizzare la ricorsione causerà comunque la riscrittura del proprio algoritmo utilizzando il proprio "Stack", che alla fine sarà soggetto a condizioni simili durante l'esecuzione.

È possibile personalizzare le dimensioni dello stack in base alle necessità dell'algoritmo, ma se si considerano gli algoritmi WPF/Silverlight e normali dell'interfaccia utente, sono tutti di natura ricorsiva e ogni clic, ogni pressione di tasto e ogni notifica passano attraverso molto metodi ricorsivi.

Partenza Creating Thread with Custom Stack Size,

Anche se la velocità può variare a seconda dell'algoritmo e la complessità, ma la creazione di un algoritmo riservato ai non ricorsivo renderà compito più complesso, come si farà tutte le operazioni di memorizzare i dati da soli utilizzando gli elenchi, pile ecc.

Questo è piuttosto un problema di progettazione e prestazioni, se si desidera ottenere prestazioni migliori, l'algoritmo non ricorsivo verrà eseguito più rapidamente, ma sarà necessario più tempo per progettare e implementare tale algoritmo. In caso contrario, se si desidera una soluzione più rapida, è possibile scrivere un algoritmo ricorsivo che sarà più lento in esecuzione, ma se la differenza è solo di pochi millisecondi o microsecondi, non vale la pena farlo.

Answer 2

Il loop supera sempre la ricorsione poiché lo stack ha sempre più sovraccarico del tuo stato. Un sacco di operazioni di threading passano pesantemente sullo stack in modo da ottenere un ulteriore calo.

Tuttavia, la leggibilità è un grande vantaggio in modo da io personalmente utilizzare la ricorsione a meno che non ho bisogno di ogni goccia di perfromance come ad esempio nelle operazioni di elaborazione delle immagini o mi aspetto che i miei pile di crescere molto grande - anche se overflow dello stack quasi esclusivamente a causa di bug.

Answer 3

Qui questo post Recursive iterator performance spiega in dettaglio la differenza tra la versione ricorsiva e l'operazione non ricorsiva. I risultati sono interessanti Check out

Answer 4

Nell'attuale implementazione di Microsoft del compilatore C#, le ottimizzazioni delle chiamate tail non vengono eseguite. Ciò rende gli algoritmi funzionali che ricorrono profondamente oltre la pila. Mentre non raccomanderei l'uso di algoritmi profondamente ricorsivi in ​​C#, i metodi che non ricorrono in profondità non dovrebbero causare alcun problema.

Answer 5

Quando hai bisogno di una ricorsione, ne hai bisogno, come per la camminata dell'albero in profondità o l'analisi della discesa ricorsiva.

Se hai una scelta, come usare la ricorsione invece di un ciclo, allora forse è una funzione di quale lingua sei. Resta semplice.

Answer 6

La ragione per cui la ricorsione nei linguaggi funzionali è una buona pratica non è dovuta alle ottimizzazioni della ricorsione della coda; è una buona pratica perché è un modo potente e semplice per esprimere molti algoritmi. Le ottimizzazioni sono semplici, e comunque le ottimizzazioni delle chiamate tail non sono rilevanti per tutte le funzioni ricorsive.

Quindi con questo in mente, è perfettamente una buona pratica costruire metodi ricorsivi in ​​C#, se questo è il modo più naturale di esprimere il proprio algoritmo. Ovviamente, se risulta avere problemi di profondità dello stack, potrebbe essere sensato renderlo iterativo. Ma prendere un algoritmo naturalmente ricorsivo e renderlo iterativo senza prima sapere che si tratta di un problema è l'ottimizzazione prematura, e potrebbe rendere il tuo codice inutilmente complicato e difficile da leggere in cambio di scarso guadagno di prestazioni.