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

# ב[[מערכת פיאנו]] מניחים רק את קיומם של המספרים הטבעיים עם פעולת העוקב <math>\ S(x)</math>(העוקב של 5 הוא S(5)=6, וכדומה). את פעולת החיבור מגדירים באופן אינדוקטיבי: אם b=1 אז לפי ההגדרה <math>\ a+b=S(a)</math>; אחרת, b הוא העוקב של איבר מתאים c, ואז מגדירים a+b=S(a)+c. החלפנו כאן את המושג "b+?" במושג 'פשוט' יותר, "c+?".

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

# עבור [[מספר טבעי|מספרים טבעיים]] אפשר להגדיר: "מספר חצילי הוא כזה שלפחות מחצית מן המספרים הקטנים ממנו אינם חציליים". לפי ההגדרה הזו 1 הוא חצילי (אין מספרים קטנים ממנו, וממילא הם ''כולם'' לא חציליים). הקורא מוזמן לבדוק שחציליות היא שם חדש לאי-זוגיות.

# ל[[קבוצה (מתמטיקה)|קבוצות]] כדוגמת [[קבוצת קנטור]] אפשר לתת הגדרה רקורסיבית: "תת-קבוצה C של הקטע [0,1] היא 'קנטורית' אם היא שווה לאיחוד של קבוצה קנטורית המכווצת לשליש השמאלי של הקטע, עם קבוצה קנטורית המכווצת לשליש הימני שלו". יש הרבה קבוצות קנטוריות (ביניהן קבוצת קנטור עצמה, אבל גם הקבוצה הריקה). כעת, את קבוצת קנטור אפשר להגדיר כאיחוד כל הקבוצות הקנטוריות - אלא שזו בניה מפורשת ולא רקורסיבית. נעיר שהגדרה כדוגמת "תת-קבוצה C של הקטע [0,1] היא 'קנטורית במובן החזק' אם היא שווה לאיחוד של הקבוצה C מכווצת לשליש השמאלי של הקטע, עם הקבוצה C מכווצת לשליש העליון שלו", אינה הגדרה רקורסיבית: כדי לבחון את C צריך אמנם לבדוק את C עצמה, אבל זו לא רקורסיביות, וגם לא מעגליות; הבדיקה האם C קנטורית-במובן-החזק אינה תלויה בקנטוריות-במובן-החזק של קבוצות אחרות, וגם לא בזו של C עצמה.