Os compiladores podem converter lógica recursiva em lógica não recursiva equivalente?

15

Eu tenho aprendido F # e está começando a influenciar como eu penso quando estou programando C #. Para esse fim, uso a recursão quando sinto que o resultado melhora a legibilidade e não consigo imaginá-lo acabar com um estouro de pilha.

Isso me leva a perguntar se os compiladores poderiam ou não converter automaticamente funções recursivas em um formato não recursivo equivalente?

Anodeto de Aaron
fonte
otimização de chamada de cauda é um bom se exemplo básico, mas que só funciona se você tiver return recursecall(args);para a recursividade, o material mais complexo é possível através da criação de uma pilha explícita e enrolando-a para baixo, mas eu duvido que eles vão
catraca aberração
@ anormal catraca: Recursão não significa "computação que está usando uma pilha".
Giorgio
1
@Giorgio eu sei, mas uma pilha é a maneira mais fácil de converter recursão para um loop
aberração catraca

Respostas:

21

Sim, alguns idiomas e complementadores converterão a lógica recursiva em lógica não recursiva. Isso é conhecido como otimização de chamada final - observe que nem todas as chamadas recursivas são otimizadas para chamada final. Nessa situação, o compilador reconhece uma função do formulário:

int foo(n) {
  ...
  return bar(n);
}

Aqui, o idioma é capaz de reconhecer que o resultado retornado é o resultado de outra função e alterar uma chamada de função com um novo quadro de pilha em um salto.

Perceba que o método fatorial clássico:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

não é otimizado para chamada final devido à inspeção necessária no retorno.

Para tornar essa chamada final otimizável,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Compilando esse código com gcc -O2 -S fact.c(o -O2 é necessário para ativar a otimização no compilador, mas com mais otimizações de -O3 fica difícil para um ser humano ler ...)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

Pode-se ver no segmento .L4, em jnevez de um call(que faz uma chamada de sub-rotina com um novo quadro de pilha).

Observe que isso foi feito com C. A otimização de chamada de cauda em java é difícil e depende da implementação da JVM - tail-recursion + java e tail-recursion + optimization são bons conjuntos de tags para navegar. Você pode achar que outros idiomas da JVM são capazes de otimizar melhor a recursão da cauda (tente o clojure (que requer que a repetição para otimizar a chamada da cauda) ou scala).

Comunidade
fonte
1
Não tenho certeza de que é isso que o OP está pedindo. Só porque o tempo de execução consome ou não o espaço da pilha de uma certa maneira, não significa que a função não seja recursiva.
1
@MattFenwick Como assim? "Isso me leva a perguntar se os compiladores poderiam ou não converter automaticamente funções recursivas para uma forma não recursiva equivalente" - a resposta é "sim em determinadas condições". As condições são demonstradas e existem algumas dicas em outros idiomas populares com otimizações de chamada de cauda que mencionei.
9

Pisar com cuidado.

A resposta é sim, mas nem sempre, e nem todos eles. Esta é uma técnica que usa alguns nomes diferentes, mas você pode encontrar algumas informações bastante definitivas aqui e na wikipedia .

Prefiro o nome "Otimização de chamada de cauda", mas há outros e algumas pessoas confundem o termo.

Dito isto, há algumas coisas importantes a serem realizadas:

  • Para otimizar uma chamada final, a chamada final requer parâmetros conhecidos no momento em que a chamada é feita. Isso significa que, se um dos parâmetros for uma chamada para a própria função, ela não poderá ser convertida em um loop, porque isso exigiria o aninhamento arbitrário do referido loop, que não pode ser expandido no tempo de compilação.

  • O C # não otimiza confiavelmente as chamadas de cauda. O IL tem a instrução de fazer isso que o compilador F # emitirá, mas o compilador C # emitirá inconsistentemente e, dependendo da situação do JIT, o JIT pode ou não fazê-lo. Todas as indicações são de que você não deve confiar na otimização de suas chamadas finais em C #, o risco de transbordamento ao fazê-lo é significativo e real

Jimmy Hoffa
fonte
1
Tem certeza de que é isso que o OP está pedindo? Como eu postei na outra resposta, apenas porque o tempo de execução consome ou não o espaço da pilha de uma certa maneira, não significa que a função não seja recursiva.
1
@MattFenwick, na verdade, é um ótimo ponto, em termos reais depende. O compilador F # que emite instruções de chamada de cauda está mantendo a lógica recursiva completamente, está apenas instruindo o JIT a executá-lo da maneira que substitui o espaço da pilha, em vez do espaço da pilha. crescendo, no entanto, outros compiladores podem literalmente compilar em um loop. (Tecnicamente, o JIT está compilando a um loop ou moda possivelmente até argolas se o loop é frente total até)
Jimmy Hoffa