Como a sua linguagem favorita lidar com profunda recursão? [fechadas]

Question

Eu recentemente comecei a aprender Python e eu estava um pouco surpreso de encontrar um limite de recursão profunda 1000 (por padrão). Se você configurá-lo alto o suficiente, cerca de 30000, ele trava com uma falha de segmentação como C. Embora, C parece ir bastante mais elevado.

(O pessoal Python são rápidos em apontar que você sempre pode converter funções recursivas para os iterativos e que eles são sempre mais rápido. Isso é 100% verdade. Não é realmente o que a minha pergunta é sobre embora.)

Eu tentei a mesma experiência em Perl e algo em torno de 10 milhões recursions que consumia todos os meus 4 GB de RAM e eu usei ^ C parar de tentar. Claramente Perl não usa a pilha C, mas ele usa uma quantidade ridícula de memória quando ele recurses -. Não muito chocante considerando a quantidade de trabalho que tem a ver com as funções de chamada

Eu tentei em Pike e foi completamente surpreso ao receber 100.000.000 recursions em cerca de 2 segundos. Eu não tenho nenhuma idéia de como ele fez isso, mas eu suspeito que arrasou a recursão para um processo iterativo - não parece consumir qualquer memória extra, enquanto ele faz isso. [Nota: Pike faz casos triviais achatar, mas segfaults sobre os mais complicados, ou assim me disseram.]

Eu usei essas funções de outra forma inúteis:

int f(int i, int l) { if(i<l) return f(i+1,l); return i; }

sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] };

def f(i,l):
   if i<l:
     return f(i+1,l)
   return i

Estou muito curioso como outras línguas (por exemplo, PHP, Ruby, Java, Lua, Ocaml, Haskell) alça de recursão e por que eles lidar com isso dessa forma. Além disso, observe se ele faz a diferença, se a função é "cauda-recursivo" (ver comentário).

Answer 1

"As pessoas Python são rápidos em apontar que você sempre pode converter funções recursivas para os iterativos e que eles são sempre mais rápido"

Isso é verdade, mas se ele é realmente tão fácil assim, por que não Python fazer isso por mim, para que o meu código pode parecer tão simples quanto possível? (Digo isto para não bater implementadores Python, mas porque a resposta explica o problema).

otimizações

Recursão estiveram presentes em linguagens funcionais, já que, como, o século 14 ou algo assim. Haskell, CAML, implementações Lisp tudo normalmente converter funções recursivas pelo menos cauda de iterações: você basicamente fazer isso através da identificação de que é possível, ou seja, que a função pode ser reorganizados de modo que nenhum outro do que o valor de retorno variáveis ??locais são usadas após a chamada recursiva . Um truque para torná-lo possível se há algum trabalho feito para o valor de retorno recursed antes do retorno, é a introdução de um parâmetro adicional "acumulador". Em termos simples, isto significa que o trabalho pode efetivamente ser feito no caminho "para baixo" em vez de no caminho "para cima":. Procurar em torno de 'como fazer uma função cauda-recursivo' para obter detalhes

Os detalhes reais de transformar uma função recursiva de cauda em um loop é basicamente a coqueteleira com a sua chamada convenção tal, você pode "realizar a chamada" simplesmente definindo os parâmetros e saltar de volta para o início da função, sem se preocupar em salvar todas essas coisas no escopo que você sabe que nunca vai usar. Em termos assembler, você não tem que preservar chamador-salva registros se a análise de fluxo de dados diz que eles estão sem uso além da chamada, eo mesmo vale para qualquer coisa na pilha: você não tem que mover o ponteiro da pilha em uma chamada, se você não se importa "seu" pouco de pilha sendo rabiscado pelo próximo recursão / iteração.

Ao contrário de como você parafraseado as pessoas Python, convertendo uma função recursiva geral para uma iteração não é trivial: por exemplo, se é multiplicar-recursiva, em seguida, em uma abordagem simples que você ainda precisa de uma pilha.

