Recursão

Um assunto interessante em programação funcional é a recursão. Um recurso usado para lidar com a impossibilidade de manter estado falado no capítulo sobre imutabilidade.

Ele se classifica em uma forma de passar por itens de uma lista, um por um.

O básico de uma recursão é: Uma função que se chama, criando um looping onde vai até sair fora dessa chamada. Vamos a um exemplo real.

capture_log como o próprio nome diz, captura o log tendo o objetivo de ser usado em testes.

Primeiro o teste:

test/recursion_test.exs

defmodule RecursionTest do
  use ExUnit.Case

  import ExUnit.CaptureLog

  describe "print_loop/1" do
    test "Print x until x = 0" do
      x = 5

      execution = capture_log(fn ->
        Recursion.print_loop(x)
      end)

      assert capture_log(execution) =~ "Printed number 5"
      assert capture_log(execution) =~ "Printed number 4"
      assert capture_log(execution) =~ "Printed number 3"
      assert capture_log(execution) =~ "Printed number 2"
      assert capture_log(execution) =~ "Printed number 1"
    end
  end
end

Queremos registrar 5 vezes uma mensagem para entender que fez um loop de 5 vezes, onde o único dado alterado é o x onde vai de 5 a 1. Para isso utilizaremos o capture_log que serve para capturar logs feitos na aplicação.

Vamos rodar esse código

mix test test/recursion_test.exs
warning: Recursion.print_loop/1 is undefined (module Recursion is not available or is yet to be defined)
  test/recursion_test.exs:11: RecursionTest."test print_loop/1 Print x until x = 0"/1



  1) test print_loop/1 Print x until x = 0 (RecursionTest)
     test/recursion_test.exs:7
     ** (UndefinedFunctionError) function Recursion.print_loop/1 is undefined (module Recursion is not available)
     code: execution = capture_log(fn ->
     stacktrace:
       Recursion.print_loop(5)
       (ex_unit 1.14.3) lib/ex_unit/capture_log.ex:108: ExUnit.CaptureLog.with_log/2
       (ex_unit 1.14.3) lib/ex_unit/capture_log.ex:77: ExUnit.CaptureLog.capture_log/2
       test/recursion_test.exs:10: (test)


Finished in 0.04 seconds (0.00s async, 0.04s sync)
1 test, 1 failure

Obtivemos o relatório de erro por não termos o módulo nem a função criados. Vamos cria-las.

lib/recursion.ex

defmodule Recursion do
  require Logger

  def print_loop(x) do
    Logger.info("Printed number #{x}")

    print_loop(x - 1)
  end
end

Como podemos ver, na linha 7 temos a chamada para a mesma função que definimos na linha 4. Isso é a recursão, algo chamando a si mesmo, criando um laço de repetição. Porém, se rodarmos esse código, teremos um loop infinito, pois não temos um condição de parada. Caso execute esse código teremos o terminal congelado esperando a operação finalziar, mas isso não irá acontecer, então precisamos apertar CTRL + C e abortar a operação.

mix test test/recursion_test.exs
^C
BREAK: (a)bort (A)bort with dump (c)ontinue (p)roc info (i)nfo
       (l)oaded (v)ersion (k)ill (D)b-tables (d)istribution
^C%

Para isso não acontecer, precisamos de uma condição de parada, sendo a primeira coisa que definimos em nossa recursão. Nesse exemplo queremos que o X seja maior que 0. Essa é nossa condição. Para por isso em nossa função utilizaremos os guards. Vamos alterar nossa implementação.

lib/recursions.ex

defmodule Recursion do
  require Logger

  def print_loop(x) when x > 0 do
    Logger.info("Printed number #{x}")

    print_loop(x - 1)
  end
end

Na linha 4, ao lado da definição da função temos a palavra chave when seguida de uma condição. Ele garantirá que nosso x seja maior que 0. Caso não seja, ele não ta match com esse função, procurando uma outra definição para seguir o processo do programa. Caso não encontre, extoura uma exceção. Vamos rodar esse teste.

mix test test/recursion_test.exs
Compiling 1 file (.ex)


  1) test print_loop/1 Print x until x = 0 (RecursionTest)
     test/recursion_test.exs:7
     ** (FunctionClauseError) no function clause matching in Recursion.print_loop/1

     The following arguments were given to Recursion.print_loop/1:
     
         # 1
         0
     
     Attempted function clauses (showing 1 out of 1):
     
         def print_loop(x) when x > 0
     
     code: assert capture_log(execution) =~ "Printed number 5"
     stacktrace:
       (hello_world 0.1.0) Recursion.print_loop/1
       (ex_unit 1.14.3) lib/ex_unit/capture_log.ex:108: ExUnit.CaptureLog.with_log/2
       (ex_unit 1.14.3) lib/ex_unit/capture_log.ex:77: ExUnit.CaptureLog.capture_log/2
       (ex_unit 1.14.3) lib/ex_unit/capture_log.ex:108: ExUnit.CaptureLog.with_log/2
       (ex_unit 1.14.3) lib/ex_unit/capture_log.ex:77: ExUnit.CaptureLog.capture_log/2
       test/recursion_test.exs:14: (test)


