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