הגדרה רקורסיבית

הגדרה רקורסיבית או הגדרת נסיגה^[1] היא הגדרת מושג באופן שמצריך פניה אל אותה הגדרה, אבל בתנאים שונים. לרוב, כדי לא להיגרר לרקורסיה אינסופית, הגדרה רקורסיבית תכלול גם תנאי עצירה.

למשל, ההגדרה "יהודי הוא מי שאמו יהודיה" היא רקורסיבית, משום שכדי לקבוע האם אדם הוא יהודי, עלינו לדעת אם אימו יהודייה. ההגדרה מחליפה את השאלה 'האם אדם הוא יהודי?' בשאלה 'האם אימו יהודיה?', בשונה מהגדרה מעגלית המחליפה את השאלה באותה שאלה עצמה.

יש להבחין בין רקורסיביות של הגדרה, לבין רקורסיה שהיא בדרך-כלל פעולה המבוצעת על ידי הפניה עצמית.

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

ההגדרה " $\ n!$ שווה ל- $\ 1$ אם $\ n=0$ , ול- $\ n\cdot (n-1)!$ אחרת" היא הגדרה אינדוקטיבית של פונקציית העצרת.
במערכת פאנו בונים את פעולת החיבור של מספרים טבעיים מתוך פעולת העוקב $\ S(x)$ (העוקב של 5 הוא S(5)=6, וכדומה). את פעולת החיבור מגדירים באופן אינדוקטיבי: אם b=1 אז לפי ההגדרה $\ a+b=S(a)$ ; אחרת, b הוא העוקב של איבר מתאים c, ואז מגדירים a+b=S(a)+c. החלפנו כאן את המושג "b+?" במושג 'פשוט' יותר, "c+?".
בלוגיקה מתמטית, פסוק תקני הוא אטום, או פסוק שנבנה באופן חוקי מפסוקים תקניים. זו הגדרה רקורסיבית, שבעזרת אינדוציה על אורך הפסוק אפשר לראות אותה כהגדרה אינדוקטיבית.
בתאוריה של מספרים סוריאליסטיים, מגדירים "משחק הוא זוג סדור שכל רכיב שלו הוא קבוצת משחקים". ממבט ראשון זו הגדרה בעייתית, שכן לכאורה ההנחה שבכלל לא קיימים משחקים היא עקבית. אבל אם נשים לב שהקבוצה הריקה היא בוודאי קבוצה של משחקים (באופן ריק, ללא קשר להגדרה), יתברר שאפשר לבנות את המשחק שבכל רכיב שלו יש קבוצה ריקה, ועוד רבים אחרים. אפשר להגדיר 'תאריכי לידה' למשחקים (המשחק שבנינו נולד ביום 0, אלו שהרכיבים שלהם משתמשים רק בו נולדו ביום 1, וכן הלאה), וכך לקבל הגדרה אינדוקטיבית תקפה.
עבור מספרים טבעיים אפשר להגדיר: "מספר חצילי הוא כזה שלפחות מחצית מן המספרים הקטנים ממנו אינם חציליים". לפי ההגדרה הזו 1 הוא חצילי באופן ריק (אין מספרים קטנים ממנו, וממילא הם כולם לא חציליים). הקורא מוזמן לבדוק שחציליות היא שם חדש לאי-זוגיות.
לקבוצות כדוגמת קבוצת קנטור אפשר לתת הגדרה רקורסיבית: "תת-קבוצה C של הקטע [0,1] היא 'קנטורית' אם היא שווה לאיחוד של קבוצה קנטורית המכווצת לשליש השמאלי של הקטע, עם קבוצה קנטורית המכווצת לשליש הימני שלו". יש הרבה קבוצות קנטוריות (ביניהן קבוצת קנטור עצמה, אבל גם הקבוצה הריקה). כעת, את קבוצת קנטור אפשר להגדיר כאיחוד כל הקבוצות הקנטוריות - אלא שזו בנייה מפורשת ולא רקורסיבית. נעיר שהגדרה כדוגמת "תת-קבוצה C של הקטע [0,1] היא 'קנטורית במובן החזק' אם היא שווה לאיחוד של הקבוצה C מכווצת לשליש השמאלי של הקטע, עם הקבוצה C מכווצת לשליש העליון שלו", אינה הגדרה רקורסיבית: כדי לבחון את C צריך אמנם לבדוק את C עצמה, אבל זו לא רקורסיביות, וגם לא מעגליות; הבדיקה האם C קנטורית-במובן-החזק אינה תלויה בקנטוריות-במובן-החזק של קבוצות אחרות, וגם לא בזו של C עצמה.