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

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