15

No .Net, eu sei que é possível fazer chamadas de causa porque o compilador do F#, ao otimizar o código, transforma uma função com recursão de cauda em uma função com um laço, evitando assim, estouros de pilha. Para deixar mais claro usarei como exemplo uma função de fatorial.

Em F#:

let rec fatorial_iter n r : int64 =
  if n <= 1L then r else fatorial_iter (n - 1L) (n * r)

let fatorial n = fatorial_iter n 1L

Isso evita estouros de pilha pois a pilha sempre terá o mesmo tamanho após a otimização. Ilustrando uma chamada para fatorial(5):

fatorial(5, 1)   -> fatorial(5 - 1, 5 * 1)  ->
fatorial(4, 5)   -> fatorial(4 - 1, 4 * 5)  ->
fatorial(3, 20)  -> fatorial(3 - 1, 3 * 20) ->
fatorial(2, 60)  -> fatorial(2 - 1, 2 * 60) ->
fatorial(1, 120) -> 120

Se tentarmos fazer isso em C#, podemos também fazer a chamada recursiva na cauda, como nesse exemplo:

static long Fatorial(int n, long r = 1) {
    return n <= 1 ? r : Fatorial(n - 1, n * r);
}

Mas o compilador do C# não pode otimizar esse código (ao menos não ainda, usando o .Net Framework 4.5).

Existe algum modo, sem perder a imutabilidade do código, de fazer com que essa função não possa causar um estouro de pilha?

1
  • Achei um artigo que mostra isso manipulando a IL, mas é meio fora de mão editar a IL para toda função. Outra solução para não ocorrer stackoverflow é usar uma Thread com o parâmetro maxStackSize no construtor. Dependendo da profundidade de recursão isso não ajuda.
    – user178974
    Commented 4/05/2020 às 21:42

4 Respostas 4

7

Como outros já mencionaram, C# não te dá uma garantia de que uma recursão de cauda vai ser otimizada. Eu sou muito fã de recursão de cauda mas acho que que você está focando um pouco no sentido errado - eu acho que o controle de fluxo flexível é um ponto mais crucial da recursão de cauda do que a imutabilidade e isso muda um pouco a maneira de abordar esse problema.

Num caso de loop simples com o do seu exemplo, usar recursão de cauda acaba sendo tão mutável e baixo nível quanto escrever seu código usando gotos. Em cada passo você tem que atualizar o acumulador e o contador e dizer que vc vai fazer um jump de volta pro início do loop.

  int acc = 1;
  int i = N;
loop:
   if (i >= 0) {
     // finge que pode usar atribuição múltipla estilo Python
     i, acc = i-1, acc*i; goto loop;
   } else {
     return acc;
   }

A única vantagem da recursão de cauda comparada com os gotos é a atribuição de mais de uma variável num passo só e que o compilador vai te avisar se você esquecer de falar o valor novo pra uma das variáveis. De qualquer forma, um for loop acaba sendo mais estruturado e alto nível, já que vc só precisa cuidar da lógica pra atualizar o produto e a atualização do contador e os gotos vem de graça. É um pouco similar a programar usando um fold ao invés de recursão de cauda

int acc = 1;
for (int i = N; i >= 0; i--){
   acc *= i;
}

Só que recursão de cauda não serve só pra fazer loops simples em que um função chama ela mesma. A parte onde a recursão de cauda faz mais diferença é quando você tem mais de uma função mutuamente recursiva. Um exemplo forçado é essa máquina de estados definida em Haskell:

par 0 = True
par n = impar (n-1)

impar 0 = False
impar m = par (m-1)

O equivalente disso sem recursão de causa é uma máquina de estados:

  int n;
  int m;
par:
  if (n == 0) {
    return true;
  } else {
    m = n - 1;
    goto impar;
  }
impar:
  if (n == 0) {
    return false;
  } else {
    n = m - 1;
    goto par;
  }

No entanto nessa versão todas as funções tem que ser combinadas num trecho de código só, o que fere a encapsulação. Por exemplo, nós precisamos declarar todas as variáveis de parâmetro lá no topo, o que torna possível que elas sejam usadas no lugar errado.

Além disso, a recursão de cauda também está presente quando chamamos uma função que nos foi passada como parâmetro. Isso é equivalente a um goto computado e não pode ser traduzido em um loopzinho estático.

