Usare la ricorsione in C #

Question

Ci sono delle regole generali quando si usa la ricorsione su come evitare lo overflow dello stack?

Answer 1

Quante volte sarai in grado di fare affidamento dipenderà da:

• La dimensione dello stack (che di solito è 1 MB IIRC, ma il file binario può essere modificato manualmente; non consiglierei di farlo)
• Quanto stack viene utilizzato da ciascun livello della ricorsione (un metodo con 10 variabili locali Guid non acquisite prenderà più stack di un metodo che non ha variabili locali, ad esempio)
• La JIT che stai usando - a volte la JIT userà la ricorsione della coda, altre volte no. Le regole sono complicate e non me le ricordo. (C'è un post sul blog di David Broman del 2007 e una pagina MSDN dello stesso autore / data , ma ormai non sono aggiornati.)

Come evitare gli overflow dello stack? Non ricorrere troppo lontano :) Se non puoi essere ragionevolmente sicuro che la tua ricorsione terminerà senza andare molto lontano (sarei preoccupato per "più di 10" anche se è molto sicuro), riscriverlo per evitare la ricorsione.

Answer 2

Dipende molto dall'algoritmo ricorsivo che stai utilizzando. Se è semplice ricorsione, puoi fare qualcosa del genere:

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 dove il livello di ricorsione può essere definito come un limite logico. Nel caso in cui ciò non accada (come un algoritmo di divisione e conquista), dovrai decidere come bilanciare la semplicità rispetto alle prestazioni rispetto alle limitazioni delle risorse. In questi casi, potrebbe essere necessario passare da un metodo all'altro dopo aver raggiunto un limite predefinito di arbritrary. Un mezzo efficace per farlo che ho usato nell'algoritmo quicksort è farlo come rapporto tra la dimensione totale della lista. In questo caso, il limite logico è il risultato di quando le condizioni non sono più ottimali.

Answer 3

Non sono a conoscenza di set fissi per evitare lo stackoverflow. Personalmente cerco di garantire -
1. Ho ragionevolmente i miei casi di base.
2. Il codice raggiunge il caso base ad un certo punto.

Answer 4

Se ti ritrovi a generare così tanti frame stack, potresti prendere in considerazione l'idea di srotolare la ricorsione in un ciclo.

Soprattutto se stai eseguendo più livelli di ricorsione (A- > B- > C- > A- > B ...) potresti scoprire che puoi estrarre uno di quei livelli in un ciclo e salvare un po 'di memoria.

Answer 5

Il limite normale, se non rimane molto nello stack tra chiamate successive, è profondo circa 15000-25000 livelli. Il 25% di questo se sei su IIS 6+.

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

Esistono vari modi per aumentare lo spazio dello stack allocato, ma preferirò prima trovare una versione iterativa. :)

Answer 6

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

Answer 7

Ho appena pensato alla ricorsione della coda, ma è risultato che C # non lo supporta. Tuttavia, il .Net-Framework sembra supportarlo:

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

Answer 8

La dimensione dello stack predefinita per un thread è 1 MB, se il CLR predefinito è in esecuzione. Tuttavia, altri host potrebbero cambiarlo. Ad esempio l'host ASP modifica l'impostazione predefinita a 256 KB. Questo significa che potresti avere un codice che funziona perfettamente con VS, ma si interrompe quando lo distribuisci nel vero ambiente di hosting.

Fortunatamente puoi specificare una dimensione dello stack, quando crei un nuovo thread usando 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 stesso per modificare la dimensione predefinita. Ciò è utile se si desidera modificare le dimensioni del thread principale. Altrimenti, consiglierei di usare il costruttore appropriato durante la creazione di thread.

Answer 9

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

Answer 10

Ricorda, se devi chiedere dei limiti di sistema, probabilmente stai facendo qualcosa di orribilmente sbagliato.

Quindi, se pensi di poter ottenere un overflow dello stack durante il normale funzionamento, devi pensare a un approccio diverso al problema.

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