Usando recursão em C #

Question

Existem regras gerais ao usar recursão sobre como evitar estouro de pilha?

Answer 1

Quantas vezes você vai ser capaz de recurse dependerá:

• O tamanho da pilha (que é geralmente 1MB IIRC, mas o binário pode ser mão-editado, eu não recomendo fazer isso)
• Quanto pilha de cada nível dos usos de recursão (um método com 10 uncaptured Guid variáveis ??locais será levar mais pilha do que um método que não tem nenhum variáveis ??locais, por exemplo)
• O JIT que você está usando - às vezes o JIT irá uso cauda recursão, outras vezes não. As regras são complicadas e eu não consigo lembrar deles. (Há uma postagem no blog de David Broman de volta a partir de 2007 , e uma página MSDN a partir do mesmo autor / data , mas eles podem estar desatualizados até agora.)

Como evitar estouros de pilha? Não recurse muito longe :) Se você não pode estar razoavelmente certo de que a sua recursão terminará sem ir muito longe (eu estaria preocupado com "mais de 10" apesar de que é muito seguro), em seguida, reescrevê-lo para recursão evitar.

Answer 2

Ela realmente depende de qual algoritmo recursivo que você está usando. Se é simples recursão, você pode fazer algo como isto:

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);
}

É importante notar que esta abordagem é realmente útil apenas quando o nível de recursividade pode ser definido como um limite lógico. No caso em que isso não pode ocorrer (como um algoritmo de dividir e conquistar), você terá de decidir como você deseja equilibrar simplicidade versus desempenho contra as limitações de recursos. Nestes casos, você pode ter que alternar entre os métodos uma vez que você atingir um limite pré-definido arbritrary. Um meio eficaz de fazer isso que eu usei no algoritmo quicksort é fazê-lo como uma relação entre o tamanho total da lista. Neste caso, o limite lógico é o resultado de quando as condições não são mais ideal.

Answer 3

Eu não tenho conhecimento de qualquer set duro para evitar stackoverflows. Eu, pessoalmente, tentar garantir -
1. Eu tenho meus casos base direita.
2. O código atinge o caso base em algum ponto.

Answer 4

Se você está encontrando-se a geração que muitos quadros de pilha, você pode querer considerar desenrolando seu recursão em um loop.

Especialmente se você estiver fazendo vários níveis de recursão (A-> B-> C-> A-> B ...) você pode achar que você pode extrair um desses níveis em um loop e poupar algum memória.

Answer 5

O limite normal, se não muito é deixado na pilha entre chamadas sucessivas, é de cerca de 15.000-25.000 níveis de profundidade. 25% do que se você estiver em IIS 6 +.

A maioria dos algorhitms recursiva pode ser expressa de forma iterativa.

Existem várias maneira de aumentar o espaço de pilha alocada, mas vou vez que você encontrar uma versão iterativa em primeiro lugar. :)

Answer 6

Para além de ter um tamanho razoável pilha e certificando-se de dividir e conquistar o seu problema de tal forma que você continuamente a trabalhar em um problema menor, não realmente.

Answer 7

Eu apenas pensei de cauda-recursão, mas acabou, que o C # não apoiá-lo. No entanto, o Net-Framework parece apoiá-lo:

http: // blogs .msdn.com / abhinaba / Arquivo / 2007/07/27 / cauda-recursão-on-net.aspx

Answer 8

O tamanho da pilha padrão para um segmento é 1 MB, se você estiver executando sob o CLR padrão. No entanto, outros hospedeiros pode mudar isso. Por exemplo, o anfitrião ASP muda o padrão de 256 KB. Isso significa que você pode ter código que funciona perfeitamente bem sob VS, mas pausas quando implantá-lo no ambiente de hospedagem real.

Felizmente, você pode especificar um tamanho da pilha, quando você cria um novo segmento usando o construtor correto. Na minha experiência, raramente é necessário, mas eu vi um caso em que esta foi a solução.

Você pode editar o cabeçalho PE do próprio binário para alterar o tamanho padrão. Isso é útil se você quer mudar o tamanho para o segmento principal. Caso contrário, eu recomendo usar o construtor apropriado ao criar tópicos.

Answer 9

Eu escrevi um pequeno artigo sobre este aqui . Basicamente, eu passar um parâmetro opcional chamado, profundidade, acrescentando 1 a ela cada vez que eu ir mais fundo nele. Dentro do método recursivo I verificar a profundidade de um valor. Se for maior do que o valor definido I, eu lançar uma exceção. O valor (limite) seria dependente de suas necessidades de aplicações.

Answer 10

Lembre-se, se você tem que perguntar sobre os limites do sistema, então provavelmente você está fazendo algo terrivelmente errado.

Então, se você acha que você pode obter um estouro de pilha em operação normal, então você precisa pensar em uma abordagem diferente para o problema.

Não é difícil converter uma função recursiva em um um iterativo, especialmente como C # tem a coleção genérico :: Stack. Usando o tipo de pilha se move a memória usada em pilha do programa em vez da pilha. Isso lhe dá a gama endereço completo para armazenar os dados recursiva. Se isso não for suficiente, não é muito difícil de página os dados no disco. Mas eu consideraria seriamente outras soluções, se você chegar a esta fase.