Einführung
Endrekursion
Wenn du rekursiv durch Enumerables (Listen, Bitstrings, Strings) gehst, gibt es oft zwei Dinge zu bedenken:
- wie viel Speicher benötigt wird, um die Spur der rekursiven Funktionsaufrufe zu speichern
- wie du die Lösung effizient aufbaust
Um diese Punkte in den Griff zu bekommen, kannst du einen Akkumulator verwenden.
Ein Akkumulator ist eine Variable, die zusätzlich zu den Daten übergeben wird. Damit gibst du den aktuellen Zustand der Ausführung der Funktion von einem Funktionsaufruf zum nächsten weiter, bis der Basisfall erreicht ist. Im Basisfall wird mit dem Akkumulator der endgültige Wert des rekursiven Funktionsaufrufs zurückgegeben.
Den Akkumulator sollte der Autor der Funktion initialisieren, nicht ihr Nutzer. Dazu deklarierst du zwei Funktionen: eine öffentliche Funktion, die nur die nötigen Daten als Argumente entgegennimmt und den Akkumulator initialisiert, und eine private Funktion, die zusätzlich einen Akkumulator entgegennimmt. In Elixir ist es ein verbreitetes Muster, dem Namen der privaten Funktion do_ voranzustellen.
# 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)
Mit einem Akkumulator kannst du rekursive Funktionen in endrekursive Funktionen umwandeln. Eine Funktion ist endrekursiv, wenn das Letzte, was die Funktion ausführt, ein Aufruf ihrer selbst ist.
Anleitung
In deinem DNA-Forschungslabor hast du verschiedene Wege ausprobiert, deine Forschungsdaten zu komprimieren, um Speicherplatz zu sparen. Ein Teammitglied schlägt vor, die DNA-Daten in eine binäre Darstellung umzuwandeln:
| Nukleinsäure |
Code |
| ein Leerzeichen |
0000 |
| A |
0001 |
| C |
0010 |
| G |
0100 |
| T |
1000 |
Du denkst darüber nach, denn das könnte die benötigten Speicherkosten halbieren, allerdings auf Kosten der menschlichen Lesbarkeit. Du beschließt, ein Modul zu schreiben, das deine Daten kodiert und dekodiert, um deine Einsparungen zu messen.
1. Nukleinsäure in einen Binärwert kodieren
Implementiere encode_nucleotide/1, sodass die Funktion den Codepunkt der Nukleinsäure entgegennimmt und den ganzzahligen Wert des kodierten Codes zurückgibt.
DNA.encode_nucleotide(?A)
# => 1
# (which is equal to 0b0001)
2. Den Binärwert in die Nukleinsäure dekodieren
Implementiere decode_nucleotide/1, sodass die Funktion den ganzzahligen Wert des kodierten Codes entgegennimmt und den Codepunkt der Nukleinsäure zurückgibt.
DNA.decode_nucleotide(0b0001)
# => 65
# (which is equal to ?A)
3. Eine DNA-Zeichenliste kodieren
Implementiere encode/1, sodass die Funktion eine Zeichenliste entgegennimmt, die Nukleinsäuren und Lücken repräsentiert, und einen Bitstring der kodierten Daten zurückgibt.
DNA.encode(~c"AC GT")
# => <<18, 4, 8::size(4)>>
4. Einen DNA-Bitstring dekodieren
Implementiere decode/1, sodass die Funktion einen Bitstring entgegennimmt, der Nukleinsäuren und Lücken repräsentiert, und die dekodierten Daten als Zeichenliste zurückgibt.
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
Lernübung
