Introdução
Recursão de chamada de cauda
Ao fazeres recursão sobre enumeráveis (listas, bitstrings, strings), há frequentemente duas preocupações:
- quanta memória é necessária para guardar o rasto das chamadas recursivas de funções
- como construir a solução de forma eficiente
Para lidar com estas preocupações, pode usar-se um acumulador.
Um acumulador é uma variável que é passada juntamente com os dados. Serve para passar o estado atual da execução da função, de chamada em chamada, até se atingir o caso base. No caso base, o acumulador é usado para devolver o valor final da chamada recursiva.
Os acumuladores devem ser inicializados por quem escreve a função, e não por quem a usa. Para isso, declara duas funções: uma função pública que recebe apenas os dados necessários como argumentos e inicializa o acumulador, e uma função privada que também recebe um acumulador. Em Elixir, é um padrão comum acrescentar o prefixo do_ ao nome da função privada.
# Count the length of a list without an accumulator
def count([]), do: 0
def count([_head | tail]), do: 1 + count(tail)
# Count the length of a list with an accumulator
def count(list), do: do_count(list, 0)
defp do_count([], count), do: count
defp do_count([_head | tail], count), do: do_count(tail, count + 1)
A utilização de um acumulador permite transformar funções recursivas em funções recursivas de cauda. Uma função é recursiva de cauda se a última coisa executada pela função for uma chamada a si própria.
Instruções
No teu laboratório de investigação de ADN, tens vindo a explorar várias formas de comprimir os teus dados de investigação para poupar espaço de armazenamento. Um colega de equipa sugere converter os dados de ADN numa representação binária:
| Ácido nucleico |
Código |
| um espaço |
0000 |
| A |
0001 |
| C |
0010 |
| G |
0100 |
| T |
1000 |
Ficas a pensar nisto, porque pode reduzir para metade os custos de armazenamento necessários, mas à custa da legibilidade para as pessoas. Decides escrever um módulo para codificar e descodificar os teus dados, para avaliar a poupança.
1. Codifica o ácido nucleico num valor binário
Implementa encode_nucleotide/1 de modo a receber o ponto de código do ácido nucleico e devolver o valor inteiro do código codificado.
DNA.encode_nucleotide(?A)
# => 1
# (which is equal to 0b0001)
2. Descodifica o valor binário para o ácido nucleico
Implementa decode_nucleotide/1 de modo a receber o valor inteiro do código codificado e devolver o ponto de código do ácido nucleico.
DNA.decode_nucleotide(0b0001)
# => 65
# (which is equal to ?A)
3. Codifica uma charlist de ADN
Implementa encode/1 de modo a receber uma charlist que representa ácidos nucleicos e espaços e devolver uma bitstring com os dados codificados.
DNA.encode(~c"AC GT")
# => <<18, 4, 8::size(4)>>
4. Descodifica uma bitstring de ADN
Implementa decode/1 de modo a receber uma bitstring que representa ácidos nucleicos e espaços e devolver os dados descodificados como uma charlist.
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
Exercício de aprendizagem
