Rekursion

Das Grundmuster — Fakultät rekursiv

Die Fakultät n! ist das kanonische Lehrbuch-Beispiel: n! = n * (n-1)!, mit 0! = 1 als Abbruchbedingung. Direkt aus der Definition wird Go-Code:

package main

import "fmt"

// factorial berechnet n! rekursiv.
// - Base Case: n <= 1 -> 1  (Terminierung)
// - Recursive Case: n * factorial(n-1)  (Reduktion in Richtung Base Case)
func factorial(n int) int {
    if n <= 1 {
        return 1 // Base Case — die Rekursion endet hier
    }
    return n * factorial(n-1) // Recursive Case
}

func main() {
    for i := 0; i <= 6; i++ {
        fmt.Printf("%d! = %d\n", i, factorial(i))
    }
}

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720

Anders als in Sprachen mit speziellen Konstrukten (rec in OCaml) braucht Go keinen Hinweis am Funktions-Kopf — der Name factorial ist im Funktions-Scope ab dem Funktions-Header sichtbar und kann im Body aufgerufen werden. Auch Top-Level-Funktionen im selben Paket sehen sich gegenseitig ohne Forward-Declaration; Mutual Recursion funktioniert ohne Vorbereitung (mehr dazu in Abschnitt 4).

Die zwei Pflicht-Komponenten jeder Rekursion

Eine korrekte rekursive Funktion hat immer zwei Teile — fehlt einer davon, läuft sie ins Verderben:

Beide Bedingungen müssen zusammenpassen: Der Recursive Case muss das Argument so verändern, dass es irgendwann garantiert den Base Case trifft. Bei factorial(n-1) ist das offensichtlich — n wird kleiner und stößt bei 1 an. Bei komplexeren Strukturen (Bäume, Graphen) ist das nicht selbstverständlich und einer der häufigsten Bug-Quellen.

// FEHLER: Kein Base Case — diese Funktion ruft sich endlos auf
func brokenFactorial(n int) int {
    return n * brokenFactorial(n-1)
    // Stack Overflow nach einigen Millionen Frames:
    // runtime: goroutine stack exceeds 1000000000-byte limit
}

// FEHLER: Base Case unerreichbar — n geht in die falsche Richtung
func wrongDirection(n int) int {
    if n == 0 {
        return 1
    }
    return wrongDirection(n + 1) // wächst weg vom Base Case
}

Die übliche Vorsicht: Bei negativen Argumenten oder unerwarteten Edge Cases vorab prüfen und entweder einen Fehler zurückgeben oder die Rekursion robust definieren. factorial(-3) würde mit dem ersten Code-Beispiel zum Glück sofort 1 zurückgeben (weil n <= 1 greift) — aber das ist Zufall, nicht Design.

Klassische Beispiele — Fibonacci und Tree-Traversal

Fibonacci-Zahlen sind das zweite Standard-Beispiel: fib(n) = fib(n-1) + fib(n-2), mit fib(0) = 0 und fib(1) = 1. Naiv geschrieben ist die Rekursion zwar korrekt — aber katastrophal langsam:

package main

import (
    "fmt"
    "time"
)

func fibNaive(n int) int {
    if n < 2 {
        return n
    }
    return fibNaive(n-1) + fibNaive(n-2)
}

func main() {
    for _, n := range []int{10, 20, 35, 40} {
        start := time.Now()
        v := fibNaive(n)
        fmt.Printf("fib(%d) = %d  (%.2fs)\n", n, v, time.Since(start).Seconds())
    }
}

fib(10) = 55  (0.00s)
fib(20) = 6765  (0.00s)
fib(35) = 9227465  (0.03s)
fib(40) = 102334155  (0.31s)

Die Laufzeit explodiert exponentiell — fib(50) dauert schon Minuten. Grund: dieselben Teil-Probleme werden vielfach neu berechnet (fib(38) wird beim Berechnen von fib(40) zweimal aufgerufen, beim Berechnen von fib(39) nochmal, usw.). Die Lösung — Memoization — folgt in Abschnitt 9.

