DEV Community 👩‍💻👨‍💻

Diego Novais
Diego Novais

Posted on • Updated on

Recursão - Ruby

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

factorial(3)

# => 6
Enter fullscreen mode Exit fullscreen mode

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

(3 * (3-1)) * (2-1)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)

We want your help! Become a Tag Moderator.
Check out this survey and help us moderate our community by becoming a tag moderator here at DEV.