Rekursionssætningen spiller en vigtig rolle i forståelsen af ​​de operationer, der kan udføres på en Turing-maskine inden for rammerne af beregningsmæssig kompleksitetsteori. For at forstå dette forhold er det vigtigt først at forstå det grundlæggende i rekursion og dets betydning inden for datalogi. Rekursion refererer til processen med