Finished in 0.02 seconds (0.00s async, 0.02s sync)
1 test, 1 failure

Uma vez que o x chegou a 0, nossa função não se apresentava mais como um match e ganhamos com isso uma FunctionClauseError que significa que que a clausura para acessar essa função não foi atendida.

O que esta correto, não queremos a recursão de valores abaixo de 1. Queremos apenas maiores que 0. O que precisamos fazer agora é silenciar essa exceção. Para isso, podemos criar uma função de mesmo nome abaixo da criada anteriormente, fazer com que aceite valores abaixo de 1 e retornar algum valor como por exemplo nil. Vamos alterar nossa implementação:

lib/recursion_test.exs

defmodule Recursion do
  require Logger

  def print_loop(x) when x > 0 do
    Logger.info("Printed number #{x}")

    print_loop(x - 1)
  end

  def print_loop(_x), do: nil
end

Na linha 10, adicionamos uma nova definição da função print_loop/1, onde apenas espera receber um valor qualquer e retorna um nil. Não temos nenhuma condição em relação a isso porque esse é um cenário onde esperamos parar o looping. Então, quando chegamos a x = 0, a primeira fução que cotém o codicionameto x >0 não será mais atendido e irá para a proxima função de mesmo nome. Nessa nova função da linha 10 espera um valor qualquer, sem qualquer regra ou condição, logo, nosso x = 0 será atendido e iremos executar essa função. Executando essa função, a unica coisa que ele faz é retornar nil. Ela não executa novamente a própria função, isso causa a parada da repetição e a finalização da recursão.

Vamos rodar esse teste:

mix test test/recursion_test.exs
Compiling 1 file (.ex)
.
Finished in 0.08 seconds (0.00s async, 0.08s sync)
1 test, 0 failures

Nosso relatório de teste nos trouxe sucesso. Tivemos então um looping em cima da função print_loop/1. Finalizando a recursão utilizando guards.

Utilizando head | tail

Entendo uma vez o conceito de recursão, temos algumas facilidades que o elixir nos proporciona. Chamamos de head | tail (cabeça e cauda). Ele diz respseito ao processamento de listas, como por exemplo [1,2,3,4,5]. O número 1 seria a cabeça (primeiro elemento da lista) enquanto o restante [2, 3, 4, 5] seria a cauda. Isso pode ser utilizado para saber qual os proximos elementos de uma recursão. Vamos a um exemplo.

Precisamos processar números de uma lista que vai do 1 até o 10. Cada iteração utilizaremos o Logger para falar que passamos por lá, muito parecido com o exemplo anterior. Mas nesse caso estamos lidando com uma lista.

Primeiro, vamos o teste de parada, para não termos um loop infinito:

test/my_list_test.exs

defmodule MyListTest do
  use ExUnit.Case

  import ExUnit.CaptureLog

  describe "process/1" do
    test "the list are empty" do
      elements = []

      execution = fn ->
        capture_log(fn -> MyList.process(elements) end)
      end
      
      assert capture_log(execution) =~ "the list are empty"
    end
  end
end

Simplesmente queremos que um looping seja feito e que seja impresso uma vez cada elemento da lista. Vamos rodar para ter nosso erro

mix test test/my_list_test.exs
Compiling 1 file (.ex)
warning: MyList.process/1 is undefined or private
  test/my_list_test.exs:11: MyListTest."test process/1 the list are empty"/1



  1) test process/1 the list are empty (MyListTest)
     test/my_list_test.exs:7
     ** (UndefinedFunctionError) function MyList.process/1 is undefined or private
     code: assert capture_log(execution) =~ "the list are empty"
     stacktrace:
       (hello_world 0.1.0) MyList.process([])
       (ex_unit 1.14.3) lib/ex_unit/capture_log.ex:108: ExUnit.CaptureLog.with_log/2
       (ex_unit 1.14.3) lib/ex_unit/capture_log.ex:77: ExUnit.CaptureLog.capture_log/2
       (ex_unit 1.14.3) lib/ex_unit/capture_log.ex:108: ExUnit.CaptureLog.with_log/2
       (ex_unit 1.14.3) lib/ex_unit/capture_log.ex:77: ExUnit.CaptureLog.capture_log/2
       test/my_list_test.exs:14: (test)


