Rekursion verstehen

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software engineer

Definition

Funktion ruft sich selbst auf
Fast alle Fälle, in denen wir Schleifen nutzen
- können durch Rekursion ersetzt werden
Löst Probleme, die zunächst sehr komplex wirken

Beispiel – Fakultät

$n!$

Beispiel – Fakultät

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

Beispiel – Fakultät mit Rekursion

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)

Läuft endlos!

Beispiel – Basisfall erkennen

Eine Bedingung hinzufügen
- sorgt dafür, dass der Algorithmus nicht endlos läuft
Fakultät: Basisfall -> $n=1$

def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

So funktioniert Rekursion

Der Computer nutzt einen Stack, um Funktionen zu verfolgen
- Call Stack

So funktioniert Rekursion

factorial(5) startet
Bevor factorial(5) endet -> startet factorial(4)
Bevor factorial(4) endet -> startet factorial(3)

Ein Bild einer Warteschlange mit einem Element, das eine Funktion darstellt.

So funktioniert Rekursion

factorial(5) startet
Bevor factorial(5) endet -> startet factorial(4)
Bevor factorial(4) endet -> startet factorial(3)
Bevor factorial(3) endet -> startet factorial(2)

Ein Bild einer Warteschlange mit zwei Elementen, die zwei Funktionen darstellen.

So funktioniert Rekursion

factorial(5) startet
Bevor factorial(5) endet -> startet factorial(4)
Bevor factorial(4) endet -> startet factorial(3)
Bevor factorial(3) endet -> startet factorial(2)
Bevor factorial(2) endet -> startet factorial(1)

Ein Bild einer Warteschlange mit drei Elementen, die drei Funktionen darstellen.

So funktioniert Rekursion

factorial(5) startet
Bevor factorial(5) endet -> startet factorial(4)
Bevor factorial(4) endet -> startet factorial(3)
Bevor factorial(3) endet -> startet factorial(2)
Bevor factorial(2) endet -> startet factorial(1)

Ein Bild einer Warteschlange mit vier Elementen, die vier Funktionen darstellen.

So funktioniert Rekursion

factorial(1) endet
- gibt 1 zurück
factorial(2) endet

Ein Bild einer Warteschlange mit vier Elementen, die vier Funktionen darstellen.

So funktioniert Rekursion

factorial(1) endet
- gibt 1 zurück
factorial(2) endet
- gibt 2 zurück

Ein Bild einer Warteschlange mit vier Elementen, die vier Funktionen darstellen. Die letzte Funktion ist mit ihrem Rückgabewert versehen.

So funktioniert Rekursion

factorial(1) endet
- gibt 1 zurück
factorial(2) endet
- gibt 2 zurück
factorial(3) endet
- gibt 6 zurück

Ein Bild einer Warteschlange mit drei Elementen, die drei Funktionen darstellen.

So funktioniert Rekursion

factorial(1) endet
- gibt 1 zurück
factorial(2) endet
- gibt 2 zurück
factorial(3) endet
- gibt 6 zurück
factorial(4) endet
- gibt 24 zurück

Ein Bild einer Warteschlange mit zwei Elementen, die zwei Funktionen darstellen.

So funktioniert Rekursion

factorial(1) endet
- gibt 1 zurück
factorial(2) endet
- gibt 2 zurück
factorial(3) endet
- gibt 6 zurück
factorial(4) endet
- gibt 24 zurück
factorial(5) endet
- gibt 120 zurück

Ein Bild einer Warteschlange mit einem Element, das eine Funktion darstellt.

So funktioniert Rekursion

factorial(1) endet
- gibt 1 zurück
factorial(2) endet
- gibt 2 zurück
factorial(3) endet
- gibt 6 zurück
factorial(4) endet
- gibt 24 zurück
factorial(5) endet
- gibt 120 zurück

Ein Bild einer leeren Warteschlange.

Dynamische Programmierung

Optimierungstechnik
Vor allem bei Rekursion angewendet
Kann die Komplexität rekursiver Algorithmen senken
Einsatz bei:
- Problemen, die in kleinere Teilprobleme zerlegbar sind
- Teilprobleme überschneiden sich
Teillösungen werden gespeichert, erneutes Berechnen entfällt
- Memoization

Lass uns üben!

Datenstrukturen und Algorithmen in Python