O que é recursão?

Recurso que permite definir algo em função dele mesmo. Ou seja, quando uma função chama a si própria. Alguns exemplos bem comuns são os algoritmos da Sequência de Fibonacci e Cálculo Fatorial.

Vamos ver alguns exemplos:

1 - Somando os números de um array com recursividade

Neste exemplo iremos somar todos os números de um array utilizando Recursividade. Dado um array de números inteiros, vamos somar todos os itens e retornar o valor da soma.

def recursive_sum(numbers)
  if numbers.size <= 1
    numbers[0]
  else
    numbers.slice!(0) + recursive_sum(numbers)
  end

# Poderíamos fazer de forma ternaria:  
# numbers.size <= 1 ? numbers[0] : numbers.slice!(0) + recursive_sum(numbers)
end

Aqui fiz apenas uma verificação pra saber se o tamanho do array recebido é menor ou igual a 1, caso seja, retorne o primeiro e único item do array. Caso o tamanho do array seja maior que 1, retorne uma soma do primeiro item do array mais uma nova chamada do método recursive_sum.

Então, pra entender melhor, vamos analisar o que acontece aqui utilizando um exemplo de um array [1, 2].

numbers = [1, 2]

recursive_sum(numbers)

# => 3

Na primeira vez que o método for executado, o array possui 2 itens, 1 e 2. Ou seja, a primeira condição será falsa e irá cair no else por ter mais de um item.

Nessa condição eu executo um slice!(0), que por sua vez remove o primeiro item do array, no caso o número 1 e chamo novamente a função soma_array, então algo como:

1 + soma_array([2])

E agora ao ser executada novamente o array possui apenas um item, então a função retorna o número 2, voltando ao contexto da primeira chamada da função:

`1 + 2

=> 3`

A mesma coisa acontece caso o array possua vários itens.

2 - Fatorial (n!)

Fatorial é um número natural inteiro positivo, o qual é representado por n!

O fatorial de um número é calculado pela multiplicação desse número por todos os seus antecessores até chegar ao número 1. Note que nesses produtos, o zero (0) é excluído.

O fatorial é representado por:

n! = n . (n – 1) . (n – 2) . (n – 3)!

Sabendo agora um pouco sobre fatorial, vamos escrever um método que execute isso de forma recursiva.

def factorial(number)
  if number == 1
    1
  else
    number * factorial(number - 1)
  end

  # number == 1 ? 1 : number * factorial(number - 1)
end

Então se utilizarmos o número 3 como parâmetro, teremos o seguinte:

factorial(3)

# => 6

Como nosso argumento é 3, faremos o seguinte cálculo:

(3 * (3-1)) * (2-1)

3 - Sequência de Fibonacci

Sequência de Fibonacci é a sequência numérica proposta pelo matemático Leonardo Pisa, mais conhecido como Fibonacci:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Foi a partir de um problema criado por ele que o mesmo detectou a existência de uma regularidade matemática.

A sequência é definida mediante a seguinte fórmula:

Fn = Fn - 1 + Fn - 2

Trata-se do exemplo clássico dos coelhos, em que Fibonacci descreve o crescimento de uma população desses animais.

Então, vamos criar esse ultimo exemplo em Ruby, lembrando que existem várias maneiras de transformar esses conceitos em código.

def fib(number)
  return number if number < 2
  fib(number-1) + fib(number-2)
  # number <= 1 ? number : fib(number - 1) + fib(number - 2)
end

Podemos ver que a condicional analisa se o número recebido é menor que 2, caso positivo, será retornado o próprio número, caso não, faça uma soma utilizando a mesma função duas vezes, a primeira parte utilizando o number - 1 e a segunda o number - 2 como descrito na fórmula da sequência de Fibonnaci.

Então se utilizarmos o número 6 como parâmetro, teremos o seguinte:

fib(6)

# => 8

Quando implementamos recursão para por exemplo, calcular o fatorial de um número. Se passarmos como parâmetro um número muito grande, por exemplo 11.000, provavelmente teremos um problema de estouro de pilha.

Para resolver este problema e conseguirmos executar o método de forma recursiva podemos usar como estratégia o TCO (Tail Call Optimization), para saber mais a respeito eu escrevi este artigo complementar.

Conclusão

Como vimos a recursão é algo bastante prático e bastante útil. E o caminho para entender melhor e dominar é a prática. Em breve teremos mais conteúdos e códigos usando este recurso.

Contato:
Email: contato@diegonovais.com.br
LinkedIn: https://www.linkedin.com/in/diegonovais/
Github: https://github.com/dnovais