Der Begriff Rekursionstheorie meint heute das gleiche wie der Begriff Berechenbarkeitstheorie, da die rekursiven Funktionen gerade die berechenbaren Funktionen sind.
Einge Autoren verwenden den Begriff Rekursion um nur die Funktionen mit expliziten Selbstbezug zu kennzeichnen.