Rekursion – Funktionen, die sich selbst aufrufen

Das lernst du

Verstehen, wie eine Funktion sich selbst aufrufen kann
Abbruchbedingung und rekursiven Schritt unterscheiden
Probleme in kleinere gleichartige Probleme zerlegen

Eine Funktion, die sich selbst aufruft

In der Turtle-Lektion hast du schon einen Baum gezeichnet, der sich selbst zeichnet. Das Prinzip heißt Rekursion: Eine Funktion löst ein Problem, indem sie eine kleinere Version desselben Problems an sich selbst weitergibt.

def countdown(n):
    if n == 0:
        print("Start! 🚀")
        return
    print(n)
    countdown(n - 1)


countdown(5)

Die zwei Zutaten

Jede Rekursion braucht genau zwei Dinge:

Abbruchbedingung – ein Fall, der so einfach ist, dass man die Antwort direkt kennt (oben: n == 0).
Rekursiver Schritt – das Problem wird ein Stück kleiner gemacht und weitergereicht (oben: countdown(n - 1)).

Fehlt die Abbruchbedingung, ruft sich die Funktion endlos selbst auf:

def endlos(n):
    return endlos(n + 1)


endlos(1)

Python bricht nach etwa 1000 Aufrufen mit einem RecursionError ab – zum Glück!

Rekursion mit Ergebnis

def summe_bis(n):
    if n == 1:
        return 1
    return n + summe_bis(n - 1)


print(summe_bis(4))   # 4 + 3 + 2 + 1

So denkt Python dabei: summe_bis(4) = 4 + summe_bis(3) = 4 + 3 + summe_bis(2) = 4 + 3 + 2 + summe_bis(1) = 4 + 3 + 2 + 1 = 10. Schau es dir mit ⏯ Schritte an!

Wofür braucht man das?

Rekursion ist ideal für Dinge, die in sich selbst verschachtelt sind: Ordner mit Unterordnern, Stammbäume, Labyrinthe, Fraktale – und viele schnelle Sortierverfahren.

ordner = {"Fotos": {"Urlaub": {"strand.jpg": 0}, "hund.jpg": 0}, "notiz.txt": 0}


def zaehle_dateien(inhalt):
    anzahl = 0
    for name, wert in inhalt.items():
        if isinstance(wert, dict):
            anzahl += zaehle_dateien(wert)   # Unterordner: gleiche Frage, kleiner
        else:
            anzahl += 1
    return anzahl


print(zaehle_dateien(ordner), "Dateien")

Kurz-Check

Was gibt dieses Programm aus?

def f(n):
    if n <= 1:
        return 1
    return f(n - 1) + f(n - 2)


print(f(5))

Deine Aufgabe

Jetzt bist du dran

Schreib zwei Funktionen rekursiv (also ohne Schleife, die Funktion ruft sich selbst auf). fakultaet(n) berechnet n! = n · (n−1) · … · 1, mit fakultaet(0) == 1. quersumme(n) addiert die Ziffern einer Zahl: quersumme(472) == 13 (Tipp: n % 10 ist die letzte Ziffer, n // 10 der Rest davor).

def fakultaet(n):
    pass


def quersumme(n):
    pass


print(fakultaet(5))
print(quersumme(472))

Denkanstoß
Abbruch: bei n == 0 gib 1 zurück. Sonst: n * fakultaet(n - 1).
Welcher Befehl hilft?
Abbruch: eine einstellige Zahl ist ihre eigene Quersumme. Sonst: letzte Ziffer (n % 10) + quersumme(n // 10).
Die Funktion muss sich in ihrem eigenen Körper selbst aufrufen – und es soll keine for- oder while-Schleife vorkommen.

Lückencode – ergänze die ___

                        def fakultaet(n):
    if ___:
        return ___
    return ___


def quersumme(n):
    if ___:
        return ___
    return ___


print(fakultaet(5))
print(quersumme(472))

Ohne Hinweise gelöst gibt es einen ⭐ auf deiner Fortschrittsseite.

Lösung anzeigen

Versuch es erst selbst – aus Fehlern lernt man am meisten. Hier ist eine mögliche Lösung:

def fakultaet(n):
    if n == 0:
        return 1
    return n * fakultaet(n - 1)


def quersumme(n):
    if n < 10:
        return n
    return n % 10 + quersumme(n // 10)


print(fakultaet(5))
print(quersumme(472))