Recursão em

Sobre Recursão

Funções recursivas são funções que chamam a si mesmas.

Uma função recursiva precisa ter pelo menos um caso base e pelo menos um caso recursivo.

Um caso base retorna um valor sem chamar a função de novo. Um caso recursivo chama a função de novo, modificando a entrada para que ela em algum momento corresponda ao caso base.

Muitas vezes, cada caso é escrito em sua própria cláusula de função.

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

Uma função recursiva pode ter muitos casos base e/ou muitos casos recursivos. Por exemplo, a sequência de Fibonacci é uma sequência recursiva com dois casos base:

def fibonacci(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

Contar o número de ocorrências de um determinado valor x em uma lista tem dois casos recursivos:

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

Laços por meio de recursão

Por causa da imutabilidade, os laços em Elixir são escritos de forma diferente das linguagens imperativas. Por exemplo, os laços geralmente se parecem com isto:

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

Em uma linguagem funcional, não é possível mutar i (chamando i++). Assim, os laços precisam ser implementados com recursão.

O equivalente a um laço for em Elixir seria assim:

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

Na prática, iterar sobre listas e outras estruturas de dados enumeráveis costuma ser feito com o módulo Enum. Por baixo dos panos, as funções do módulo Enum são implementadas com recursão.

Execução infinita

As funções recursivas, se implementadas de forma incorreta, podem nunca retornar o resultado. Isso pode ser um problema porque, a cada vez que uma função é chamada, uma referência é armazenada na memória, no ponto para onde a VM deve retornar o resultado (na pilha de chamadas). Se uma função recursiva chama a si mesma infinitamente, é possível ficar sem memória e fazer a VM travar (um erro de estouro de pilha). A VM do Erlang, na qual o Elixir roda, é especialmente otimizada para recursão e confiabilidade, então pode demorar bastante até que erros de recursão infinita apareçam ou travamentos aconteçam.

Esse problema de execução infinita pode ser causado por:

• Esquecer de implementar um caso base.
• Não definir o caso base como a primeira cláusula.
• Não modificar o argumento corretamente ao fazer a chamada recursiva e, com isso, nunca chegar ao caso base.