Skip to main content
Correções gramaticais e deixei o código um pouco mais legível.
Fonte Link

Como outros já mencionaram, C# não te dá uma garantia de que uma recursão de causacauda vai ser otimizada. Eu sou muito fã de recursão de cauda mas acho que que você está focando um poncopouco 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 inicioinício do loop.

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

  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 dede 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.

Como outros já mencionaram, C# não te dá uma garantia de que uma recursão de causa vai ser otimizada. Eu sou muito fã de recursão de cauda mas acho que que você está focando um ponco 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 inicio 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;
   }
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 pate 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:

  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.

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

  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.

Fonte Link
hugomg
  • 9,1mil
  • 27
  • 39

Como outros já mencionaram, C# não te dá uma garantia de que uma recursão de causa vai ser otimizada. Eu sou muito fã de recursão de cauda mas acho que que você está focando um ponco 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 inicio 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 pate 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.