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

'''פונקציה רקורסיבית''' היא [[פונקציה]] מתת קבוצה של [[מספר טבעי|המספרים הטבעיים]] לעצמם, הנחשבת, באופן אינטואיטיבי, כ"ניתנת לחישוב". בפרט, [[תורת החישוביות]] מראה כי הפונקציות הרקורסיביות הן בדיוק אותן פונקציות שניתנות לחישוב בידי [[מכונת טיורינג]], הנחשבת (על פי [[תזת צ'רץ'-טיורינג]]) כמודל הכללי ביותר של חישוב סביר.

 

 

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