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

למעשה, ההבדל בין הפונקציות הרקורסיביות והפונקציות הרקורסיביות-פרמטיביות הוא באפשרות של הפונקציה לא לעצור על קלט מסויים. הפונקציות הפרמיטיביות בהכרח עוצרות על כל קלט, ולכן הן מתאימות לקבוצת מכונות הטיורינג שתמיד עוצרות. לעומתן הפונקציות הרקורסיביות לא מוגבלות בתנאי הזה והן יכולות שלא לעצור על שום קלט. יש לציין שהתאמה הזו היא חד-כיוונית כלומר קיימת פונקציה רקורסיבית שאינה פרימיטיבית ועוצרת על כל קלט.