Introdução
Recursão é um conceito poderoso em programação: uma função que chama a si mesma.
Pode ser um pouco complicado de entender no começo, mas, depois que você domina os fundamentos, ela se torna uma ferramenta valiosa para resolver problemas complexos.
Neste tutorial, vamos explorar a recursão em JavaScript com exemplos fáceis de entender.
O que é recursão?
A recursão acontece quando uma função chama a si mesma, de forma direta ou indireta.
É parecido com um laço, mas envolve dividir um problema em subproblemas menores e mais fáceis de lidar.
Exemplo 1: contagem regressiva
Vamos começar com um exemplo simples: uma função de contagem regressiva.
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
Neste exemplo:
-
Caso base: quando
num fica menor ou igual a 0, a função imprime "Blastoff!" e para de chamar a si mesma.
-
Caso recursivo: a função imprime o
num atual e chama a si mesma com num - 1.
Exemplo 2: fatorial
Agora, vamos ver um exemplo clássico de recursão: calcular o fatorial de um número.
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
Neste exemplo:
-
Caso base: quando
n é 0 ou 1, a função retorna 1.
-
Caso recursivo: a função multiplica
n pelo fatorial de n - 1.
Conceitos-chave
Caso base
Toda função recursiva precisa ter pelo menos um caso base, uma condição em que a função para de chamar a si mesma.
Sem um caso base, a recursão continuaria indefinidamente, causando um estouro de pilha.
Caso recursivo
O caso recursivo define como a função chama a si mesma com uma versão menor ou mais simples do problema.
Prós e contras da recursão
Prós:
- Solução elegante para certos problemas.
- Imita o conceito de indução matemática.
Contras:
- Pode ser menos eficiente que soluções iterativas.
- Pode causar estouro de pilha em recursões muito profundas.
Conclusão
A recursão é uma técnica valiosa que pode simplificar problemas complexos dividindo-os em subproblemas menores e mais fáceis de lidar.
Entender os casos base e os casos recursivos é essencial para implementar soluções recursivas eficazes em JavaScript.
Saiba mais:
Instruções
Você tem uma pizzaria e oferece três tipos de pizza:
- Margherita: $7
- Caprese: $9
- Formaggio: $10
Se os clientes quiserem, podem adicionar um número ilimitado de opções extras: "ExtraSauce" por $1 ou "ExtraToppings" por $2.
Sua tarefa é escrever um código que ajude o cliente a descobrir o custo para ele.
Calcule o preço de uma pizza
Recebendo o nome da pizza como primeiro argumento e um número ilimitado de opções adicionais, calcule o preço da pizza em dólares.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
Calcule o preço total de um pedido
Sua função é chamada com uma lista de PizzaOrders e deve retornar o preço total do pedido em dólares.
Cada PizzaOrder tem uma propriedade pizza, que é o nome da pizza, e uma propriedade extras, que é a lista de opções extras.
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
Você vai perceber que não pode escrever isso usando recursão, pois um teste com uma quantidade enorme de pedidos vai lançar um Maximum call stack size exceeded.
Não se preocupe, isso é intencional. Tente implementar essa função usando um laço imperativo!
Você tem muitas opções, incluindo, mas não se limitando a, usar reduce ou um laço for.
Quando o intérprete de JavaScript está executando o código JavaScript, ele mantém o controle de quais funções foram iniciadas (chamadas) em uma estrutura de dados chamada "pilha".
Quando a função retorna (termina), ela é removida da pilha.
No entanto, essa pilha tem um tamanho limitado.
O erro mais comum é uma função recursiva que nunca termina.
Cada chamada é colocada na pilha, mas antes que ela retorne, outra chamada é colocada na pilha.
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
O rastreamento da pilha desse erro mostra a mesma linha repetidas vezes, o que faz sentido, porque a função chama a si mesma.
Embora não tenha uma aplicação prática real na maioria dos casos, você pode descobrir o quão alta essa pilha pode ficar.
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
Existem apenas duas soluções viáveis para um erro de pilha de chamadas causado por uma função recursiva síncrona:
- garanta que as funções retornem antes que o limite da pilha seja atingido, geralmente adicionando ou corrigindo um caso base.
- reescreva a função recursiva como um laço imperativo, que executará o corpo do laço sem precisar entrar em uma função, e assim sem aumentar a pilha.
Exercício de aprendizagem
