Introducción
Recursión de cola
Cuando recorres enumerables (arrays, bitstrings, strings) mediante recursión, a menudo hay dos cuestiones que tener en cuenta:
- cuánta memoria se necesita para almacenar la secuencia de llamadas recursivas a la función
- cómo construir la solución de forma eficiente
Para abordar estas cuestiones se puede usar un acumulador.
Un acumulador es una variable que se pasa junto con los datos. Se usa para ir pasando 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.
Los acumuladores debe inicializarlos el autor de la función, no quien la usa. Para lograrlo, declara dos funciones: una función pública que recibe únicamente los datos necesarios como argumentos e inicializa el acumulador, y una función privada que también recibe un acumulador. En Elixir, es un patrón habitual 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 buscando distintas formas de comprimir los datos de tu investigación para ahorrar espacio de almacenamiento. Un compañero de 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 los costes de almacenamiento necesarios, pero a costa de la legibilidad para las personas. Decides escribir un módulo para codificar y decodificar tus datos y así poder medir el ahorro.
1. Codifica un á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 un charlist de ADN
Implementa encode/1 para que acepte un charlist que represente ácidos nucleicos y huecos y devuelva un bitstring con 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 huecos y devuelva los datos decodificados como un charlist.
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
Ejercicio de aprendizaje
