Recursividade

1. O que é

Recursão é resolver um problema quebrando-o em versões menores dele mesmo, até chegar a uma tão pequena que a resposta é óbvia. Em código: uma função que chama a si mesma.

function recursiva() {
  if (condição) {
    // CASO BASE: para de se chamar
  } else {
    recursiva();   // PASSO RECURSIVO: chama de novo, com um problema menor
  }
}

• Caso base: a condição de parada. Sem ele, a função se chama para sempre.
• Sem caso base, o JavaScript desiste depois de ~10 mil chamadas e dá o erro Maximum call stack size exceeded (estouro da pilha de chamadas, o famoso stack overflow).
• Cada chamada precisa chegar mais perto do caso base.

2. Exemplo clássico: fatorial

Fatorial (5!) é multiplicar de 1 até o número: 5 x 4 x 3 x 2 x 1 = 120. Repare que 5! é 5 x 4!: o problema contém uma versão menor dele mesmo.

function fatorial(x) {
  if (x <= 1) {
    return 1;                  // caso base
  }
  return x * fatorial(x - 1);  // passo recursivo
}

fatorial(5);   // 120

As chamadas descem até o caso base e depois sobem devolvendo os resultados, como caixas uma dentro da outra:

fatorial(5) = 5 * fatorial(4)
                  4 * fatorial(3)
                      3 * fatorial(2)
                          2 * fatorial(1)
                              1            <- caso base

Código: js/recursividade.js, seção 1.

3. Contagem regressiva: for x recursão

// Com for: o laço repete
for (let cont = 10; cont >= 1; cont--) {
  console.log(cont);
}

// Com recursão: a função se repete
function regressiva(cont, num) {
  console.log(cont);
  if (num < cont) {               // enquanto não chegou no fim...
    regressiva(cont - 1, num);    // ...chama de novo com um a menos
  }
}

regressiva(10, 1);   // 10 9 8 7 6 5 4 3 2 1

Cuidado com cont-- na chamada: regressiva(cont--, num) entrega o valor antes de diminuir. A função recebe 10 de novo, para sempre, e estoura a pilha. Funciona com --cont (diminui antes) ou, mais claro, com cont - 1.

Código: js/recursividade.js, seção 2.

4. Recursão ou repetição? Onde se usa de verdade

// Contar arquivos numa pasta que tem pastas dentro (não se sabe quantos níveis)
function contarArquivos(pasta) {
  let total = pasta.arquivos.length;
  for (let sub of pasta.subpastas) {
    total += contarArquivos(sub);   // cada subpasta é o MESMO problema, menor
  }
  return total;                     // caso base: pasta sem subpastas
}

Para contar de 10 até 1, o for é mais simples e mais rápido. A recursão brilha quando o problema tem formato de árvore.

Desafio: fatorial sem recursão

Escreva fatorialComFor(x) usando um laço for em vez de recursão. Dica: comece com resultado = 1 e vá multiplicando (variável acumuladora, página Repetição).

Escreva sua resposta em js/recursividade.js, seção 3 (está em branco).

// sua resposta aqui

Quando quiser a solução, é só pedir.