Finished in 0.02 seconds (0.00s async, 0.02s sync)
1 test, 1 failure

Como esperado, o relatório nos avisou que MyList.process/1 não foi definido. Vamos a implementação. Primeiramente precisamos decidir o critério de parada. O conceito de recursão continua o mesmo, a função vai se chamar, até que por algum motivo o parâmetro que inserimos na função faça com que outra função de mesmo nome seja invocada e faça a parada da recursão.

Utilizaremos o conceito de head|tail. Sendo head o primeiro elemento, e tail o restante. Com isso podemos entender que ao chamar a propria função na recursão enviaremos o tail para a proxima iteração, seguindo até o final onde teremos uma lista vazia e isso causará a parada da recursão.

Vamos implementar primeiro a condição de parada:

lib/my_list.ex

defmodule MyList do
  require Logger

  def process([]) do
    Logger.info("the list are empty")
  end
end

Utilizamos pattern matching para dizer que, ao receber uma lista vazia por parâmetro, não chamaremos a função process dentro dela mesmo. Isso causará a parada da recursão. Também logamos o registro the list are empty, para garantirmos que estamos corretos. Vamos rodar o teste novamente

mix test test/my_list_test.exs
Compiling 1 file (.ex)
.
Finished in 0.02 seconds (0.00s async, 0.02s sync)
1 test, 0 failures

Perfeito! Temos a parada, agora precisamos fazer a recursão utilizando head|tail. vamos começar pelo teste:

lib/my_list.ex

defmodule MyListTest do
  use ExUnit.Case

  import ExUnit.CaptureLog

  describe "process/1" do
    # ...
    test "print all elements" do
      elements = [1,2,3,4,5]

      execution = fn ->
        capture_log(fn -> MyList.process(elements) end)
      end

      assert capture_log(execution) =~ "head is 1 and tail is [2, 3, 4, 5]"
      assert capture_log(execution) =~ "head is 2 and tail is [3, 4, 5]"
      assert capture_log(execution) =~ "head is 3 and tail is [4, 5]"
      assert capture_log(execution) =~ "head is 4 and tail is [5]"
      assert capture_log(execution) =~ "head is 5 and tail is []"
      assert capture_log(execution) =~ "the list are empty"
    end
  end
end

De forma simples, queremos apenas que cada iteração faz um log do valor de head e tail para exemplificar como o looping se comporta. Novamente head é o primeiro valor da lista, sem ser uma lista e tail é o restante sendo uma lista. Se tivermos [1,2,3] o head é o número 1 e tail é a lista [2,3].

Interpolação.

Podemos inserir valores em uma string utilizando a interpolação. Dentro de uma string definida qualquer texto que tem envolta aspas duplas. Para demarcar o local utilizamos jogo da velha abrir chaves, a variável a ser impressa e fechar chaves.

inspect Para imprimir um valor complexo como listas e mapas como texto, precisamos utilizar a função inspect/1 onde converterá os dados para texto.

Vamos a implementação

lib/my_list.ex

defmodule MyList do
  require Logger

  def process([]) do
    Logger.info("the list are empty")
  end

  def process([head | tail]) do
    Logger.info("head is #{head} and tail is #{inspect(tail)}")

    process(tail)
  end
end

Criamos uma nova função embaixo da criada como critério de parada com o mesmo nome. Utilizamos então o head | tail na entrada do parâmetro com a notação padrão [head | tail], conseguindo nosso head e nosso tail de forma fácil. Agora precisamos nos ater a duas coisas

1. head é o valor atual, não sendo uma lista. Esse valor usaremos para realizar algo nessa iteração. Nesse nosso exemplo, logaremos "Printed number #{head}".

2. tail é uma lista dos elementos restantes que deve ser passada para a proxima iteração.

Podemos rodar o teste novamente e ver o que acontece:

mix test test/my_list_test.exs
..
Finished in 0.03 seconds (0.00s async, 0.03s sync)
2 tests, 0 failures

O relatório de sucesso é imprimido, isso quer dizer que nossa recursão utilizando head | tail foi um sucesso! Esse conteúdo pode ser um pouco estanho quando vemos pela primeira vez, mas com o tempo e prática vai se tornar claro.

Conclusão

A utilização de recursão é altamente utilizado em programações funcionais. Elixir não é diferente. Ele possibilidade diversas funções. No próximo capítulo utilizaremos funções nativas do Elixir que se beneficiam da recursão.