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