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

E com isso terminamos nosso aprendizado sobre recursividade com Javascript :)