פונקציה פרימיטיבית רקורסיבית היא פונקציה שמקבלת מספרים טבעיים ומחזירה מספר טבעי. זו פעמון בניית פונקציות: מתחילים ממספר פונקציות בסיסיות וקובעים חוק התחלה וחוק חזרה. הפונקציות הבסיסיות הן אפס (הפונקציה הקבועה שמחזירה 0), העוקב (הוספת אחד), ובחירת רכיב (פונקציה שמחזירה אחד מהרכיבים של הקלט).
מחלקה של פונקציות נקראת סגורה תחת רקורסיה פרימיטיבית אם אפשר לבנות ממנה פונקציות חדשות בעזרת חיבור של פונקציות וקביעת רקורסיה מסוג זה. מחלקת הפונקציות הפרימיטיביות הרקורסיביות היא הקבוצה המינימלית שמכילה את הפונקציות ההתחלתיות וסגורה להרכבה ולרקורסיה פרימיטיבית. כל פונקציה בקבוצה הזאת נקראת פונקציה פרימיטיבית רקורסיבית.
רוב הפונקציות האריתמטיות הבסיסיות הן פרימיטיביות רקורסיביות, לעיתים לאחר התאמות כדי לשמור על תמונה בתוך המספרים הטבעיים. לדוגמה:
חיבור של שני מספרים הוא פונקציה פרימיטיבית רקורסיבית. אפשר להגדיר את החיבור בעזרת פונקציית הזהות (הטלה של הרכיב הראשון) וכוח הרקורסיה:
f(0,x)=x
f(n+1,x)=s(f(n,x)) כלומר מוסיפים אחד כל פעם.
כפל, חזקות (חזקת מספר) ולעצרת (פקטוריאל) גם הן פרימיטיביות רקורסיביות. ההוכחה דומה לזו של החיבור, באמצעות בנייה רקורסיבית מהפונקציות הבסיסיות.
חיסור רגיל עשוי להוביל לתוצאה שלילית, ולכן מתקנים אותו כדי שיחזיר תמיד מספר טבעי. בדרך מקובלת מגדירים חיסור שמחזיר 0 אם התוצאה אמורה להיות שלילית. כדי לבנות חיסור כזה מגדירים קודם את פונקציית "הקודם" p שמחזירה לכל n>0 את n-1, ול-0 מחזירה 0. באמצעות p ניתן להוריד יחידה בכל שלב ולבנות חיסור באמצעות רקורסיה.
גם לחילוק יש תיקון כדי שהתמונה תהיה מספר טבעי. מגדירים חילוק שלמים (עיגול כלפי מטה) באמצעות חזרה על החיסור המתוקן. כלומר מחלקים את המספרים על ידי החזרה עד שאין עוד מה לחלק.
פונקציות פרימיטיביות רקורסיביות משמשות כבסיס למחלקות חישוביות רבות. קל להראות שפונקציות אריתמטיות הן רקורסיביות על ידי הצגה פרימיטיבית שלהן. עם זאת, לא כל פונקציה רקורסיבית היא פרימיטיבית רקורסיבית.
קיים קשר הדוק בין פונקציות פרימיטיביות רקורסיביות לפונקציות רקורסיביות כלליות. אם פונקציה רקורסיבית תמיד עוצרת בתוך גבול שקובע פונקציה פרימיטיבית רקורסיבית, אז היא פרימיטיבית גם כן. אבל יש פונקציות רקורסיביות שאינן פרימיטיביות, כמו פונקציית אקרמן, שהן חזקות יותר מבחינת גדילה והתנהגות.
פונקציה היא חוק שמקבל מספרים ומחזיר מספר. פונקציה פרימיטיבית רקורסיבית בונים משתי פעולות פשוטות וחוקים שחוזרים על עצמם.
הפונקציות הפשוטות הן: אפס (מחזירה 0), העוקב (מוסיף 1), ובחירת רכיב (מחזירה אחד מהמספרים שהכנסת).
חיבור של מספרים נוצר כך: אם מוסיפים 1 שוב ושוב מגיעים לתוצאה. לכן חיבור הוא פונקציה כזו.
כפל, חזקות, ועצרת (פקטוריאל) נבנים גם הם עם אותו רעיון של חזרה.
חיסור יכול לתת תוצאה שלילית, וזה לא מספר טבעי. לכן מתאימים אותו כך שאם התוצאה אמורה להיות שלילית, מחזירים 0. לנוסח הזה משתמשים בפונקציה שנקראת "הקודם". היא מחזירה את המספר הקודם, ול־0 היא מחזירה 0.
לחילוק גם עושים תיקון כדי שהתוצאה תהיה מספר טבעי. מבצעים חיסור חוזר עד שאי אפשר עוד לחלק, וכך מוצאים כמה פעמים אפשר לחלק.
הרעיון עוזר לבנות הרבה פונקציות חזקות ושימושיות במתמטיקה ובמחשבים. אבל יש פונקציות שחושבות אחרת, שאינן אפשריות לבנייה בדרך הזו, כמו פונקציית אקרמן.
תגובות גולשים