Tree-Traversal ist der Fall, in dem Rekursion ihrer iterativen Variante deutlich überlegen ist — der Code spiegelt die Datenstruktur direkt wider:

package main

import "fmt"

type Node struct {
    Value    int
    Children []*Node
}

// sum durchwandert den Baum rekursiv und addiert alle Werte.
// Base Case: Knoten ohne Kinder — gib einfach den eigenen Wert zurück.
// Recursive Case: eigener Wert plus Summe aller Teilbäume.
func sum(n *Node) int {
    if n == nil {
        return 0
    }
    total := n.Value
    for _, child := range n.Children {
        total += sum(child) // rekursiver Abstieg
    }
    return total
}

func main() {
    root := &Node{
        Value: 1,
        Children: []*Node{
            {Value: 2, Children: []*Node{{Value: 5}, {Value: 6}}},
            {Value: 3},
            {Value: 4, Children: []*Node{{Value: 7}}},
        },
    }
    fmt.Println("Summe:", sum(root))
}

Summe: 28

Genau dasselbe Muster nutzt die Stdlib für Verzeichnis-Traversal: filepath.WalkDir ist intern rekursiv organisiert. Auch wenn der Aufrufer keine Rekursion schreibt, läuft sie unter der Haube — Datei-Bäume sind die natürliche Heimat des Patterns.

package main

import (
    "fmt"
    "io/fs"
    "path/filepath"
)

func main() {
    // WalkDir steigt rekursiv in jedes Unterverzeichnis hinab.
    // Der Callback bekommt jeden gefundenen Eintrag — Datei oder Ordner.
    err := filepath.WalkDir(".", func(path string, d fs.DirEntry, err error) error {
        if err != nil {
            return err
        }
        fmt.Println(path)
        return nil
    })
    if err != nil {
        fmt.Println("Fehler:", err)
    }
}

Mutual Recursion — zwei Funktionen rufen sich gegenseitig

Bei gegenseitiger Rekursion rufen zwei (oder mehr) Funktionen sich abwechselnd auf. Klassisches Beispiel: isEven und isOdd jeweils über die andere definieren:

package main

import "fmt"

func isEven(n int) bool {
    if n == 0 {
        return true
    }
    return isOdd(n - 1) // delegiert an die andere Funktion
}

func isOdd(n int) bool {
    if n == 0 {
        return false
    }
    return isEven(n - 1)
}

func main() {
    for i := 0; i < 5; i++ {
        fmt.Printf("%d: even=%v odd=%v\n", i, isEven(i), isOdd(i))
    }
}

0: even=true odd=false
1: even=false odd=true
2: even=true odd=false
3: even=false odd=true
4: even=true odd=false

Bemerkenswert: Go braucht keine Forward-Declaration. In C oder C++ müsstest du isOdd vor isEven als Prototyp deklarieren, weil der Compiler die Datei top-down liest. Gos Paket-Scope sieht alle Top-Level-Identifier auf einmal — die Reihenfolge der Funktionen ist beliebig. Auch über mehrere Files im selben Paket hinweg funktioniert das ohne Vorkehrungen.

Praktischer Einsatz von Mutual Recursion: Parser für gegenseitig referenzierende Grammatik-Regeln (Ausdruck enthält Term, Term enthält Ausdruck), State-Machines mit wenigen Zuständen, alternierende Tree-Walker. Für arithmetische Tricks wie even/odd ist es ein Lehrbuch-Beispiel — produktiv schreibt man n%2 == 0.

Anonyme Rekursion — der Self-Reference-Trick

Eine anonyme Funktion (Funktions-Literal ohne Name) kann sich nicht direkt selbst aufrufen — sie hat keinen Namen, an dem sie sich greifen könnte. Wer trotzdem Rekursion in einem Funktions-Literal braucht, weist die Funktion vorher einer benannten Variable zu:

package main

import "fmt"

func main() {
    // Schritt 1: var-Deklaration mit dem passenden Funktions-Typ.
    // Die Variable f ist jetzt im Scope und kann referenziert werden.
    var f func(int) int

    // Schritt 2: Funktions-Literal zuweisen, das f intern aufruft.
    f = func(n int) int {
        if n <= 1 {
            return 1
        }
        return n * f(n-1) // <- Self-Reference über die Variable
    }

    fmt.Println(f(5)) // 120
}

120

Warum var f func(int) int und kein f := func(...) { ... } in einem Schritt? Bei := ist die linke Variable erst nach der Auswertung des Initialisierers im Scope. Beim Aufruf von f im Funktions-Literal-Body wäre f noch undefiniert — Compile-Fehler. Mit var wird f zuerst angelegt (mit Zero Value nil), dann erst zugewiesen. Im Moment des Aufrufs (später, nicht beim Erzeugen des Literals) ist f dann definiert.

Y-Combinator-artige Konstrukte (Self-Reference ohne jede Namens-Bindung) lassen sich in Go theoretisch nachbauen, sind aber ein akademisches Spielzeug. Der oben gezeigte var-Trick ist die idiomatische Lösung.

Die Stack-Mechanik — warum Go tiefere Rekursionen verträgt

In klassischen Sprachen (C, C++, Java) hat jeder Thread einen festen, beim Start allozierten Stack — typisch 1–8 MB. Wer eine Rekursion zu tief treibt, läuft gegen diese Wand und kassiert einen Segmentation Fault. Go macht das anders: jede Goroutine startet mit einem winzigen Stack (aktuell ca. 2–8 KB) und der Runtime lässt ihn dynamisch wachsen.

Die Mechanik (Go ≥ 1.4):

• Jeder Funktions-Prolog enthält einen Stack-Guard-Check — eine billige Vergleichs-Instruktion. Reicht der verbleibende Platz nicht, springt der Code in den Runtime-Code zur Stack-Erweiterung.
• Die Runtime alloziert dann einen neuen, doppelt so großen Stack, kopiert den alten dorthin und passt alle internen Pointer an. Der Aufrufer merkt davon nichts.
• Das wiederholt sich nach Bedarf, bis die Goroutine entweder fertig ist oder den globalen Stack-Limit erreicht.

Die Go-FAQ formuliert es so:

„To make the stacks small, Go's run-time uses resizable, bounded stacks. A newly minted goroutine is given a few kilobytes, which is almost always enough. When it isn't, the run-time grows (and shrinks) the memory for storing the stack automatically, allowing many goroutines to live in a modest amount of memory."

Der Default-Maximalwert ist 1 GB pro Goroutine auf 64-Bit-Systemen, konfigurierbar über runtime/debug.SetMaxStack. Bei 2 KB pro Stack-Frame wären das theoretisch ca. 500000 Rekursions-Ebenen — in der Praxis weniger, weil ein Frame mit lokalen Variablen schnell mehr als 2 KB belegt. Aber: Größenordnungen mehr als in C/Java mit Default-Konfiguration.

package main

import "fmt"

// depth zählt nur — kein Nutzen außer als Tiefen-Test.
func depth(n int) int {
    if n == 0 {
        return 0
    }
    return 1 + depth(n-1)
}

func main() {
    // 100000 Rekursions-Ebenen — in C: garantierter Stack Overflow.
    // In Go: läuft durch, der Stack wächst transparent mit.
    fmt.Println(depth(100000))
}

100000

Stack Overflow — wann es doch passiert

„Dynamisch wachsend" heißt nicht „unbegrenzt". Wer eine Endlos-Rekursion baut oder die Tiefe wirklich überzieht, kassiert eine eindeutige Fehlermeldung:

package main

// Endlos-Rekursion ohne Base Case — bricht ab, sobald der Stack-Limit erreicht ist.
func endless(n int) int {
    return endless(n + 1)
}

