Bei einer sinnvollen Anwendung der Rekursion spielt das Problem des Speicherbedarfs keine Rolle. Es gibt aber Anwendungen, bei denen man es sich nicht leisten kann, Speicher zu verbrauchen. Ein Beispiel dafür ist die Garbage Collection nache dem 'Mark and Sweep'-Algorithmus. Hier ist es zwar sehr einfach eine rekursive Variante für die Mark-Phase zu schreiben - aber sie würde nicht taugen, da man nicht genug Speicherplatz für diese Operation besitzt. Also muß man auf eine iterative Variante zurückgreifen.

Beispiel: Rekursives Mark (in Oberon)

PROCEDURE Mark (p: Ptr);
    IF (p # NIL) & (!p.marked) THEN
        p.marked := TRUE;
        Mark(p.left);
        Mark(p.right);
    END;
END Mark;

Die iterative Variante ist etwas aufwendiger und auch nicht auf der ersten Blick verständlich. Der Weg durch den Speicher wird in den Zeigern selbst gespeichert.

Unendliche Rekursion

Ein weiteres Problem tritt auf, wenn die Rekursion nicht endet weil man z.B. einen Rekursionsendpunkt übersehen hatt. Hier könnte man sich helfen, indem bei jedem Funktionsaufruf die Rekursionstiefe als Parameter übergeben wird. Mittels dieses Sicherheitszähler ist man in der Lage, die Rekursion bei einer bestimmten Tiefe zu unterbrechen.