Was ist Rekursion ?

"Ein Objekt heißt rekursiv, wenn ...es sich selbst als Teil enthält oder mit Hilfe seiner selbst definiert ist."
(aus: Niklaus Wirth: "Algorithmen und Datenstrukturen in Modula", 1986)
 
Rekursive Lösungen benötigen immer eine Abbruchbedingung, bei dem die Rekursion beendet werden soll und eine allgemeine Rekursionsvorschrift, die das Problem um (mindestens) einen Schritt vereinfacht .

Rekursive Programme sind in der Regel kurz und übersichtlich. Der Zweck eines Programms lässt sich unmittelbar aus dem Quelltext ableiten.
Allerdings ist die Rekursion sehr speicheraufwendig und damit auch zeitaufwendig, da der rekursive Selbstaufruf alle Variablen mehrfach im Arbeitspeicher halten muss (s.u.).