A recursão é um daqueles tópicos de programação que podem parecer intimidantes. Isso é especialmente verdadeiro se você for novo em programação. Neste tutorial, você aprenderá tudo o que precisa saber sobre isso. Você aprenderá o que é recursão, como funciona a recursão em JavaScript e também como implementá-la.
Uma introdução rápida
A maneira mais simples de descrever o que é recursão é dizendo que é uma função que chama a si mesma. Este tipo de função é denominado “função recursiva”. Não importa se é recursão em JavaScript ou qualquer outra linguagem. A ideia principal é que você tenha uma função e essa função se auto-chama, pelo menos uma vez.
// Simple recursive function
function recursiveFunction() {
// Call the recursive function again
recursiveFunction()
}
// Call the recursiveFunction()
recursiveFunction()
Dito isso, a função recursiva não é qualquer função. Existem algumas condições que todas as funções recursivas devem atender. Isso não é necessário apenas para que você possa chamar essa função de recursão. Também é necessário fazer com que essa recursão funcione corretamente. Aqui está o problema potencial.
Digamos que você tenha uma função. Esta função chama a si mesma. O que acontece quando você chama essa função? Bem, ele se chamará. O que acontece depois? Quando essa função chama a si mesma, ela se chamará novamente, e novamente e novamente. O problema é que não há um ponto em que a função seja encerrada. O resultado é um loop infinito.
Por exemplo, isso acontecerá se você tentar executar a função do exemplo acima. Ao executar essa função, você obterá um erro Uncaught RangeError: Maximum call stack size exceeded. Você pode evitar esse problema, criando um loop infinito, adicionando um caso base à função recursiva.
Caso base
Um caso base é um nome sofisticado para uma condição específica. Também é chamado de “condição básica”. Essa condição forçará a função a fazer uma de duas coisas. Se a condição for avaliada como false, a função recursiva se chamará novamente. Se a condição for avaliada como true, a função recursiva retornará um valor.
A maneira mais fácil de criar esse caso base é usando a instrução if… else simples . Dentro de um bloco, ifou elsedependendo da condição, você retornará algum valor. Dentro do outro bloco, você chamará a função recursiva novamente. Isso permitirá que você encerre a função no momento certo.
// Simple recursive function
function recursiveFunction() {
// Add base case
if (/* condition */) {
// Call the recursive function again
recursiveFunction()
} else {
// Return something instead of calling
// the recursive function again
}
}
// Call the recursive function
recursiveFunction()
JavaScript encerrará a execução da função quando encontrar uma returninstrução. Isso significa que você realmente não precisa usar a if...elseinstrução. Você precisa apenas da ifparte. Se algo, devolva algo. Caso contrário, você pode deixar o JavaScript ignorar o if...elsee continuar.
// Recursive function with shorter condition
function recursiveFunction() {
// Add base case
if (/* condition */) {
// If condition evaluates to true
// terminate this function call
// by returning something
return /* some value */
}
// Otherwise, call the recursive function again
recursiveFunction()
}
// Call the recursive function
recursiveFunction()
Esta não é realmente a versão mais curta. Você pode tornar a condição básica e toda a função ainda mais curtas. Você pode substituir a if...elseinstrução pelo operador ternário . Desta forma, você pode reduzir toda a função recursiva quase uma linha. Se você usar uma função de seta do que literalmente para uma linha.
// Recursive function with ternary operator
function recursiveFunction() {
// Add base case
return (/* condition */) ? /* some value */ : recursiveFunction()
}
// Call the recursive function
recursiveFunction()
Como escolher o melhor caso base
Qual é o melhor candidato para o caso base? Isso depende do que você deseja alcançar com sua função recursiva. Por exemplo, digamos que você deseja usar a recursão para calcular o fatorial. Este é o exemplo mais popular de recursão. No caso de um fatorial, pense em qual é o menor número que você pode usar.
Para fatorial, o menor número é 1. Fatorial de 1 (1!) Sempre resultará em um. Isso torna 1 o melhor candidato para o caso base porque é o menor número, ou nível, que você pode obter. Se você quiser contar números de X até 0, 0 será o número mais baixo. Também será o melhor candidato para o caso base.
Se você quiser fazer o oposto e contar para cima, a base será o número mais alto que você deseja alcançar. Outro exemplo poderia ser inverter uma string simples. Nessa situação, o caso básico seria que o comprimento da string deve ser maior que 0. Não faz sentido continuar revertendo uma string vazia.
Como realmente funciona: uma introdução rápida à pilha de chamadas
Você sabe o que é recursão e como ela se parece, para que possa reconhecê-la quando a vir. Você também sabe o que é um caso básico. Agora, vamos dar uma olhada em como isso realmente funciona. Principalmente como funciona em JavaScript, já que essa será a linguagem de programação com a qual você está mais familiarizado.
Para entender como funciona a recursão, você precisa saber pelo menos um pouco sobre a pilha de chamadas . A pilha de chamadas é um mecanismo integrado em JavaScript. JavaScript o usa para rastrear todas as chamadas de função. Digamos que você chame uma função. Quando você fizer isso, o JavaScript adicionará essa função à pilha de chamadas.
Quando essa chamada de função for concluída, o JavaScript removerá automaticamente essa chamada de função da pilha de chamadas e vai para outra abaixo, se houver. No entanto, se a função que você chamou chamar outra função, algo diferente acontecerá. Quando essa segunda função é chamada, o JavaScript também a adiciona à pilha de chamadas.
Se essa segunda função também chamar uma função, o JavaScript também a adicionará ao topo da pilha de chamadas. Isso se repete enquanto houver chamadas de função na cadeia de funções atual. Existem três coisas importantes que você precisa saber. A primeira coisa é que o JavaScript colocará a segunda chamada acima da primeira.
JavaScript irá adicionar essa chamada de função em cima dele, no topo de toda a pilha de chamadas. A segunda coisa é que o JavaScript executa chamadas na pilha de chamadas de cima para baixo. Isso significa que a primeira chamada de função adicionada à pilha de chamadas será executada como a última.
Por outro lado, a última chamada de função adicionada à pilha de chamadas será executada como a primeira. Isso é chamado de princípio LIFO (Last-In-First-Out). A terceira coisa é que quando o JavaScript encontra uma chamada de função, ele para de executar a chamada atual, executa essa nova chamada e qualquer coisa dentro da função recém-chamada.
Somente quando a função recém-chamada for executada, o JavaScript retornará à chamada anterior e terminará de executar aquela. Isso se repetirá para cada função na pilha de chamadas.
function funcFour() {
// some code to execute
}
function funcThree() {
funcFour()
// Execution of funcThree() is paused on the line above
// until funcFour() is finished
}
function funcTwo() {
funcThree()
// Execution of funcTwo() is paused on the line above
// until funcThree() is finished
}
function funcOne() {
funcTwo()
// Execution of funcOne() is paused on the line above
// until funcTwo() is finished
}
// Call the funcOne()
funcOne()
// Call stack at this moment:
// funcFour() - executed as first (top of the stack)
// funcThree() - waiting for funcFour() to finish
// funcTwo() - waiting for funcThree() to finish
// funcOne() - waiting for funcTwo() to finish
// README:
// funcFour() is at the top of the stack
// and its function call will be finished as first
// after that execution will return to funcThree()
// when funcThree() is finished execution will return to funcTwo()
// when funcTwo() is finished execution will return to funcOne()
// when funcOne() is finished the call stack will be empty
Função fatorial recursiva, pilha de chamadas e análise
Agora, vamos usar essas informações sobre a pilha de chamadas para entender como funciona a recursão em JavaScript. Para ilustrar isso melhor, vamos usar uma função recursiva para calcular um fatorial. Esta função aceitará um único parâmetro, um número para o qual calculará um fatorial.
O caso base para esta função será que o número que você passou como argumento deve ser igual a 1. Quando essa situação acontecer, a função retornará esse número. Ele retornará 1. Caso contrário, ele retornará o número multiplicado pelo resultado da própria chamada com o número diminuído por 1 passado como um argumento.
// Recursive function to calculate factorial
function calculateFactorial(num) {
// Base case
if (num === 1) {
// The value of "num" here will be 1
return num
}
return num * calculateFactorial(num - 1)
}
// Shorter version with ternary operator
function calculateFactorial(num) {
// Base case
return (num === 1) ? num : num * calculateFactorial(num - 1)
}
// Test the calculateFactorial()
calculateFactorial(4)
// Output:
// 24
// Test the calculateFactorial() again
calculateFactorial(9)
// Output:
// 362880
// Test the calculateFactorial() one more time
calculateFactorial(1)
// Output:
// 1
Vamos analisar a execução da calculateFactorial()função. Para ser breve, vamos usar 4 como o número para o qual queremos calcular o fatorial. Quando você chama a função com o número 4 como argumento, o JavaScript a adiciona à pilha de chamadas. Como 4 não é igual a 1 calculateFactorial(), será chamado novamente.
Neste momento, calculateFactorial()será chamado não com o número 4, mas sim com o número 3 passado como argumento. As chamadas subsequentes são sempre com número diminuído em 1. JavaScript adicionará essa segunda chamada à pilha de chamadas também. Ele será adicionado ao início da chamada anterior de calculateFactorial()com o número 4.
O número ainda não é igual a 1. Portanto, outra chamada de calculateFactorial()função será executada. O número passado como um argumento agora será 2. JavaScript adicionará esta chamada no topo da pilha de chamadas e chamará a calculateFactorial()função novamente. O número agora será 1.
Esse número atende ao caso básico, portanto a calculateFactorial()função agora retornará o número e não ligará para si mesma novamente. A cadeia de chamadas acabou e estamos no topo da pilha de chamadas.
// Recursive function to calculate factorial
function calculateFactorial(num) {
// Base case
return (num === 1) ? return num : num * calculateFactorial(num - 1)
}
// Test the calculateFactorial()
calculateFactorial(4)
// Call stack after calling calculateFactorial(4):
// calculateFactorial(1) - top of the stack, first out
// calculateFactorial(2)
// calculateFactorial(3)
// calculateFactorial(4) - bottom of the stack, last out
O que acontece depois? Quando estivermos no topo da pilha e não houver mais chamadas, o JavaScript começará a se mover para o final da pilha. Durante isso, o JavaScript também começará a retornar valores de todas as chamadas de função na pilha. Com cada valor retornado, uma chamada de função será removida da pilha.
A parte mais interessante são os valores retornados de todas essas chamadas. Você se lembra da num * calculateFactorial(num - 1)linha no código da calculateFactorial()função? Esses valores retornados por chamadas na pilha basicamente substituirão a calculateFactorial(num - 1)parte.
A linha agora será semelhante a num * "num" (returned by the previous call). Para cada chamada na pilha, o numserá multiplicado pelo resultado da chamada anterior. O calculateFactorial(1)é a última chamada no topo da pilha e seu valor de retorno será retornado como o primeiro.
Não há chamada anterior e a função diz que este número deve ser devolvido. Essa é a (num === 1) ? return num :parte. Portanto, o primeiro valor retornado é 1. A próxima chamada está na pilha de chamadas é calculateFactorial(2). Esta não é a última chamada, então a (num === 1) ? return num :linha não se aplica aqui.
Em vez disso, temos que aplicar o num * calculateFactorial(num - 1). O primeiro numé o número passado como parâmetro para a chamada atual: 2. calculateFactorial(num - 1)É o número retornado na última chamada: 1. Portanto, num * calculateFactorial(num - 1)resultará em 2 * 1.
A próxima chamada na pilha de chamadas é calculateFactorial(3). Assim como no caso anterior, temos que aplicar o num * calculateFactorial(num - 1). O primeiro numé novamente o número passado para a chamada atual: 3. O calculateFactorial(num - 1)é o número retornado pela última chamada: 2.
O resultado da última chamada foi 2 * 1. É por isso que calculateFactorial(num - 1)agora é traduzido para 2. Então, num * calculateFactorial(num - 1)traduziremos para 3 * 2. A calculateFactorial(4)chamada foi a última chamada, na parte inferior da pilha. O numpassado para a chamada atual é 4.
O resultado de calculateFactorial(num - 1)retornado pela chamada anterior,, calculateFactorial(3)foi 6 (resultado de 3 * 2). Então, agora, se num * calculateFactorial(num - 1)traduz em 4 * 6. Isso torna o valor retornado pela chamada atual e última 24. Esse também é o resultado final do cálculo fatorial.
// Recursive function to calculate factorial
function calculateFactorial(num) {
// Base case
return (num === 1) ? return num : num * calculateFactorial(num - 1)
}
// Test the calculateFactorial()
calculateFactorial(4)
// Call stack after calling calculateFactorial(4):
// calculateFactorial(1)
// - returns 1
// calculateFactorial(2)
// - returns 2 * 1 (1 is value returned from calculateFactorial(1))
// calculateFactorial(3)
// - returns 3 * 2 (2 is value returned from calculateFactorial(2))
// calculateFactorial(4)
// - returns 4 * 6 (6 is value returned from calculateFactorial(4))
Outros dois exemplos de recursão em JavaScript
Antes de terminar este tutorial, vamos dar uma olhada em alguns exemplos de recursão em JavaScript. Você já sabe como usar a recursão para calcular o fatorial de qualquer número fornecido. Vamos dar uma olhada rápida em outros dois exemplos de funções recursivas.
Função recursiva para contagem regressiva
Um bom exemplo para demonstrar a implementação de recursão em JavaScript pode ser uma função que conta até 0 e imprime um número para cada chamada recursiva. O caso base para esta função recursiva será se o número passado, quando diminuído em um, for maior que 0.
Somente se o número for maior que 0 a função será chamada novamente. Caso contrário, não haverá mais nada a fazer, então a função será encerrada.
// Recursive function for countdown
function countdown(num) {
// Print the number passed
// to the current recursive call
console.log(num)
// Base case
if (num - 1 > 0) {
// If current number decreased by 1
// is higher than 0 call countdown() again
// with number decreased by 1
return countdown(num - 1)
}
}
// Call the countdown() function
countdown(11)
// Output:
// 11
// 10
// 9
// 8
// 7
// 6
// 5
// 4
// 3
// 2
// 1
Função recursiva para reverter string
O segundo exemplo de uma implementação de recursão em JavaScript será uma função que inverte uma string. Esta função aceitará string como parâmetro. O caso base será se o comprimento da string for maior que 1. Se esta condição for verdadeira, a função se chamará.
A string para esta chamada subsequente será a string da chamada atual sem o primeiro caractere. Além disso, este primeiro caractere será adicionado ao final do valor retornado pela próxima chamada.
// Recursive function for reversing string
function reverseString(str) {
// Base case
if (str.length >= 1) {
// If the length of the string is bigger than 1
// call the reverseString() function again,
// pass in pass in the string without the first character
// and then add the character and the end
return reverseString(str.substring(1)) + str.charAt(0)
}
// Otherwise, return the string
return str
}
// Call the reverseString() function
reverseString('Hello')
// Output:
// 'olleH'
Conclusão: Introdução à recursão em JavaScript
A recursão é um tópico avançado que pode ser muito difícil de entender. Porém, vale a pena aprender a aprender sobre isso. A recursão pode ser uma ferramenta muito útil para resolver alguns problemas melhor e mais rapidamente. Espero que este tutorial tenha ajudado você a entender a recursão em JavaScript funciona e o que é em geral.