Rekursion in

Über 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.

Sehr oft wird jeder Fall in einer eigenen Funktionsklausel geschrieben.

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

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(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

Das Zählen der Vorkommen eines gegebenen Werts x in einer Liste hat zwei Rekursionsfälle:

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

Schleifen durch Rekursion

Aufgrund der Unveränderlichkeit werden Schleifen in Elixir anders geschrieben als in imperativen Sprachen. Zum Beispiel sehen Schleifen üblicherweise so aus:

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

In einer funktionalen Sprache ist es nicht möglich, i zu verändern (durch den Aufruf von i++). Deshalb müssen Schleifen mit Rekursion umgesetzt werden.

Das Äquivalent einer for-Schleife in Elixir würde so aussehen:

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

In der Praxis nutzt du zum Iterieren über Listen und andere aufzählbare Datenstrukturen meist das Modul Enum. Unter der Haube sind die Funktionen des Enum-Moduls mit Rekursion implementiert.

Endlose Ausführung

Falsch implementierte rekursive Funktionen geben ihr Ergebnis möglicherweise nie zurück. Das kann problematisch sein, denn bei jedem Aufruf einer Funktion wird im Speicher eine Referenz darauf abgelegt, wohin die VM das Ergebnis zurückgeben soll (auf dem Call Stack). Wenn eine rekursive Funktion sich unendlich oft selbst aufruft, kann der Speicher ausgehen und die VM abstürzen (ein Stack-Overflow-Fehler). Die Erlang-VM, auf der Elixir läuft, ist speziell auf Rekursion und Zuverlässigkeit optimiert. Deshalb kann es lange dauern, bis Fehler durch endlose Rekursion sichtbar werden oder es zu Abstürzen kommt.

Folgendes kann dieses Problem der endlosen Ausführung verursachen:

• Vergessen, einen Basisfall zu implementieren.
• Den Basisfall nicht als erste Klausel zu definieren.
• Das Argument beim rekursiven Aufruf nicht richtig zu verändern und so den Basisfall nie zu erreichen.