Função recursiva JavaScript

Resumo : neste tutorial você aprenderá como usar a técnica de recursão para desenvolver uma função recursiva JavaScript, que é uma função que chama a si mesma.

Introdução às funções recursivas JavaScript

Uma função recursiva é uma função que chama a si mesma até que não o faça. Essa técnica é chamada de recursão.

Suponha que você tenha uma função chamada recurse(). A recurse()função é recursiva se chama a si mesma dentro de seu corpo, assim:

function recurse() {
    // ...
    recurse();
    // ...
}
Linguagem de código:  JavaScript  ( javascript )

Uma função recursiva sempre tem uma condição para parar de chamar a si mesma. Caso contrário, ele se chamará indefinidamente. Portanto, uma função recursiva normalmente se parece com o seguinte:

function recurse() {
    if(condition) {
        // stop calling itself
        //...
    } else {
        recurse();
    }
}Linguagem de código:  JavaScript  ( javascript )

Geralmente, você usa funções recursivas para dividir um grande problema em problemas menores. Normalmente, você encontrará funções recursivas em estruturas de dados como árvores binárias e gráficos e algoritmos como pesquisa binária e quicksort.

Exemplos de funções recursivas JavaScript

Vejamos alguns exemplos de uso de funções recursivas.

1) Um exemplo simples de função recursiva JavaScript

Suponha que você precise desenvolver uma função que faça a contagem regressiva de um número especificado até 1. Por exemplo, para fazer a contagem regressiva de 3 até 1:

3
2
1

O seguinte mostra a countDown()função:

function countDown(fromNumber) {
    console.log(fromNumber);
}

countDown(3);Linguagem de código:  JavaScript  ( javascript )

Isso countDown(3)mostra apenas o número 3.

Para fazer a contagem regressiva do número 3 a 1, você pode:

1. mostre o número 3.
2. e ligue para o countDown(2)que mostra o número 2.
3. e ligue para o countDown(1)que mostra o número 1.

O seguinte altera countDown()para uma função recursiva:

function countDown(fromNumber) {
    console.log(fromNumber);
    countDown(fromNumber-1);
}

countDown(3);Linguagem de código:  JavaScript  ( javascript )

Isso countDown(3)será executado até que o tamanho da pilha de chamadas seja excedido, assim:

Uncaught RangeError: Maximum call stack size exceeded.Linguagem de código:  JavaScript  ( javascript )

… porque não tem condição de parar de se chamar.

A contagem regressiva irá parar quando o próximo número for zero. Portanto, você adiciona uma condição if da seguinte maneira:

function countDown(fromNumber) {
    console.log(fromNumber);

    let nextNumber = fromNumber - 1;

    if (nextNumber > 0) {
        countDown(nextNumber);
    }
}
countDown(3);Linguagem de código:  JavaScript  ( javascript )

Saída:

3
2
1

Parece countDown()funcionar conforme o esperado.

No entanto, conforme mencionado no tutorial Tipo de função , o nome da função é uma referência ao objeto de função real.

Se o nome da função estiver definido em nullalgum lugar do código, a função recursiva irá parar de funcionar.

Por exemplo, o código a seguir resultará em um erro:

let newYearCountDown = countDown;
// somewhere in the code
countDown = null;
// the following function call will cause an error
newYearCountDown(10);Linguagem de código:  JavaScript  ( javascript )

Erro:

Uncaught TypeError: countDown is not a functionLinguagem de código:  JavaScript  ( javascript )

Como funciona o roteiro:

• Primeiro, atribua o countDownnome da função à variável newYearCountDown.
• Segundo, defina a countDownreferência da função como null.
• Terceiro, chame a newYearCountDownfunção.

O código causa um erro porque o corpo da countDown()função faz referência ao countDownnome da função, que foi definido nullno momento da chamada da função.

Para corrigir isso, você pode usar uma expressão de função nomeada da seguinte maneira:

let countDown = function f(fromNumber) {
    console.log(fromNumber);

    let nextNumber = fromNumber - 1;

    if (nextNumber > 0) {
        f(nextNumber);
    }
}

let newYearCountDown = countDown;
countDown = null;
newYearCountDown(10);Linguagem de código:  JavaScript  ( javascript )

2) Exemplo de cálculo da soma de n números naturais

Suponha que você precise calcular a soma dos números naturais de 1 a n usando a técnica de recursão. Para fazer isso, você precisa definir sum()recursivamente da seguinte forma:

sum(n) = n + sum(n-1)
sum(n-1) = n - 1 + sum(n-2)
...
sum(1) = 1

O seguinte ilustra a sum()função recursiva:

function sum(n) {
  if (n <= 1) {
    return n;
  }
  return n + sum(n - 1);
}Linguagem de código:  JavaScript  ( javascript )

Caso base:

• A função começa com uma instrução “if” que verifica se né menor ou igual a 1.
• Se nfor 1 ou menos, a função simplesmente retorna n. Este é o caso base, que serve como condição de parada para a recursão.

Caso recursivo:

• Se o caso base não for atendido (ou seja, nfor maior que 1), a função entra no bloco após a ifinstrução.
• A função retorna a soma ne o resultado da chamada a si mesma com o argumento (n - 1). É aqui que a recursão acontece.

Como funciona:

• Por exemplo, se você chamar sum(3), a função primeiro verifica se 3 é menor ou igual a 1 (caso base não atendido).
• Como não é o caso base, ele calcula 3 + sum(2). Agora, ele se autodenomina com o argumento 2.
• Na próxima chamada recursiva com sum(2), ele calcula 2 + sum(1).
• Novamente, na próxima chamada recursiva com sum(1), ele atinge o caso base e retorna 1.
• Agora, as chamadas anteriores estão resolvidas: 2 + 1dá 3 e 3 + 3dá o resultado final de 6.

Terminação:

• A recursão continua acontecendo, reduzindo o problema a subproblemas menores até atingir o caso base.
• Uma vez atingido o caso base, a função começa a se desenrolar, combinando os resultados de cada nível de recursão até que o resultado final seja obtido.

Resumo

• Uma função recursiva é uma função que chama a si mesma até que não o faça
• Uma função recursiva sempre possui uma condição que impede a função de chamar a si mesma.