Rekursion in

Über Rekursion

Rekursive Funktionen sind Funktionen, die sich selbst aufrufen.

Eine rekursive Funktion braucht mindestens einen Basisfall und mindestens einen rekursiven Fall.

Ein Basisfall gibt einen Wert zurück, ohne die Funktion erneut aufzurufen. Ein rekursiver Fall ruft die Funktion erneut auf und verändert dabei den Eingabewert so, dass er 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 rekursive Fä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, wie oft ein gegebener Wert x in einer Liste vorkommt, hat zwei rekursive Fä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äufst du Listen und andere aufzählbare Datenstrukturen meistens mit eingebauten Funktionen wie map und reduce, oder indem du Streams verwendest wie [.[] | select(...)]. Unter der Haube sind einige eingebaute Funktionen mit Rekursion implementiert.

Unendliche Rekursion

Rekursive Funktionen, die falsch implementiert sind, geben ihr Ergebnis möglicherweise nie zurück. Das kann problematisch sein, denn bei jedem Aufruf einer Funktion wird im Speicher eine Referenz abgelegt, an die die VM das Ergebnis zurückgeben soll (auf dem Aufrufstapel). Wenn eine rekursive Funktion sich unendlich oft selbst aufruft, kann der Speicher ausgehen, und die VM stürzt mit einem Stapelüberlauf-Fehler ab.

Dieses Problem der unendlichen Rekursion kann folgende Ursachen haben:

• Du vergisst, einen Basisfall zu implementieren.
• Du definierst den Basisfall nicht als ersten Zweig.
• Du veränderst beim rekursiven Aufruf das Argument nicht richtig und erreichst so nie den Basisfall.

Endaufrufoptimierung

Wie in Wikipedia beschrieben:

Ein Endaufruf ist ein Unterprogrammaufruf, der als letzte Aktion einer Prozedur ausgeführt wird. Wenn das Ziel eines Endaufrufs dasselbe Unterprogramm ist, nennt man das Unterprogramm endrekursiv.

Betrachte die oben gezeigte Implementierung von fibonacci. Der rekursive Fall ruft sich selbst zweimal auf. Die letzte Aktion, die die Funktion ausführen muss, ist eine Addition. Da die letzte Aktion kein Aufruf ihrer selbst ist, ist diese Funktion zwar rekursiv, aber nicht endrekursiv.

Manche Sprachen implementieren Endaufrufoptimierung, sodass der Endaufruf den aktuellen Stackframe wiederverwenden kann, statt einen neuen Frame zum Aufrufstapel hinzufügen zu müssen. Das kann zusätzlich zum Schutz vor dem gefürchteten Stapelüberlauf auch die Performance verbessern.

jq implementiert die Endaufrufoptimierung tatsächlich, aber nur für nullstellige Funktionen. Um davon zu profitieren, definierst du eine „innere“ nullstellige Funktion, die eine Art Zustand als Eingabe nimmt. Die innere Funktion kann den Zustand nach Bedarf verändern und den neuen Zustand an den endrekursiven Aufruf übergeben. Die äußere Funktion erstellt den Anfangszustand und übergibt ihn an die innere Funktion, um die Rekursion zu starten.

Eine endrekursive fibonacci-Funktion könntest du implementieren, indem du die bisher berechnete Folge als Teil des Zustands beibehältst.

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55