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

בתורת החישוביות; פונקציה פרימיטיבית רקורסיבית היא פונקציה n⁻מקומית (עבור n כלשהו) מקבוצת המספרים הטבעיים לעצמה, הנוצרת מהרכבת פונקציות ופעולה שנקראת "רקורסיה פרימיטיבית" באופן חוזר ונשנה על מספר פונקציות בסיסיות קבועות: הפונקציה הקבועה אפס, הוספת אחד, ובחירת אחד מרכיבי הקלט. מתוך ויקיפדיה

פונקציה רציונלית, פונקציה רציפה, פונקציה רציפה (אנליזה), פונקציה רציפה (טופולוגיה), פונקציה רציפה במידה שווה, פונקציה רקורסיבית פרימיטיבית, פונקציה שומרת סדר, פונקציה שלמה, פונקציה תת⁻לינארית, פונקציה תת⁻ליניארית