Rekursion

Någonting är rekursivt om det anropar sig själv. Detta gäller allt från enkla datatyper till funktioner och hela program.

Rekursiva datatyper kallar man sådana datatyper som innehåller referenser till den egna typen. Notera att det är typen som refererar till sig själv, inte nödvändigtvis objekt skapat utifrån en rekursiv datatyp. Funktioner och procedurer som är rekursiva har ett anrop till sig själva och skapar på så sätt en loop i programmet. För att avbryta en sådan loop måste funktionen själv upptäcka att det är dags att sluta anropa sig själv. Man kallar detta att man når ett basfall.