Utilizzo della ricorsione in C#

Question

Esistono regole generali quando si utilizza la ricorsione su come evitare gli stackoverflow?

Answer 1

Quante volte ti sarà in grado di ricorsione dipenderà da:

• la dimensione dello stack (che di solito è 1 MB IIRC, ma il binario può essere modificato a mano, io non consiglierei di farlo)
• quanto pila ogni livello degli usi ricorsione (un metodo con 10 non catturate Guid variabili locali sarà prendere più di stack di un metodo che non ha nessun variabili locali, per esempio)
• Il JIT si sta utilizzando - a volte il JIT utilizza ricorsione di coda, altre volte non lo fa . Le regole sono complicate e non riesco a ricordarle. (C'è un blog post by David Broman back from 2007, e an MSDN page from the same author/date, ma possono non essere aggiornati da ora.)

come evitare overflow dello stack? Non recitare troppo lontano :) Se non puoi essere ragionevolmente sicuro che la tua recessione terminerà senza andare molto lontano (sarei preoccupato di "più di 10" anche se questo è molto sicuro) quindi riscrivilo per evitare la ricorsione.

Answer 2

Oltre ad avere una dimensione di stack ragionevole e assicurarsi di dividere e conquistare il problema in modo da lavorare continuamente su un problema più piccolo, non proprio.

Answer 3

Non sono a conoscenza di alcun set per evitare i flussi di stackover. Io personalmente cerco di garantire -
1. Ho le mie basi di destra.
2. Il codice raggiunge il caso base ad un certo punto.

Answer 4

Se stai scoprendo che stai creando molti frame di stack, potresti considerare di srotolare la tua ricorsione in un ciclo.

Soprattutto se si eseguono più livelli di ricorsione (A-> B-> C-> A-> B ...) si potrebbe scoprire che è possibile estrarre uno di questi livelli in un ciclo e salvarsi un po 'di memoria .

Answer 5

Il limite normale, se non è rimasto molto nello stack tra le chiamate successive, è profondo intorno ai 15000-25000 livelli. 25% di quello se sei su IIS 6+.

La maggior parte degli algoritmi ricorsivi può essere espressa in modo iterativo.

Ci sono vari modi per aumentare lo spazio di stack allocato, ma preferisco lasciarti trovare prima una versione iterativa. :)

Answer 6

Dipende molto dall'algoritmo ricorsivo che si sta utilizzando. Se si tratta di semplice ricorsione, si può fare qualcosa di simile:

public int CalculateSomethingRecursively(int someNumber) 
{ 
    return doSomethingRecursively(someNumber, 0); 
} 

private int doSomethingRecursively(int someNumber, int level) 
{ 
    if (level >= MAX_LEVEL || !shouldKeepCalculating(someNumber)) 
     return someNumber; 
    return doSomethingRecursively(someNumber, level + 1); 
} 

Vale la pena notare che questo approccio è davvero utile solo se il livello di ricorsione può essere definito come un limite logico. Nel caso in cui ciò non si verifichi (come un algoritmo divide and conquer), dovrai decidere come bilanciare la semplicità contro le prestazioni rispetto alle limitazioni delle risorse. In questi casi, potrebbe essere necessario passare da un metodo all'altro una volta raggiunto un limite predefinito arbritrario. Un mezzo efficace per fare ciò che ho usato nell'algoritmo quicksort è farlo come un rapporto della dimensione totale della lista. In questo caso, il limite logico è il risultato di quando le condizioni non sono più ottimali.

Answer 7

Ho appena pensato alla ricorsione in coda, ma si è scoperto che C# non lo supporta. Tuttavia la .Net-Framework sembra sostenerlo:

http://blogs.msdn.com/abhinaba/archive/2007/07/27/tail-recursion-on-net.aspx

Answer 8

Ricordate, se si deve chiedere di limiti del sistema, allora probabilmente stai facendo qualcosa di terribilmente sbagliato.

Quindi, se si ritiene che si possa ottenere un overflow dello stack durante il normale funzionamento, è necessario pensare a un approccio diverso al problema.

Non è difficile convertire una funzione ricorsiva in una iterativa, soprattutto perché C# ha la raccolta Generic :: Stack. L'uso del tipo di pila sposta la memoria utilizzata nell'heap del programma anziché nella pila. Questo ti dà l'intero intervallo di indirizzi per memorizzare i dati ricorsivi. Se ciò non è sufficiente, non è troppo difficile eseguire il paging dei dati sul disco. Ma prenderei seriamente in considerazione altre soluzioni se arrivi a questo stadio.

Answer 9

La dimensione dello stack predefinita per un thread è 1 MB, se si sta utilizzando il CLR predefinito. Tuttavia, altri host potrebbero cambiarlo. Ad esempio, l'host ASP cambia il valore predefinito a 256 KB. Ciò significa che potresti avere un codice che funziona perfettamente in VS, ma si interrompe quando lo si distribuisce nell'ambiente di hosting reale.

Fortunatamente è possibile specificare una dimensione dello stack quando si crea un nuovo thread utilizzando il costruttore corretto. Nella mia esperienza è raramente necessario, ma ho visto un caso in cui questa era la soluzione.

È possibile modificare l'intestazione PE del file binario per modificare la dimensione predefinita. Questo è utile se vuoi cambiare la dimensione del thread principale. Altrimenti, consiglierei di usare il costruttore appropriato durante la creazione dei thread.

Answer 10

Ho scritto un breve articolo su questo here. Fondamentalmente, passo un parametro opzionale chiamato, depth, aggiungendo 1 ad esso ogni volta che approfondisco. All'interno del metodo ricorsivo, controllo la profondità di un valore. Se è maggiore del valore impostato, lancio un'eccezione. Il valore (soglia) dipenderà dalle esigenze delle applicazioni.