Rekursjonsdybden

Rekursjonsdybden beskriver hvor mange ganger en funksjon kan kalle seg selv i løpet av en kjøring før programmet når en grense eller krasjer. Den svarer til den maksimale mengden aktive funksjonsrammer som kan være til stede samtidig. Rekursjonsdybden er derfor nært knyttet til kallestakken i programutførelsen og påvirkes av hvor stor hver ramme er og hvor mye minne stakken har til rådighet.

Faktorer som påvirker rekursjonsdybden inkluderer programmeringsspråket og kompilatoren, stakkstørrelsen i operativsystemet, og hvor mye minne hver funksjonskallramme bruker. Noen språk støtter tail call optimization (TCO), som kan redusere eller fjerne behovet for økt stakkdybde i enkelte rekursjonstyper. I andre språk blir rekursjon dyrere fordi stakken må vokse med hvert kall.

Konsekvenser: når rekursjonsdybden overskrides, kan programmet få en feil som kalles stack overflow. I Python kan dette kontrolleres via rekursjonsgrensen (standard rundt 1000) og kan økes med sys.setrecursionlimit, selv om det ofte er risikabelt. Java håndterer StackOverflowError. C og C++ avhenger av operativsystemets stakkstørrelse og kan også føre til segfault.

Håndtering: når rekursjon når uheldige dybder, kan man omforme til en iterativ løsning eller bruke en eksplisitt stakk til å simulere rekursjon. I språk som støtter tail call optimization, kan tail-rekursjon være relativt effektiv, men ikke alle språk garanterer TCO. I mange tilfeller kan algoritmiske endringer, for eksempel tre- eller graftraverser, med en iterativ tilnærming lindre problemet.