Introdução
A recursão é um conceito poderoso em programação que envolve uma função a chamar-se a si própria.
Pode ser um pouco difícil de perceber ao início, mas depois de compreenderes os fundamentos, torna-se uma ferramenta valiosa para resolver problemas complexos.
Neste tutorial, vamos explorar a recursão em JavaScript com exemplos fáceis de perceber.
O que é a recursão?
A recursão acontece quando uma função se chama a si própria, direta ou indiretamente.
É semelhante a um ciclo, mas envolve dividir um problema em subproblemas mais pequenos e mais fáceis de gerir.
Exemplo 1: contagem decrescente
Vamos começar com um exemplo simples: uma função de contagem decrescente.
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 deixa de se chamar a si própria.
-
Caso recursivo: a função imprime o
num atual e chama-se a si própria 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 devolve 1.
-
Caso recursivo: a função multiplica
n pelo fatorial de n - 1.
Conceitos-chave
Caso base
Todas as funções recursivas têm de ter pelo menos um caso base, uma condição em que a função deixa de se chamar a si própria.
Sem um caso base, a recursão continuaria indefinidamente, o que acabaria num stack overflow.
Caso recursivo
O caso recursivo define como a função se chama a si própria com uma versão menor ou mais simples do problema.
Vantagens e desvantagens da recursão
Vantagens:
- Solução elegante para certos problemas.
- Imita o conceito de indução matemática.
Desvantagens:
- Pode ser menos eficiente do que soluções iterativas.
- Pode levar a um stack overflow em recursões profundas.
Conclusão
A recursão é uma técnica valiosa que pode simplificar problemas complexos, dividindo-os em subproblemas mais pequenos e mais fáceis de gerir.
Compreender os casos base e os casos recursivos é essencial para implementar soluções recursivas eficazes em JavaScript.
Saber mais:
Instruções
Tens uma pizzaria e serves três tipos de pizza:
- Margherita: $7
- Caprese: $9
- Formaggio: $10
Se os clientes quiserem, podem acrescentar um número ilimitado de opções extra: "ExtraSauce" por $1 ou "ExtraToppings" por $2.
A tua tarefa é escrever código que ajude o cliente a calcular o custo.
Calcula o preço de uma pizza
Dado o nome da pizza como primeiro argumento, e um número ilimitado de opções extra, calcula o preço da pizza em dólares.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
Calcula o preço total de um pedido
A tua função recebe uma lista de PizzaOrders e deve devolver o preço total do pedido em dólares.
Cada PizzaOrder tem uma propriedade pizza (o nome da pizza) e uma propriedade extras (a lista de opções extra).
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
Vais perceber que não podes escrever isto com recursão, porque um teste com uma enorme quantidade de pedidos provoca um Maximum call stack size exceeded.
Não te preocupes, é intencional: experimenta implementar esta função com um ciclo imperativo!
Tens muitas opções, como, por exemplo, usar reduce ou um ciclo for.
Quando o intérprete de JavaScript está a executar o código JavaScript, vai registando as funções em que entrou (que começou a chamar) numa estrutura de dados chamada "pilha".
Quando a função termina (chega ao fim), é removida da pilha.
No entanto, esta pilha tem um tamanho limitado.
O erro mais comum é uma função recursiva que nunca termina.
Cada chamada é colocada na pilha e, antes de terminar, coloca lá outra chamada.
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
A stack trace deste erro mostra a mesma linha vezes sem conta, o que faz sentido, porque a função se chama a si própria.
Embora, na maioria dos casos, não tenha grande aplicação prática, podes descobrir até que ponto a pilha pode crescer.
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
Há apenas duas soluções viáveis para um erro de pilha de chamadas provocado por uma função recursiva síncrona:
- garantir que as funções terminam antes de a pilha atingir o limite, normalmente adicionando ou corrigindo um caso base.
- reescrever a função recursiva como um ciclo imperativo, que executa o corpo do ciclo sem ter de entrar numa função e, por isso, sem aumentar a pilha.
Exercício de aprendizagem
