פונקציה רקורסיבית – הבדלי גרסאות

כדי לבנות את קבוצת הפונקציות הרקורסיביות יש קודם לבנות קבוצה של כללית פחות - הפונקציות הפרימיטיביות.

===פונקציה רקורסיבית פרימיטיבית===

<!-- זו ההגדרה הראשונה שניתנה למושג הפונקציה הרקורסיבית. -->

קבוצת הפונקציות הרקורסיביות הפרימיטיביות מוגדרת להיות הקבוצה המינימלית, <math>\ PR^{(k)}</math>, של פונקציות מ-<math>\N^k</math> למספרים הטבעיים, שמקיימת את התנאים הבאים: