Recursão - Ruby
Tags: braziliandevs, ruby, rails
Published: 2022-01-03 12:45:38

## 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.

```ruby
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].

```ruby
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.

```ruby
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:

```ruby
factorial(3)

# => 6
```

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

```ruby
(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.

```ruby
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:

```ruby
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](https://dev.to/dnovais/tco-tail-call-optimization-ruby-54ap).

## 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