Memoização é uma técnica útil, no entanto, para funções arbitrariamente recursiva, que você pode gostar de olhar para cima se você estiver interessado nas possíveis abordagens. O que isto significa é que cada vez que uma função é avaliada, você furar o resultado em um cache. Para usar isso para recursão otimizar, basicamente, se o número de função recursiva "para baixo", e você memoize-lo, então você pode avaliá-lo de forma iterativa, adicionando um loop que conta "para cima" cálculo de cada valor da função, por sua vez até chegar ao alvo. Esta muito pouco espaço de pilha utilizações, desde que o cache memorando é grande o suficiente para armazenar todos os valores que você vai precisar: por exemplo, se f (n) depende de f (n-1), f (n-2) e f (n -3) você só precisa de espaço para 3 valores no cache: como você ir até você pode chutar a escada de distância. Se f (n) depende de f (n-1) e f (n / 2), você precisa de muito espaço no cache, mas ainda menos do que você usaria para a pilha em uma recursão unoptimised.

Answer 2

Esta é mais uma questão de implementação do que uma questão da língua. Não há nada que impeça alguns (stoopid) compilador C implementador de também limitar a sua pilha de chamadas para 1000. Há uma grande quantidade de pequenos processadores lá fora, que não teria espaço de pilha, mesmo para muitos.

(O pessoal Python são rápidos em apontar que você sempre pode converter funções recursivas para os iterativos e que eles são sempre mais rápido. Isso é 100% verdade. Não é realmente o que a minha pergunta é sobre embora.)

Talvez eles dizem isso, mas isso não é totalmente correcta. Recursão sempre pode ser convertido para iteração, mas às vezes ele também requer o uso manual de um pilha também. Nestas circunstâncias, eu podia ver a versão recursiva ser mais rápido (supondo que você é inteligente o suficiente para fazer otimizações simples, como puxar declarações desnecessárias fora da rotina recursiva). Afinal, os empurrões pilha que cercam chamadas de procedimento são um problema bem delimitada que seu compilador deve saber como otimizar muito bem. operações de pilha manuais, por outro lado, não vão se especializaram código de otimização em seu compilador, e são susceptíveis de ter todos os tipos de verificações de interface do usuário de sanidade que vai ocupar ciclos extra.

Pode ser o caso de que a solução / pilha iterativa é sempre mais rápido em Python . Se assim for, isso é uma falha de Python, não da recursão.

Answer 3

PHP tem um limite padrão de 100 antes de morrer:

Fatal error: Maximum function nesting level of '100' reached, aborting!

Edit: Você pode alterar o limite com ini_set('xdebug.max_nesting_level', 100000);, mas se você ir acima de aproximadamente 1150 iterações PHP falhar:

