פונקציה רקורסיבית
הגדרה: תהי פונקציה:
המינימיזציה של g היא:
דוגמא:
i P P P N N P ) ( ... , 3 ) 2 ( , 2 ) 1 ( , 1 ) 0 ( , : = = = =
i מספר
נגדיר פונקציה על מספרים ראשוניים (prime):
P מוגדרת ע"י הרקורסיה:
פונקציות רקורסיביות
תקרא רקורסיבית אם אפשר ליצור אותה מהפונקציות הבסיסיות בשימוש של הרכבה רקורסיה ומינימיזציה.