Entendendo Recursão
Há um famoso ditado de programação que diz o seguinte:
Para entender a recursão, é preciso entender antes a recursão
A recursão é um método de resolução de problemas que consiste em solucionar partes menores do mesmo problema até resolvermos o problema original, mais amplo
Em geral, ela envolve chamar a própria função
Um método ou função será recursivo se ele puder chamar a si mesmo diretamente, assim:
function recursiveFunction(params) {
recursiveFunction(params)
}Uma função também é chamada de recursiva se puder chamar a si mesma indiretamente, assim:
function recursiveFunction1(params) {
recursiveFunction2(params)
}function recursiveFunction2(params) {
recursiveFunction1(params)
}Suponha que tenhamos de executar recursiveFunction
Qual seria o resultado? Nesse caso, a função seria executada indefinidamente
Por esse motivo, toda função recursiva deve ter um caso de base, que é uma condição para a qual nenhuma chamada recursiva será feita (um ponto de parada) a fim de evitar uma recursão infinita
Retornando ao ditado mencionado no começo sobre programação, ao compreender o que é uma recursão, resolveremos o problema original
Se traduzirmos esse ditado de programação em código Javascript, poderemos escrevê-lo assim:
function understandRecursion(doIUnderstandRecursion) {
const recursionAnswer = confirm('Do you understand recursion?')
if (recursionAnswer === true) {
return true
}
understandRecursion(recursionAnswer)
}A função understandRecursion ficará chamando a si mesma até que recursionAnswer seja true
Calculando o fatorial de um número
Em nosso primeiro exemplo de recursão, veremos como calcular o fatorial de um número
O fatorial de um número n é definido por n!, que é o resultado da multiplicação dos números de 1 a n
O fatorial de 5 é representado por 5! e é igual a 5 * 4 * 3 * 2 * 1, resultando em 120
Fatorial iterativo
Se tentarmos representar os passos para calcular o fatorial de qualquer número n, podemos defini-los assim: (n) * (n - 1) * (n - 2) * (n - 3 ) * ... * 1
É possível escrever um função para calcular o fatorial de um número usando um laço, assim:
function factorialIterative(number) {
if (number < 1) return undefined
let total = 1
for (let i = number; i > 1; i--) {
total = total * n
}
return total
}Podemos iniciar o cálculo do fatorial começando com o dado number e decrementando n até que ele tenha um valor igual a 2, pois o fatorial de 1 é 1 e já estará incluso na variável total
O fatorial de zero também é 1
O fatorial de números negativos não será calculado
Fatorial recursivo
Vamos agora tentar reescrever a função factorialIterative usando recursão
Antes, porém, vamos determinar todos os passos usando uma definição recursiva
O fatorial de 5 é calculado com 5 * 4 * 3 * 2 * 1
O fatorial de 4 (n - 1) é calculado com 4 * 3 * 2 * 1
Calcular (n - 1) é um subproblema que resolveremos para calcular n!, que é o problema original, portanto, podemos definir o fatorial de 5 assim:
factorial(5) = 5 * factorial(4): podemos calcular 5! como 5 * 4!
factorial(5) = 5 * (4 * factorial(3)): precisamos resolver o subproblema de calcular 4!, que podemos calcular como 4 * 3!
factorial(5) = 5 * 4 * (3 * factorial(2)): precisamos resolver o subproblema de calcular 3!, que podemos calcular como 3 * 2
factorial(5) = 5 * 4 * 3 * (2 * factorial(1)): precisamos resolver o subproblema de calcular 2!, que podemos calcular como 2 * 1
factorial(5) = 5 * 4 * 3 * 2 * (1): precisamos resolver o subproblema de calcular 1!
factorial(1) ou factorial(0) devolve 1. 1! é igual a 1. Poderíamos dizer também que 1! = 1 * 0! e 0! também é 1
A função factorial usando recursão é declarada da seguinte maneira:
function factorial(n) {
if (n === 1 || n === 0) {
return 1
}
return n * factorial(n - 1)
}Sequência de Fibonacci
A sequência de fiboncci é outro problema que podemos resolver usando a recursão
Essa sequência é composta de uma série de números: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 e assim por diante
O número 2 é encontrado por meio da soma de 1 + 1
O número 3 é encontrado somando 1 + 3
O número 5 é encontrado somando 2 + 3 e assim sucessivamente
A sequência de Fibonacci pode ser definida assim:
O número de Fibonacci na posição 0 é 1
O número de Fibonacci na posição 1 ou 2 é 1
O número de Fibonacci na posição n (para n > 2) é o Fibonacci de (n - 1) + Fibonacci de (n - 2)
Fibonacci iterativo
Implementamos a função de fibonacci de modo interativo, assim:
function fibonacci(n) {
if (n < 1) return 0
if (n <= 2) return 1
let fibNMinus2 = 0
let fibNMinus1 = 1
let fibN = n
for (let i = 2; i <= n; i++) {
fibN = fibNMinus1 + fibNMinus2
fibNMinus2 = fibNMinus1
fibNMinus1 - fibN
}
return fibN
}Fibonacci recursivo
A função fibonacci pode ser reescrita da seguinte maneira:
function fibonacci(n) {
if (n < 1) return 0
if (n <= 2) return 1
return fibonacci(n - 1) + fibonacci(n - 2)
}Fibonacci com memoização
Há também uma terceira abordagem chamado memoização (memoization), que podemos usar para escrever a função fibonacci
A memoização é uma técnica de otimização em que armazenamos os valores de resultados anteriores, de modo semelhante a um cache
Se analisarmos as chamadas feitas para calcular fibonacci(5), perceberemos que fibonacci()3 foi calculado duas vezes; portanto, podemos armazenar o seu resultado de modo que, quando a processarmos novamente, já teremos esse resultado
O código a seguir representa a função fibonacci escrita com memoização:
function fibonacciMemoization(n) {
const memo = [0, 1]
const fibonacci = (n) => {
if (memo[n] !== null) return memo[n]
return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
}
return fibonacci
}No código anterior, declaramos um array memo que fará o cache de todos os resultados calculados
Se o resultado já tiver sido calculado, ele será devolvido, caso contrário, calcularemos o resultado e o adicionaremos ao cache