Recursão em Ruby: Para começar a aventura com Elixir e Programação Funcional

em Desenvolvimento, Ruby.

Recursão é um assunto que assusta muitas pessoas em um primeiro momento. O motivo de tal medo é por termos sido educados (em especial no Brasil) para pensar em resolver todos os nossos problemas utilizando iteração. A escolha está no fato de que praticamente todas as linguagens que estudamos trabalham com programação imperativa, dados mutáveis, orientação a objetos e etc. Pode pegar a grade de qualquer faculdade, curso ou ver o que é comum no mercado: C, C++, Java, Ruby, C#, PHP, JavaScript, Perl, Python, Objective-C e por aí vai.

É triste ver que até mesmo no meio universitário o ensino da computação é limitado a uma única vertente de paradigmasgerando profissionais que acreditam que só existe uma maneira de resolver um problema…. Lamentações à parte, vamos ao que interessa:

>>> Qual a diferença básica entre resolver um problema utilizando iteração e recursão?

Programando com Iteração

Vamos pegar um exemplo básico, contar quantos itens uma lista possui.

Com iteração, o que faríamos é criar uma variável para armazenar a contagem dos itens e percorrer cada item da lista incrementando o valor da variável. Um exemplo simples e bem verboso com Ruby:

def count_list(list)
  counter = 0

  for item in list do
    counter = counter + 1
  end

  return counter
end

my_list = [1, 2, 3, 4, 5]

puts count_list(my_list) # 5

O equivalente em JavaScript seria:

function count_list(list) {
  var counter = 0;

  for (var item in list) {
    counter = counter + 1;
  }

  return counter;
}


var my_list = [1, 2, 3, 4, 5];

console.log(count_list(my_list)); /* 5 */

Poderíamos também escrever uma versão mais compacta deste código com Ruby:

def count_list(list)
  counter = 0

  list.each { counter += 1 }

  counter
end

my_list = [1, 2, 3, 4, 5]

puts count_list(my_list) # 5

Para alterar todos os itens de uma lista, como somar 10 em cada número da lista, podemos fazer:

def add_ten_to_all(list)
  index = 0

  for value in list do
    list[index] = value + 10

    index = index + 1
  end

  return list
end

my_list = [1, 2, 3, 4, 5]

puts add_ten_to_all(my_list).inspect
# [11, 12, 13, 14, 15]

O que em Ruby podemos também resumir a:

def add_ten_to_all(list)
  list.each_with_index do |value, index|
    list[index] = value + 10
  end
end

my_list = [1, 2, 3, 4, 5]

puts add_ten_to_all(my_list).inspect
# [11, 12, 13, 14, 15]

Porém, como em Ruby os objetos não são imutáveis, tais exemplos irão alterar a lista de fato. Se quisermos manter a nossa lista original sem modificações, podemos utilizar o .map que retorna uma cópia da lista modificada, ficando assim:

def add_ten_to_all(list)
  list.map { |value| value + 10 }
end

my_list = [1, 2, 3, 4, 5]

puts add_ten_to_all(my_list).inspect
# [11, 12, 13, 14, 15]

Tudo se baseia em iterar sobre os dados, repetir ações em todos os elementos da lista.

Já se o pensamento for trabalhar com recursão, a história muda…

Programando com Recursão

Em Elixir por exemplo, para contar os itens de uma lista, poderíamos fazer:

defmodule Recursion do
  def count([]) do
    0
  end

  def count([_head | tail]) do
    1 + count(tail)
  end
end

my_list = [1, 2, 3, 4, 5]

IO.inspect Recursion.count(my_list) # 5

Em SML/NJ, uma clássica linguagem para se aprender programação funcional, teríamos o seguinte código equivalente:

fun count_list (list) =
  case list of
      [] => 0
    | _ :: tail => 1 + count_list(tail);

val my_list = [1, 2, 3, 4, 5];

count_list(my_list); (* val it = 5 : int *)

E para somar 10 a cada item da lista? Em Elixir podemos fazer:

defmodule Recursion do
  def add_ten_to_all([]) do
    []
  end

  def add_ten_to_all([head | tail]) do
    [head + 10 | add_ten_to_all(tail)]
  end
end

my_list = [1, 2, 3, 4, 5]

IO.inspect Recursion.add_ten_to_all(my_list)

E aí, se você passou a vida inteira estudando e trabalhando com orientação a objetos, a sua reação ao ver os exemplos de código acima é:

Functional?

Você não entende nada, é confuso e não faz sentido. Mas calma, vamos por partes. A dificuldade é que ao mudar de paradigma, principalmente quando falamos de programação funcional, mudamos radicalmente diversos conceitos ao mesmo tempo. Nos exemplos acima passamos a trabalhar com recursão, pattern matching, diferentes estruturas de dados e (menos evidente mas também presente) imutabilidade, tudo de uma só vez.

Precisamos entender cada um desses conceitos (e mais alguns!) para começarmos a nos sentir mais confortáveis ao lidar com linguagens funcionais como Elixir, SML, Haskell, etc.

Hoje vamos focar apenas na recursão e, para isso, voltemos ao Ruby. Sim, é possível fazer recursão em Ruby e para quem está começando agora no mundo das linguagens funcionais, pode ser mais fácil entender como ela funciona do ponto de vista de uma linguagem que já estamos acostumados.

Recursão em programação orientada a objetos

A princípio, recursão não é algo exclusivo de programação funcional, é uma ideia que podemos utilizar em praticamente qualquer linguagem.

Com Ruby, uma solução utilizando recursão para contar os itens de uma lista, seria algo como:

def count_list(list)
  return 0 if list.empty?

  head = list.shift
  tail = list

  1 + count_list(tail)