func main() {
    endless(0)
}

// Ausgabe (gekürzt):
// runtime: goroutine stack exceeds 1000000000-byte limit
// runtime: sp=0xc020100380 stack=[0xc020100000, 0xc040100000]
// fatal error: stack overflow

Im Unterschied zu C ist das ein expliziter Runtime-Fehler mit klarer Diagnose — nicht ein stiller Segfault. Du siehst sofort, dass der Stack gesprengt wurde, und der Stack-Trace zeigt den letzten Frame.

Den Limit kannst du programmatisch anheben oder absenken:

package main

import "runtime/debug"

func main() {
    // Limit auf 4 GB hochsetzen — sinnvoll für Tools mit tiefen Bäumen.
    debug.SetMaxStack(4 * 1024 * 1024 * 1024)

    // Auf 1 MB absenken — schneller Stack Overflow zum Testen.
    // debug.SetMaxStack(1 * 1024 * 1024)
}

In der Praxis ist das selten nötig. Wenn du den Default sprengst, ist meist die Rekursion das Problem, nicht der Limit — entweder fehlt der Base Case, oder das Problem skaliert nicht mit Rekursion und gehört in eine iterative Variante.

Keine Tail-Call-Optimierung — und warum

In funktionalen Sprachen (Scheme, OCaml, Haskell) ist die Tail-Call-Optimierung (TCO) Pflicht: Wenn der allerletzte Schritt einer Funktion ein Aufruf einer anderen (oder derselben) Funktion ist, kann der Compiler den aktuellen Stack-Frame durch den neuen ersetzen statt einen weiteren draufzulegen. Damit verbraucht selbst tiefste Rekursion konstanten Stack-Platz — sie wird zur Schleife.

Go hat das bewusst nicht. Die Begründung aus dem Sprachdesign-Umfeld: TCO macht Stack-Traces unbrauchbar, weil die Zwischen-Frames fehlen. In einem Sprach-Ökosystem, das stark auf Debugging und Stack-Traces setzt (Panic-Output, Profiling, Goroutine-Dumps), wäre das ein schlechter Tausch.

Konsequenz für deinen Code: Jeder rekursive Aufruf belegt einen echten Stack-Frame, auch wenn er als letztes Statement vor return steht.

// Diese Funktion ist „tail-recursive" — der rekursive Aufruf ist die letzte Operation.
// In Scheme/OCaml würde sie zu einer Schleife optimiert, konstanter Stack.
// In Go: jeder Aufruf belegt einen vollen Frame, Stack wächst linear mit n.
func sumTail(n, acc int) int {
    if n == 0 {
        return acc
    }
    return sumTail(n-1, acc+n) // Tail Call — aber Go optimiert nicht
}

// Iterative Variante — konstanter Stack, gleiche Komplexität.
func sumIter(n int) int {
    acc := 0
    for i := n; i > 0; i-- {
        acc += i
    }
    return acc
}

Praxis-Konsequenz: Bei Algorithmen, die in funktionalen Sprachen elegant tail-rekursiv geschrieben werden, lohnt sich in Go meist die iterative Variante — gleiche Lesbarkeit, deutlich weniger Stack-Verbrauch, oft schneller (weniger Funktions-Aufruf-Overhead).

Memoization — überlappende Subprobleme cachen

Zurück zu Fibonacci. Die naive Variante aus Abschnitt 3 berechnet fib(38) mehrere hundertmal — jeder Teil-Baum wird neu durchlaufen. Memoization legt jedes Zwischenergebnis in einer Map ab und liefert es beim zweiten Bedarf direkt zurück:

package main

import (
    "fmt"
    "time"
)

func fibMemo() func(int) int {
    cache := map[int]int{0: 0, 1: 1}
    var fib func(int) int
    fib = func(n int) int {
        if v, ok := cache[n]; ok {
            return v
        }
        v := fib(n-1) + fib(n-2)
        cache[n] = v
        return v
    }
    return fib
}

