Introdução
Recursão de cauda
Ao fazer recursão sobre enumeráveis (listas, bitstrings, strings), muitas vezes há duas preocupações:
- quanta memória é necessária para armazenar a trilha de chamadas recursivas de função
- como construir a solução de forma eficiente
Para lidar com essas preocupações, pode-se usar um acumulador.
Um acumulador é uma variável que é passada junto, além dos dados. Ele serve para passar o estado atual da execução da função, de chamada em chamada, até chegar ao caso base. No caso base, o acumulador é usado para retornar o valor final da chamada recursiva.
Os acumuladores devem ser inicializados por quem escreve a função, não por quem a usa. Para isso, declare 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. No Elixir, é um padrão comum prefixar o nome da função privada com do_.
# 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)
O uso 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 por ela é uma chamada a si mesma.
Instruções
No seu laboratório de pesquisa de DNA, você vem trabalhando em várias formas de comprimir seus dados de pesquisa para economizar espaço de armazenamento. Uma pessoa da equipe sugere converter os dados de DNA para uma representação binária:
| Ácido nucleico |
Código |
| um espaço |
0000 |
| A |
0001 |
| C |
0010 |
| G |
0100 |
| T |
1000 |
Você reflete sobre isso, já que pode reduzir pela metade o custo de armazenamento necessário, mas às custas da legibilidade para humanos. Você decide escrever um módulo para codificar e decodificar seus dados e medir a economia.
1. Codifique o ácido nucleico em valor binário
Implemente encode_nucleotide/1 para receber o code point do ácido nucleico e retornar o valor inteiro do código codificado.
DNA.encode_nucleotide(?A)
# => 1
# (which is equal to 0b0001)
2. Decodifique o valor binário para o ácido nucleico
Implemente decode_nucleotide/1 para receber o valor inteiro do código codificado e retornar o code point do ácido nucleico.
DNA.decode_nucleotide(0b0001)
# => 65
# (which is equal to ?A)
3. Codifique uma charlist de DNA
Implemente encode/1 para receber uma charlist que representa ácidos nucleicos e lacunas e retornar uma bitstring com os dados codificados.
DNA.encode(~c"AC GT")
# => <<18, 4, 8::size(4)>>
4. Decodifique uma bitstring de DNA
Implemente decode/1 para receber uma bitstring que representa ácidos nucleicos e lacunas e retornar os dados decodificados como uma charlist.
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
Exercício de aprendizagem
