Keller

Die Rekursion benötigt meist einen Kellerspeicher. In diesem Kellerspeicher werden die einzelnen Funktionsaufrufe gespeichert. Man kann also davon ausgehen, daß in diesem Speicher der gesamte Verlauf des "Prozesses" gespeichert ist. Bei einem iterativen Programm spiegeln die einzelnen Variablen den Zustand des Berechnungsprozesses wieder - bei der Rekursion ist dieser Zustand über den gesamten Kellerspeicher verteilt. Würde man eine Berechnung anhalten und zu einem späteren Zeitpunkt weiterführen wollen, so müßte man sich bei einem iterativen Programm nur die Werte der Variablen merken, bei einem rekursiven Programm benötigt man auch noch den Inhalt des Kellerspeichers.

Beispiel: Rekursive Fakultätsberechnung (in Lisp)

(define (fakultät n)
    (if (= n 1)
        1
        (* n (fakultät (- n 1)))))

Funktionsaufruf des linear rekursiven Prozeß zur Berechnung von 6!

(fakultät 6)
(* 6 (fakultät 5))
(* 6 (* 5 (fakultät 4)))
(* 6 (* 5 (* 4 (fakultät 3))))
(* 6 (* 5 (* 4 (* 3 (fakultät 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (fakultät 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720