func main() {
    fib := fibMemo()
    for _, n := range []int{40, 50, 70, 90} {
        start := time.Now()
        v := fib(n)
        fmt.Printf("fib(%d) = %d  (%v)\n", n, v, time.Since(start))
    }
}

fib(40) = 102334155  (15µs)
fib(50) = 12586269025  (3µs)
fib(70) = 190392490709135  (4µs)
fib(90) = 2880067194370816120  (6µs)

Aus exponentieller Laufzeit wird linear. Der Trick funktioniert immer, wenn die Subprobleme sich überlappen — also der gleiche Eingabe-Wert mehrfach berechnet würde. Bei reinen Tree-Traversals (jeder Knoten genau einmal besucht) bringt Memoization nichts; bei klassischen DP-Problemen (Fibonacci, Coin Change, Longest Common Subsequence) ist sie der Schlüssel.

Ein paar Details des obigen Codes: Die Variable fib wird über den Self-Reference-Trick aus Abschnitt 5 aufgebaut. Das cache ist als Closure-State gekapselt — fibMemo() gibt eine konfigurierte Funktion zurück, die ihren Cache mitschleppt.

Iterative Alternative — Schleife oder expliziter Stack

Jede rekursive Funktion lässt sich theoretisch in eine iterative umschreiben. Bei linearer Rekursion (factorial, sum) ist das trivial — eine for-Schleife reicht. Bei verzweigter Rekursion (Tree-Traversal, Backtracking) braucht man einen expliziten Stack als Slice, um die offene Arbeit zu verwalten.

Fakultät, iterativ:

package main

import "fmt"

func factorialIter(n int) int {
    result := 1
    for i := 2; i <= n; i++ {
        result *= i
    }
    return result
}

func main() {
    for i := 0; i <= 6; i++ {
        fmt.Printf("%d! = %d\n", i, factorialIter(i))
    }
}

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720

Tree-Traversal mit explizitem Stack:

package main

import "fmt"

type Node struct {
    Value    int
    Children []*Node
}

// sumIter durchwandert den Baum ohne Rekursion.
// Ein Slice agiert als expliziter Stack — Push am Ende, Pop am Ende (LIFO).
func sumIter(root *Node) int {
    if root == nil {
        return 0
    }
    total := 0
    stack := []*Node{root}
    for len(stack) > 0 {
        // Pop
        n := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        total += n.Value
        // Push aller Kinder
        stack = append(stack, n.Children...)
    }
    return total
}

func main() {
    root := &Node{
        Value: 1,
        Children: []*Node{
            {Value: 2, Children: []*Node{{Value: 5}, {Value: 6}}},
            {Value: 3},
            {Value: 4, Children: []*Node{{Value: 7}}},
        },
    }
    fmt.Println("Summe:", sumIter(root))
}

Summe: 28

Vergleich der Varianten:

Faustregel: Für lineare Rekursion (Iteration über eine Folge) ist die Schleife immer besser. Für Baum- und Graph-Strukturen ist die rekursive Form lesbarer und idiomatisch — wenn die Tiefe in vernünftigem Rahmen bleibt. Erst bei pathologisch tiefen Bäumen lohnt der explizite Stack.

Weiterführende Ressourcen

Externe Quellen

• Function declarations – Go Language Specification
• Go FAQ: Why goroutines instead of threads (Stack-Management)
• runtime/debug.SetMaxStack
• filepath.WalkDir – rekursives Datei-System-Walking
• Contiguous stacks – Design-Dokument Go 1.4

Verwandte Artikel

• Funktionen – Übersicht über alle Funktions-Mechaniken
• Multiple Returns – das (wert, err)-Pattern
• Variadic Functions – Funktionen mit beliebiger Argument-Anzahl
• Closures – Funktionen mit gekapseltem State
• First-Class Funktionen – Funktionen als Werte
• for-Schleife – die iterative Alternative
• defer mit Stolperfallen – LIFO-Stack pro Funktion