Recursão em

Sobre Recursão

As funções recursivas são funções que se chamam a si próprias.

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

Um caso base devolve um valor sem voltar a chamar a função. Um caso recursivo volta a chamar a função, modificando o valor de entrada para que este acabe por corresponder ao caso base.

Muitas vezes, cada caso é escrito na 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 numa 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)

Ciclos através da recursão

Devido à imutabilidade, os ciclos em Elixir são escritos de forma diferente das linguagens imperativas. Por exemplo, é comum os ciclos terem este aspeto:

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

Numa linguagem funcional, não é possível alterar i (chamando i++). Assim, os ciclos têm de ser implementados com recursão.

O equivalente a um ciclo 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 faz-se quase sempre com o módulo Enum. Nos bastidores, as funções do módulo Enum são implementadas com recursão.

Execução infinita

As funções recursivas, se forem implementadas incorretamente, podem nunca devolver o resultado. Isto pode ser problemático, porque sempre que uma função é chamada é armazenada uma referência na memória, no local para onde a VM deve devolver o resultado (na pilha de chamadas). Se uma função recursiva se chamar a si própria infinitamente, é possível ficar sem memória, o que faz a VM falhar (um erro de transbordo de pilha). A VM Erlang, sobre a qual o Elixir corre, é especialmente otimizada para recursão e fiabilidade, por isso pode demorar muito tempo até os erros de recursão infinita serem visíveis ou ocorrerem falhas.

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

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