Descondificando CC

Recursão em Javascript

August 25, 2019

Javascript
Avançado

A recursão é o ato de auto invocação de uma função. A recursão é usada para resolver problemas que contêm subproblemas menores.

  • Propriedades de função recursiva:

    • Mesma operação é executade multiplas vezes com entradas diferentes.
    • Em cada passo tentamos fazer com que o problema seja menor.
    • Precisa ter uma condição de base, que fará com que a recursão termine.
    • Precisa ter uma condição de recursão, que fará com que a recursão continue.
  • Formato de uma função recursiva:

    • Caso Recursivo: Caso em que a função se repete.
    • Caso de Base: Caso em que a função nao se repete.

Porquê aprender Recursão?

Porque torna o código fácil de escrever (comparado ao iterativo) sempre que um determinado problema pode ser dividido em subproblema similar

A recursão é muito utilizada em técnicas como Divisão e Conquista, Programação Dinamica, etc.

Exemplo:

function simplesRecursao(parametro) {
  if (condicaoDeBase) return "termine a execução";
  else {
    let parametroModificado = ...;
    return simplesRecursao(parametroModificado);
  }
}

Como é que a Recursão funciona internamemente?

Ao invocarmos funções recursivas no JavaScript, nós armazenamos tudo o que precisa ser feito na Stack(pilha) para depois voltar e terminar tudo.

Pois então, o que é uma Stack ? 👿

Dizemos sempre que uma imagem vale mais do que mil palavras.

Uma Stack é nada mais do que um compartimento de armazenamento em pilha que respeita uma regra, esta regra chama-se LIFO(Last In, First Out), em português Ultimo Dentro, Primeiro Fora.

Na imagem acima podemos ver que o número dois é o ultimo a ser adicionado na pilha e o primeiro a ser removido.

Vejamos as seguintes funções e como elas seriam adicionadas na pilha.

function funcaoPrincipal() {
  segundaFuncao();
  console.log("funcaoPrincipal()");
}

function segundaFuncao() {
  terceiraFuncao();
  console.log("segundaFuncao()");
}

function terceiraFuncao() {
  quartaFuncao();
  console.log("terceiraFuncao()");
}

function quartaFuncao() {
  console.log("quartaFuncao()");
}

funcaoPrincipal();

A ordem de execução das funções acima criadas numa pilha seria:

4 - quartaFuncao()
3 - terceiraFuncao()
2 - segundaFuncao()
1 - funcaoPrincipal()

Após a execução completa da quartaFuncao() ela é então removida da pilha, e em seguida regressamos à terceiraFuncao() para terminar a sua execução e removê-la da pilha. Repetimos este processo até a funcaoPrincipal() ser complementamente executada e removida da pilha.

Agora que já sabemos como funciona a Stack, é hora de vermos un exemplo básico de uma função recursiva.

function contagemRegressiva(numero) {
  if (numero < 1) return;
  else contagemRegressiva(numero - 1);
  console.log("O número actual é:", numero);
}

function main() {
  contagemRegressiva(3);
  console.log("main()");
}

main();

O resultado que será imprimido no console será o seguinte:

O número actual é: 1
O número actual é: 2
O número actual é: 3
main()

Como pudemos observar aqui a implementação de uma função recursiva. Se olharmos atentamente veremos que ela obedece o formato de uma função recursiva, onde:

  • Caso de Base: caso o número for menor que 1, terminamos a execução
if (numero < 1) return;
  • Caso Recursivo: caso contrario, continuamos a execução, mas decrementando o parâmetro inicial
else contagemRegressiva(numero - 1);

No caso recursivo, podemos reparar que a função se auto-chama mas com um parâmetro diferente a cada chamada.

Vejamos um exemplo mais avançado onde calcularemos o factorial de um dado numero.

function factorial(numero) {
  if (numero === 0) return 1;
  else {
    return numero * factorial(numero - 1);
  }
}

factorial(5);

O resultado desta operação é obviamente: 120. Mas e então, qual seria a ordem de execução desta operação?

A execução desta operação na pilha seria da seguinta maneira:

1 * 1 - 1  (resultado após recursão)
1 * ? - 1  (resultado após recursão)
2 * ? - 2  (resultado após recursão)
3 * ? - 6  (resultado após recursão)
4 * ? - 6  (resultado após recursão)
5 * ? - 24 (resultado após recursão)

5 * 24 = 120;

Nesta operação, cada ? indica que o valor resultante da operação * factorial(numero - 1) é desconhecido antes da recursão, mas este será informado após a execução completa de cada função recursiva.