Funções recursivas, estouros de pilha, e Y-Combinadores

Question

Eu tenho uma função recursiva (em C #) que eu preciso para chamar cerca de 800 milhões de vezes; esta seria obviamente normalmente resultar em um estouro de pilha depois sobre a chamada 900. Eu chutei isso para vários loops, mas o padrão recursiva é apenas muito mais fácil, e mais limpo para manter.

Eu estou olhando para implementar a função recursiva usando uma y-Combinator, a partir do que estou lendo e visto, que deve resolver o problema de estouro de pilha, e corrigir os vários loops aninhados.

Alguém tem experiência usando o y-combinator? Eu ainda vou ser preso em um estouro de pilha?

Tomemos o exemplo simples de um fatorial. A factorial na maioria dos números maiores do que como 5000 vai causar um estouro de pilha. Se eu usei um y-combinator corretamente nesse cenário, seria corrigir o estouro de pilha?

Não parece trivial para implementar, por isso quero confirmar isso antes de eu gastar o esforço de desenvolvimento / recursos implementação e aprender a y-Combinator.

Answer 1

Não, usando o Y-Combinator não vai ajudar a sua situação. Se você precisa fazer algo 800 milhões de vezes, você pode (a) recurse, ou (b) loop (ou Suponho (c) write 800 milhões de chamadas para a função). Desde o Y-Combinator não loop, ele deve, portanto, recurse.

Um loop é o que você está procurando, a menos que você estiver usando um ambiente de tempo de execução que recursão ofertas adequada cauda (como Scheme).

Dito isto, a implementação da Y-Combinator a partir do zero na língua de sua escolha é um excelente exercício.

Answer 2

combinadores

Y são úteis, mas eu acho que você realmente quer cauda recursão otimização que elimina o uso da pilha para funções recursiva cauda. recursão de cauda só é possível quando o resultado de cada chamada recursiva é imediatamente devolvido pelo chamador e nunca qualquer computação adicional após a chamada. Infelizmente C # não suporta otimização cauda recursão no entanto você pode imitá-lo com um trampolim que permite uma conversão simples de método recursivo cauda a um método trampolim embrulhado.

// Tail
int factorial( int n ) { return factorialTail( n, 1, 1 ); }
int factorialTail( int n, int i, int acc ) {
  if ( n < i ) return acc;
  else return factorialTail( n, i + 1, acc * i );
}

// Trampoline
int factorialTramp( int n ) { 
   var bounce = new Tuple<bool,int,int>(true,1,1);
   while( bounce.Item1 ) bounce = factorialOline( n, bounce.Item2, bounce.Item3 );
   return bounce.Item3;
}
Tuple<bool,int,int> factorialOline( int n, int i, int acc ) {
  if ( n < i ) return new Tuple<bool,int,int>(false,i,acc);
  else return new Tuple<bool,int,int>(true,i + 1,acc * i);
}

Answer 3

Você pode usar o trampolim como é usado em Reactive Extensão, tentei explicar isso no meu blog http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

Uma solução é converter sua função (s) para usar um loop e um explícita contexto estrutura de dados. O contexto representa o que as pessoas geralmente pensam como a pilha de chamadas. Você pode achar minha resposta a outra pergunta sobre a conversão de recursão de cauda útil. Os passos relevantes são de 1 a 5; 6 e 7 são específicos para essa função específica, enquanto que sons o seu mais complicado.

A alternativa "fácil", porém, é para adicionar um contador de profundidade para cada uma de suas funções; quando se atinge um determinado limite (determinado pela experimentação), gerar um novo segmento para continuar a recursão com uma pilha fresco. Os velhos blocos segmento de espera para o novo segmento para enviar-lhe um resultado (ou se você quer ser extravagante, um resultado ou uma exceção a re-raise). O contador de profundidade remonta a 0 para o novo segmento; quando se atinge o limite, criar uma terceira linha, e assim por diante. Se você armazenar em cache tópicos para evitar pagar o custo de criação de threads mais frequentemente do que o necessário, espero que você vai ter um desempenho aceitável sem ter que reestruturar drasticamente seu programa.