[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.

Answer 4

C # /. NET usará cauda recursão em um determinado conjunto de circunstâncias. (A C # compilador não emitem um código de operação tailcall, mas o JIT irá implementar recursão de cauda em alguns casos .

Shri Borde também tem um post sobre este tema . Claro, o CLR está mudando continuamente, e com .NET 3.5 e 3.5SP1 ele pode ter mudado de novo no que diz respeito às chamadas de cauda.

Answer 5

Usando o seguinte no console interativo F #, ele correu em menos de um segundo:

let rec f i l = 
  match i with 
  | i when i < l -> f (i+1) l
  | _ -> l

f 0 100000000;;

Então eu tentei um ou seja tradução em linha reta.

let rec g i l = if i < l then g (i+1) l else l

g 0 100000000;;

O mesmo resultado, mas compilação diferente.

Este é o f parece em quando traduzido para C #:

int f(int i, int l)
{
  while(true)
  {
    int num = i;
    if(num >= l)
      return l;
    int i = num;
    l = l;
    i = i + 1;
  }
}

g , no entanto é traduzido para o seguinte:

int g(int i, int l)
{
  while(i < l)
  {
    l = l;
    i++;
  }
  return l;
}

É interessante que duas funções que são fundamentalmente os mesmos são prestados de forma diferente pelo compilador F #. Ele também mostra que o compilador F # tem a otimização de recursiva. Assim, este ciclo deve até que eu atinja o limite de inteiros de 32 bits.

Answer 6

De acordo com esta discussão, torno de 5.000.000 com java , 1GB de RAM. (E que, com a versão 'cliente' do hotspot)

Foi com um pilha (-Xss) de 300Mo.

Com um -server opção , que poderia ser aumentada.

Também pode-se tentar otimizar o compilador ( com JET por exemplo) para reduzir o empilhar sobrecarga em cada camada.

Answer 7

Em alguns casos patológicos não (como a sua), (mais recente) Lua usará cauda chamada recursão , ie. ela só vai saltar sem enviar dados na pilha. Assim, o número de loops de recursão pode ser quase ilimitada.

Testado com:

function f(i, l)
    if i < l then
        return f(i+1, l)
    end
    return i
end

local val1  = arg[1] or 1
local val2  = arg[2] or 100000000
print(f(val1 + 0, val2 + 0))

Também com:

function g(i, l)
    if i >= l then
        return i
    end
    return g(i+1, l)
end

e ainda tentou cross-recursão (f chamando g e g chamando f ...).

No Windows, Lua 5.1 usos em torno 1.1MB (constantes) para executar este, acabamentos em poucos segundos.

Answer 8

Running 1.9.2dev rubi (2010-07-11 revisão 28618) [x86_64-darwin10.0.0] em um macbook branco mais velho:

def f
  @i += 1
  f
end

@i = 0

begin
  f
rescue SystemStackError
  puts @i
end

saídas de 9353 para mim, o que significa Rubi craps para fora com menos de 10.000 chamadas na pilha.

Com cross-recursão, tais como:

def f
  @i += 1
  g
end

def g
  f
end

que craps para fora na metade do tempo, em 4677 (~ = 9353/2).

Eu posso espremer mais algumas iterações envolvendo a chamada recursiva em um proc:

def f
  @i += 1
  yield
end

@i = 0
@block = lambda { f(&@block) }

begin
  f(&@block)
rescue SystemStackError
  puts @i
end

que se levanta para 4850 antes erroring fora.

Answer 9

Visual Dataflex vai estouro de pilha.

Answer 10

Eu sou muito fã de programação funcional, e uma vez que a maioria desses langauges implementar otimização de chamada de cauda, ??você pode recurse tanto quanto você gosta :-P

No entanto, praticamente, eu tenho que usar um monte de Java e usar Python muito também. Não faço ideia o limite de Java tem, mas para Python eu tinha realmente planejado (mas ainda não tiver feito isso) para implementar um decorador que chamaria cauda otimizar a função decorados. Eu estava planejando isso não a recursão otimizar, mas, principalmente, como um exercício de remendar dinamicamente Python bytecode e aprender mais sobre o funcionamento interno Pythons. Heres alguns links itneresting: http://lambda-the-ultimate.org/node/1331 e http://www.rowehl.com/blog/?p=626

Answer 11

Há uma maneira de aperfeiçoar o código Perl, para torná-lo usar uma pilha tamanho constante. Você pode fazer isso usando uma forma especial de goto.

sub f{
  if( $_[0] < $_[1] ){

    # return f( $_[0]+1, $_[1] );

    @_ = ( $_[0]+1, $_[1] );
    goto &f;

  } else {
    return $_[0]
  }
}

Quando a primeira chamada será alocar espaço na pilha. Em seguida, ele vai mudar seus argumentos, e reiniciar o sub-rotina, sem acrescentar mais nada para a pilha. Será, portanto, fingir que nunca chamou sua auto, transformando-o em um processo iterativo.

---

Você também pode usar o Sub :: Chamada :: Recorrência módulo. O que torna o código mais fácil de entender, e mais curto.

use Sub::Call::Recur;
sub f{
  recur( $_[0]+1, $_[1] ) if $_[0] < $_[1];
  return $_[0];
}

Answer 12

clojure fornece um formulário especial para recursão de cauda "recorrência" isso só pode ser utilizado em locais cauda da ast. Caso contrário, ele se comporta como java e provavelmente vai jogar um StackverflowException.