Rekursion
Definition: Rekursion ist ein allgemeines Verfahren, bei dem ein Konzept direkt oder indirekt durch sich selbst definiert wird.
Beispiel: Eine Liste ist entweder leer oder besteht aus einer Liste gefolgt von einner Liste.
Definition: Ein Algorithmus heißt rekursiv, wenn er sich selbst aufruft.
Beispiel: Die Fakultät fac(n) einer ganzen Zahl n > 0 ist definiert durch
mit der „Startbedingung“ fac(0) = 1.
Weitere Beispiele: Euklidischer Algorithmus, Türme von Hanoi, Ariadne Faden u.a.