Nesses últimos dois casos é quando o suporte da linguagem para recursão de cauda faz mais falta. Se você tiver que fazer algo equivalente, o mais próximo vai ser usar o um padrão "trampolim", mas é meio ineficiente e bem chatinho de usar.

1
  • Gostei da resposta. De fato, eu buscava a recursão de causa exatamente por causa do código mais conciso quando comparado ao uso de pulos e laços. O conceito do trampolim eu achei interessante, mas aparentemente é mais uma perda de produtividade do que usar laços. Commented 3/02/2014 às 20:39
4

Este tipo de otimização está presente apenas no JIT de 64-bit em modo Release.

Teste seu código em x64 no modo Release e o StackOverflow não mais ocorrerá.

E, claro, nunca confie em uma otimização do JIT. Você não sabe em qual framework, plataforma ou arquitetura seu código irá rodar.

Código testado aqui:

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine(Fatorial(2000000));
    }

    static long Fatorial(int n, long r = 1)
    {
        return n <= 1 ? r : Fatorial(n - 1, n * r);
    }
}
5
  • Agora fiquei confuso. Se eu compilo meu código para o Framework 4.5 como Release, ele poderá rodar em versões mais antigas do Framework? Commented 3/02/2014 às 19:07
  • Dependendo do que você está fazendo, sim... Este código é código de .net 1.0, portanto a IL é a mesma. Testei isso no .net 3.5 (era possível rodar no 2.0 sem problemas algumas coisas que não eram novas, e até algumas novas como Extension Methods, já que não foi gerada nenhuma IL nova pra isso). O fato é que existe Mono, x86, x64, etc...
    – JCKödel
    Commented 3/02/2014 às 19:08
  • 2
    E, a propósito: eu disse que só funciona em Release x64 porque cada arquitetura (x64/x86/arm) possui seu próprio JIT. Tem coisas que só são otimizadas em um JIT específico, como este caso. Faça exatamente o mesmo código e só mude x64 para AnyCPU e dará exceção. Mude para DEBUG e dará exceção.
    – JCKödel
    Commented 3/02/2014 às 19:10
  • Entendi. Infelizmente estou sem x64 aqui para testar, e nem sempre podemos contar com ele. Será que não existe um método sem depender do x64? Que eu saiba outras linguagens não dependem de x64 (O que não faria muito sentido, também)... Commented 3/02/2014 às 19:14
  • Como eu disse, NUNCA confie em otimizações, pois elas podem não estar presentes. Aqui a única forma é remover a recursividade. Isso garantiria que o método não seria chamado e então o endereço de retorno não seria colocado na pilha e a mesma não estouraria =)
    – JCKödel
    Commented 3/02/2014 às 19:18
1

Neste caso a única forma garantida de não causar um StackOverflow seria usar um algoritmo não recursivo. Por exemplo:

static long Fatorial(int n) 
{
    long r = 1;

    for (; n > 1; n--)
    {
        r *= n;
    }

    return r;
}
1
  • Eu fiz um algoritmo parecido com esses, mas minha ideia era usar imutabilidade mesmo. for (long i = n, j = 1; ; j *= i--) if (i <= 1) return j; Commented 3/02/2014 às 19:49
0

Posso estar falando besteira agora, mas acredito que a resposta do JCKödel está incorreta.

Acredito que você só conseguiu computar um número fatorial tão grande justamente porque está utilizando a arquitetura de 64 bits e não por causa de nenhuma otimização.

OBS: Tive que postar como resposta, não posso "comentar" em outras respostas ainda, não tenho reputação suficiente.

2
  • Você está dando uma informação pertinente à pergunta que não está contida em outra resposta, então creio que não há problema. Eu não tenho um sistema x64 para testar, mas se tiveres, podes comparar os dois ILs gerados para ver se há uma diferença. Commented 3/02/2014 às 21:05
  • 1
    Tem certeza? O stack overflow tem a ver com o tamanho da entrada, não com o tamanho da resposta obtida (e o fatorial vai dar overflow num int de 64 bits rapidinho de qquer forma). E esse artigo aqui indica que o JIT de 32 e 64 bits sao diferentes mesmo: blogs.msdn.com/b/jomo_fisher/archive/2007/09/19/…
    – hugomg
    Commented 4/02/2014 às 4:06

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .