Gehaxelts Blog

In diesem Blogpost möchte ich die verschiedenen Arten der Rekursion vorstellen.

Man kann in der Programmierung Rekursion verwenden um Schleifen zu “simulieren”, was z.B. in funktionalen Programmiersprachen von Vorteil ist, da es dort keine Variablen und somit keine Schleifen gibt.

Unterteilung

Man unterteilt in die direkte bzw. indirekte Rekursion. Bei der direkten Rekursion ruft sich eine Funktion wieder selbst auf. Bei der indirekten Rekursion ruft die Funktion eine andere Funktion auf, welche wiederum die aufrufende Funktion aufruft.

Zitat:

Um die Rekursion zu verstehen, muss man zunächst die Rekursion verstehen

Direkte Rekursion

Bei der direkten Rekursion unterscheidet man vier verschiedene Arten:

Repetitive Rekursion

Bei der repetitiven Rekursion ruft sich die Funktion mit einem veränderten Parameter auf:

Beispiel:

1
2
3
4
5

def func(x,y):
  if x == 0:
      return y
  y=y+x
  return func(x-1,y)

Lineare Rekursion

Bei der linearen Rekursion wird der übergebene Parameter mit dem Rekursionsergebnis verrechnet:

Beispiel:

1
2
3
4

def func(x):
  if x == 0:
      return 1
  return x*func(x-1)

Baumartige Rekursion

Die baumartige Rekursion kommt zum Einsatz, wenn man das Ergebnis aus zwei verschiedenen Rekursionsaufrufen berechnet.

Beispiel:

1
2
3
4

def func(x):
  if x == 1:
      return 0 
  return func(x-1) + func(x-2)

Geschachtelte Rekursion

Bei der geschachtelten Rekursion ist das Ergebnis des Rekursionsaufrufes Parameter eines Rekursionsaufrufes.

Beispiel:

1
2
3
4

def func(x):
  if x == 1:
      return 0
  return func(x - func(x-1))

Verschränkte Rekursion

Bei der verschränkten Rekursion rufen sich zwei Funktionen gegenseitig auf.

Beispiel:

1
2
3
4
5
6
7
8
9

def func(x):
  if x== 0:
      return 1
  return g(x-1)

def g(x):
  if x== 1:
      return 0
  return f(x-1)

Fazit

Ihr habt nun eine kleine Übersicht über die verschiedenen Rekursionsarten.

Gruß

gehaxelt