end

my_list = [1, 2, 3, 4, 5]

puts count_list(my_list.clone) # 5

Entendendo o fluxo, primeiro temos a nossa condição de parada, o que acontece quando a nossa lista terminar:

return 0 if list.empty?

Então, se a lista for vazia, retornamos 0.

Depois, pegamos dois valores básicos em recursão de listas, o head (cabeça) e o tail (cauda) da lista. head, é o primeiro item da lista, tail, é o restante da lista:

head = list.shift
tail = list

Em nosso exemplo, com a lista [1, 2, 3, 4, 5], o nosso head será 5 e o nosso tail será [4, 3, 2, 1].

Uma outra forma mais prática de conseguir os mesmos dados é a partir do seguinte código:

head, *tail = list

Mas veremos no futuro que apesar de parecer melhor, pode não ser uma boa ideia na prática.

E a última parte é onde acontece a recursão em si, chamamos o método dentro do próprio método:

1 + count_list(tail)

E o que acontece na prática, é que recursivamente vamos obtendo os valores para o nosso resultado.

Na primeira vez que chamamos o método, o que teremos na prática é:

1 + count_list([2, 3, 4, 5])

tail é o restante da lista depois que removemos o primeiro item. Como chamamos o mesmo método, só que agora com a lista contendo um item a menos, o resultado da próxima chamada será:

1 + count_list([3, 4, 5])

E para tentar visualizar melhor, o que acontece é:

1 + count_list([4, 3, 2, 1])
1 + 1 + count_list([3, 2, 1])
1 + 1 + 1 + count_list([2, 1])
1 + 1 + 1 + 1 + count_list([1])
1 + 1 + 1 + 1 + 1 + count_list([])
1 + 1 + 1 + 1 + 1 + 0

O último item foi 0, por causa da nossa condição de parada, que retorna 0 quando a nossa lista é vazia e para de continuar chamando o mesmo método recursivamente (caso contrário teríamos o clássico loop infinito).

E então, o resultado da soma 1 + 1 + 1 + 1 + 1 + 0 será 5, a quantidade de itens em nossa lista. Algo que você deve ter notado é que agora utilizamos o .clone na lista que estamos passando como parâmetro para o método:

add_ten_to_all(my_list.clone)

Para entender melhor o motivo disso vamos conversar futuramente sobre sobre as diferenças entre uma linguagem que possui imutabilidade (Elixir, Haskell, etc.) e uma que não (Ruby, Java, entre outros).

A mesma ideia, aplicada ao segundo problema, somar 10 em todos os itens da lista:

def add_ten_to_all(list)
  return [] if list.empty?

  head = list.shift
  tail = list

  [head + 10] + add_ten_to_all(tail)
end

my_list = [1, 2, 3, 4, 5]

puts add_ten_to_all(my_list.clone).inspect
# [11, 12, 13, 14, 15]

Neste caso, vamos reconstruindo a nossa lista juntando cada pedacinho dela. Visualizando o que acontece:

[head + 10] + add_ten_to_all(tail)
[1 + 10] + add_ten_to_all([2, 3, 4, 5])
[1 + 10] + [2 + 10] + add_ten_to_all([3, 4, 5])
[1 + 10] + [2 + 10] + [3 + 10] + add_ten_to_all([4, 5])
[1 + 10] + [2 + 10] + [3 + 10] + [4 + 10] + add_ten_to_all([5])
[1 + 10] + [2 + 10] + [3 + 10] + [4 + 10] + [5 + 10] + add_ten_to_all([])
[1 + 10] + [2 + 10] + [3 + 10] + [4 + 10] + [5 + 10] + []
[11] + [12] + [13] + [14] + [15] + []

Em Ruby, somar várias arrays significa concatená-las, logo, [11] + [12] + [13] + [14] + [15] + [] resultará em [11, 12, 13, 14, 15].

Um bom exercício para começar a entender melhor como recursão funciona, é tentar implementar rotinas triviais que você está acostumado a realizar com iteração, de forma recursiva.

Como você somaria todos os itens de uma lista? Como você ordenaria uma lista? Lembrando dos componentes básicos aqui comentados: toda recursão precisa ter uma condição de parada e geralmente trabalhar com a ideia de head/tail.

Depois de um pouco de prática você começará a visualizar automaticamente o que acontece durante as chamadas recursivas e qual será o resultado esperado e, para o seu provável espanto, se pegará considerando recursão uma técnica muito elegante!

Próximos passos

Depois de entender como a recursão acontece, você estará mais confortável para se aventurar nas linguagens funcionais. Os próximos passos provavelmente serão entender melhor sobre stack e pattern matching.

Pattern matching te ajudará começar a ver de forma natural os exemplos de códigos em Elixir ou SML aqui mostrados, quebrando a próxima barreira que provavelmente te faz achar programação funcional algo bizarro e complexo.

Já o stack é o que te fará entender mais a fundo sobre como funciona internamente uma recursão e te dará respostas para muitas perguntas clássicas sobre desempenho ou o motivo de no geral não utilizarmos recursão em linguagens orientadas a objetos.

Um exemplo simples em Ruby para atiçar a curiosidade:

def count_list(list)
  return 0 if list.empty?

  head = list.shift
  tail = list

  1 + count_list(tail)
end

my_list = (0..100000).to_a

puts count_list(my_list.clone)

Tal código ao ser executado retornará um clássico erro muito conhecido por quem programa em Ruby:

stack level too deep

Sim, é possível resolver esse “problema” em Ruby (e ele não é exclusivo desta linguagem) e fazer o método acima funcionar.

Mas isso tudo é assunto para outros posts, até lá!

Você também pode gostar