Publicado em por Paulo Künzel

Recursão e a Pilha (Stack)

Se você não é novato em programação, e até aqueles que já fizeram algumas cadeiras/módulos de programação, provavelmente já ouviu os termos recursão e pilha.

Recursão é um método de programação onde o código executa uma função que chama a si mesma um número X de vezes para resolver um problema que apresenta um padrão repetitivo. Ela tem uma funcionalidade muito similar aos loops, mas sem explicitamente mostrar que está fazendo o mesmo trabalho repetidas vezes.

Quais as vantagens de usar recursão?

Essa é uma duvida bem comum, devo iterar? ou usar a recursão? Nos seguintes casos, seria melhor usar a recursão:

  • Reduzir o código e deixar torna-lo mais simples de ler: Para quem não está acostumado isso parece estranho, mas em grande maioria dos casos é possível escrever a mesma lógica com um número menor de linhas, tornando-o mais fácil de entender e debugar.
  • Quando você está trabalhando com uma linguagem funcional: Linguagens funcionais lidam com recursão muito melhor que imperativas. Já as linguagens imperativas lidam com iteração melhor, então leve isso em consideração quando estiver desenvolvendo seu programa ou script
  • A recursão é melhor na travessia de árvores. Este é um pouco mais avançado. Uma versão extremamente simplificada do que isso significa é a seguinte: Uma árvore é uma coleção de objetos que estão ligados um ao outro (imagine folhas em uma árvore conectada por ramos que por sua vez estão conectados a outros ramos até as raízes). Uma das maneiras mais eficientes de percorrer essas árvores ao procurar por uma folha (ou nó) específica é seguir, de maneira recursiva, uma única ramificação até o final dessa ramificação até encontrar o valor que você está procurando.

Exemplos de Recursão

Digamos que queremos criar algo simples, como uma função que faz que calcula a potencia N de um valor X (exemplo 2^3 = 8, X^N = 8).

let valor = potencia(2, 2);
//Exibe o valor 4
console.log(valor);

valor = potencia (2, 3);
//Exibe o valor 8
console.log(valor);

valor = potencia (2, 4);
//Exibe o valor 16
console.log(valor);

Importante: Este é apenas um exemplo, utilizem o objeto Math do JavaScript para esse tipo de calculo.

Poderíamos faze-lo com o Loop For

function potencia(x, n) {
  let result = 1;

  // Multiplica o resultado X N vezes para obter a resposta
  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

Console.log(potencia(2, 3) ); // 8

Agora utilizando a recursão

function potencia(x, n) {
  if (n == 1) {
    // Quando n finalmente é 1, não executa mais a recursão para finalizar o calculo
    return x;
  } else {
    //obtém a resposta do próximo pedaço do calculo chamando a função novamente
    let recursao = potencia(x, n - 1)

    return x * recursao;
  }
}

console.log(potencia(2, 3) ); // 8

Então, o que está acontecendo exatamente?

No caso da recursão deste algoritmo, quebramos a lógica em pequenos passos que fazem a multiplicação de X pelo resultado anterior até chegar em um ponto onde não é feita mais a chamada recursiva. Quando isso ocorre, as funções começam a ser retornadas e resolvidas.

No caso do exemplo acima, se fizéssemos 2^3, a ultima recursão ser no n==1 que retornaria 2 para a função anterior. Ela multiplicaria 2 * 2, resultando em quatro e retornaria para a primeira chamada que resultaria em 8 e terminaria a função.

A recursão normalmente possui menos linhas de código

A recursão normalmente é menor que a iteração. Abaixo está o mesmo exemplo que fizemos acima, mas usando o mínimo de comandos, retornos e de linhas possíveis.

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

Pilha

Uma pilha é uma região na memória, que opera no modo First-In-Last-Out, exatamente como a pilha que você deve ter estudado em estrutura de dados. Para cada nova ação que precisa ser executada, esta é “empilhada” e terá que ser processada antes da ação anterior voltar a ser trabalhada.

Note que as pilhas não tem tamanho infinito e quando você cria uma função recursiva muito grande ou mau feita, causará o famoso erro que chamamos de stack-overflow

Para ter uma ideia, execute o seguinte código

let i=0;
function estourarPilha() {
    console.log(i++);
    estourarPilha();
}
estourarPilha();

Para cada navegador os valores serão diferentes, mas eventualmente eles irão parar de funcionar pois você conseguiu quebra-los. Mas fique tranquilo, basta reinicia-lo que tudo voltará ao normal.

Conclusão

Esta foi uma introdução bem básica sobre recursão e a pilha no JavaScript, espero que você tenha aprendido com o exemplo e caso tenha alguma duvida ou sugestão por favor deixe seu comentário abaixo.

Deixe um comentário