Introduction
Récursion terminale
Lorsqu'on fait de la récursion sur des énumérables (listes, bitstrings, strings), deux préoccupations reviennent souvent :
- la quantité de mémoire nécessaire pour conserver la trace des appels de fonctions récursives
- la manière de construire la solution efficacement
Pour répondre à ces préoccupations, on peut utiliser un accumulateur.
Un accumulateur est une variable que l'on transmet en plus des données. Il sert à faire passer l'état courant de l'exécution de la fonction, d'un appel à l'autre, jusqu'à ce que le cas de base soit atteint. Dans le cas de base, l'accumulateur sert à renvoyer la valeur finale de l'appel de la fonction récursive.
Les accumulateurs doivent être initialisés par l'auteur de la fonction, et non par celui qui l'utilise. Pour cela, on déclare deux fonctions : une fonction publique qui prend en arguments uniquement les données nécessaires et qui initialise l'accumulateur, et une fonction privée qui prend aussi un accumulateur. En Elixir, il est courant de préfixer le nom de la fonction privée par 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)
L'utilisation d'un accumulateur permet de transformer des fonctions récursives en fonctions récursives terminales. Une fonction est récursive terminale si la dernière chose exécutée par la fonction est un appel à elle-même.
Instructions
Dans ton laboratoire de recherche sur l'ADN, tu as exploré différentes façons de compresser tes données de recherche pour économiser de l'espace de stockage. Un membre de ton équipe suggère de convertir les données d'ADN en une représentation binaire :
| Acide nucléique |
Code |
| un espace |
0000 |
| A |
0001 |
| C |
0010 |
| G |
0100 |
| T |
1000 |
Tu réfléchis à cette idée : elle pourrait diviser par deux l'espace de stockage nécessaire, mais au prix de la lisibilité pour un humain. Tu décides d'écrire un module pour encoder et décoder tes données afin de mesurer les économies réalisées.
1. Encode un acide nucléique en valeur binaire
Implémente encode_nucleotide/1 pour accepter le point de code de l'acide nucléique et renvoyer la valeur entière du code encodé.
DNA.encode_nucleotide(?A)
# => 1
# (which is equal to 0b0001)
2. Décode la valeur binaire en acide nucléique
Implémente decode_nucleotide/1 pour accepter la valeur entière du code encodé et renvoyer le point de code de l'acide nucléique.
DNA.decode_nucleotide(0b0001)
# => 65
# (which is equal to ?A)
3. Encode une charlist d'ADN
Implémente encode/1 pour accepter une charlist représentant des acides nucléiques et des espaces, et renvoyer un bitstring des données encodées.
DNA.encode(~c"AC GT")
# => <<18, 4, 8::size(4)>>
4. Décode un bitstring d'ADN
Implémente decode/1 pour accepter un bitstring représentant des acides nucléiques et des espaces, et renvoyer les données décodées sous forme de charlist.
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
Exercice d'apprentissage
