לדלג לתוכן

הבדלים בין גרסאות בדף "פונקציה פרימיטיבית רקורסיבית"

בוט - מחליף 'דוגמא' ב'דוגמה', 'פונקצית' ב'פונקציית'
(יישור קו עם פונקציה רקורסיבית)
(בוט - מחליף 'דוגמא' ב'דוגמה', 'פונקצית' ב'פונקציית')
:<math>\
s(x) = x+1
</math> -פונקציתפונקציית העוקב.<br />
:<math>\
n(x) = 0
</math> -פונקציתפונקציית האפס.<br />
:<math>\
s_n^i(x_1, ... , x_{i-1}, x_i, x_{i+1}, ... , x_n) = x_i
</math> -פונקציתפונקציית ההטלה לרכיב ה-i.<br />
ובנוסף סגורה לפעולות של [[הרכבה של פונקציות]], ורקורסיה פרימיטיבית. כאשר הרקורסיה הפרימיטיבית היא בעצם הגדרת פונקציה חדשה באמצעות הגדרתה על נקודת התחלה באמצעות פונקציה רקורסיבית פרימיטיבית, ותיאור ההתקדמות שלה באמצעות פונקציה רקורסיבית פרימיטיבית אחרת:<br>
אם <math>\ f: \N^k \rightarrow \N</math> ו-<math>\ g: \N^{k+2} \rightarrow \N</math> פונקציות פרימיטיביות, אז הפונקציה <math>\ h: \N^{k+1} \rightarrow \N</math> שמוגדרת ב[[רקורסיה]]:
קיימים קשרים מעניינים ביותר בין פונקציות פרימיטיביות רקורסיביות, ו[[פונקציה רקורסיבית|פונקציות רקורסיביות]]. בפרט, ניתן להראת שאם פונקציה היא רקורסיבית, ועוצרת תמיד לאחר מספר ידוע של צעדים (שחסום על ידי פונקציה פרימיטיבית רקורסיבית), אזי היא גם פרימיטיבית רקורסיבית.
 
ולמרות שנובע מכך שפונקציות רקורסיביות רבות ביותר הן פרימיטיביות רקורסיביות, קיימות פונקציות רקורסיביות שאינן פרימיטיביות רקורסיביות, כמו לדוגמאלדוגמה [[פונקציתפונקציית אקרמן]].
 
[[קטגוריה:סיבוכיות]]
68,018

עריכות