Einführung
Rekursion
Rekursive Funktionen sind Funktionen, die sich selbst aufrufen.
Eine rekursive Funktion braucht mindestens einen Basisfall und mindestens einen Rekursionsfall.
Ein Basisfall gibt einen Wert zurück, ohne die Funktion erneut aufzurufen.
Ein Rekursionsfall ruft die Funktion erneut auf und verändert dabei die Eingabe so, dass sie irgendwann zum Basisfall passt.
Hier ist ein Beispiel, das die Elemente eines Arrays zählt.
def count:
if length == 0 then
0 # base case
else
1 + (.[1:] | count) # recursive case
end;
([] | count), # => 0
([11, 22, 33] | count) # => 3
Eine rekursive Funktion kann viele Basisfälle und/oder viele Rekursionsfälle haben.
Zum Beispiel ist die Fibonacci-Folge eine rekursive Folge mit zwei Basisfällen.
def fibonacci:
if . == 0 then
0
elif . == 1 then
1
else
(. - 1 | fibonacci) + (. - 2 | fibonacci)
end;
10 | fibonacci # => 55
Das Zählen der Vorkommen eines gegebenen Werts x in einer Liste hat zwei Rekursionsfälle.
def count_occurrences(x):
if length == 0 then
0
elif first == x then
1 + (.[1:] | count_occurrences(x))
else
(.[1:] | count_occurrences(x))
end;
[11, 22, 33, 22, 44] | count_occurrences(22) # => 2
In der Praxis durchläuft man Listen und andere aufzählbare Datenstrukturen meistens mit eingebauten Funktionen wie map und reduce oder indem man Streams verwendet, etwa [.[] | select(...)].
Intern sind einige der eingebauten Funktionen mithilfe von Rekursion implementiert.
Anleitung
Du bist gerade einem Team beigetreten, das eine jq-basierte Datenpipeline betreut.
In deiner ersten Pairing-Session wird dein neuer Kollege neugierig:
„Weißt du, wie add, reverse und map unter der Haube funktionieren? Lass es uns herausfinden: Versuch, sie selbst mit Rekursion zu implementieren, ohne die eingebauten Filter."
1. Implementiere eine Funktion, die die Zahlen in einem Array addiert
Wir implementieren den eingebauten Filter add neu, um Rekursion zu üben.
Der Basisfall ist, dass ein leeres Array die Summe null hat.
Implementiere es selbst mit einer rekursiven Funktion; verwende nicht den eingebauten Filter add.
[5, 4, 6, 10] | array_add # => 25
2. Kehre ein Array um
Wir implementieren den eingebauten Filter reverse neu.
Der Basisfall ist, dass ein umgedrehtes leeres Array ein leeres Array ist.
Implementiere es selbst mit einer rekursiven Funktion; verwende nicht den eingebauten Filter reverse.
[5, 4, 6, 10] | array_reverse # => [10, 6, 4, 5]
3. Wende map auf ein Array an
Wir implementieren den eingebauten Filter map neu.
Die Funktion nimmt einen Filter als Parameter, wendet ihn auf jedes Element des Eingabe-Arrays an und gibt die Ergebnisse in einem neuen Array zurück.
Der Basisfall ist, dass map auf ein leeres Array angewendet ein leeres Array ergibt.
Implementiere es selbst mit einer rekursiven Funktion; verwende nicht den eingebauten Filter map.
[5, 4, 6, 10] | array_map(. + 10) # => [15, 14, 16, 20]
Lernübung
