פונקציה רקורסיבית – הבדלי גרסאות

הפונקציות הרקורסיביות מתקבלות מהפונקציות הרקורסיביות-פרמטיביות על ידי הוספת אופטור, שמכונה אופרטור <math>\mu</math> או אופרטור החיפוש. נסמן את קבוצת הפונקציות הרקורסיביות הפועלות על קלט בן k מספרים ב- <math>\ R^{(k)}</math>. אופרטור זה פועל על פונקציה רקורסיבית קיימת <math>\ f \in R^{(k+1)}</math>, ומחזיר את הפונקציה <math>\ \mu f (\in R^{(k)} )</math>, שעבור הקלט <math>\ (x_1, \dots , x_k)</math> מחזירה כפלט את ה-y המינימלי שעבורו מתקיים השיוויון <math>\ f(y,x_1, \dots , x_n ) =1</math>. y כזה לא בהכרח קיים, ורק אם הוא קיים הפונקציה עוצרת על אותו קלט. פונקציות אלו הן פונקציות חלקיות, כלומר הן אינן מוגדרות על כל קלט ולפעמים אפילו על שום קלט. לדוגמא הפעלת אופרטור <math>\mu</math> על הפונקציה הפרמטיבית-רקורסיבית הקבועה 1 תיצור בהכרח פונקציה שלא מוגדרת על שום מספר טבעי.