Rekursiv

Et matematisk begreb, som også benyttes i forbindelse med procedurer eller underprogrammer. Rekursivitet betyder, at noget er defineret ved sig selv; i procedure-sammenhæng at proceduren kalder sig selv, enten direkte eller indirekte gennem kald af en procedure, der kalder en procedure, der til sidst kalder den første procedure. Mange problemstillinger løses særdeles simpelt og elegant med rekursiv programmering. F.eks. kan man i ML skrive fakultetsfunktionen "fak" (defineret ved fak(n) = n! = 123* ... *n)

    fun fak n = if n = 1 then 1 else fak (n-1) * n

Det er ikke alle programmeringssprog, der tillader dette; eksempler på sprog med mulighed for rekursiv programmering er LISP, ALGOL, Pascal og ADA.

Rekursivitet kræver normalt en stakorienteret udførelse af programmet. Rekursivitet er beslægtet med begrebet iteration (se iterativ), som er en gentagelsesproces, men som ikke kræver en stak. Se også reentrant.