Introducción
Recursión de cola
Cuando se recursa a través de enumerables (arrays, bitstrings, strings), a menudo surgen dos preocupaciones:
- cuánta memoria se requiere para almacenar la secuencia de llamadas recursivas a funciones
- cómo construir la solución de manera eficiente
Para abordar estas preocupaciones se puede usar un acumulador.
Un acumulador es una variable que se pasa junto con los datos. Se usa para pasar el estado actual de la ejecución de la función, de llamada en llamada, hasta llegar al caso base. En el caso base, el acumulador se usa para devolver el valor final de la llamada recursiva a la función.
Quien escribe la función debe inicializar los acumuladores, no quien la usa. Para lograr esto, declara dos funciones: una función pública que recibe solo los datos necesarios como argumentos y que inicializa el acumulador, y una función privada que también recibe un acumulador. En Elixir, es un patrón común anteponer do_ al nombre de la función 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)
El uso de un acumulador nos permite convertir funciones recursivas en funciones recursivas de cola. Una función es recursiva de cola si lo último que se ejecuta en ella es una llamada a sí misma.
Instrucciones
En tu laboratorio de investigación de ADN, has estado probando varias formas de comprimir tus datos de investigación para ahorrar espacio de almacenamiento. Alguien de tu equipo sugiere convertir los datos de ADN a una representación binaria:
| Ácido nucleico |
Código |
| un espacio |
0000 |
| A |
0001 |
| C |
0010 |
| G |
0100 |
| T |
1000 |
Le das vueltas a la idea, ya que podría reducir a la mitad el costo del almacenamiento de datos, aunque a costa de la legibilidad humana. Decides escribir un módulo para codificar y decodificar tus datos y así medir cuánto ahorras.
1. Codifica el ácido nucleico a un valor binario
Implementa encode_nucleotide/1 para que acepte el punto de código del ácido nucleico y devuelva el valor entero del código codificado.
DNA.encode_nucleotide(?A)
# => 1
# (which is equal to 0b0001)
2. Decodifica el valor binario al ácido nucleico
Implementa decode_nucleotide/1 para que acepte el valor entero del código codificado y devuelva el punto de código del ácido nucleico.
DNA.decode_nucleotide(0b0001)
# => 65
# (which is equal to ?A)
3. Codifica una charlist de ADN
Implementa encode/1 para que acepte una charlist que represente ácidos nucleicos y espacios y devuelva un bitstring de los datos codificados.
DNA.encode(~c"AC GT")
# => <<18, 4, 8::size(4)>>
4. Decodifica un bitstring de ADN
Implementa decode/1 para que acepte un bitstring que represente ácidos nucleicos y espacios y devuelva los datos decodificados como una charlist.
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
Ejercicio de aprendizaje
