הצגת המקור של הדף "הגדרה רקורסיבית"

'''הגדרה רקורסיבית''' או '''הגדרת נסיגה'''{{הערה|{{מילון אקדמיה|138|58458_1|הַגְדָּרַת נְסִיגָה}}}} היא הגדרת מושג באופן שמצריך פניה אל אותה [[הגדרה]], אבל בתנאים שונים. לרוב, כדי לא להיגרר ל[[רקורסיה]] אינסופית, הגדרה רקורסיבית תכלול גם תנאי עצירה.

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

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

ב[[מתמטיקה]] הגדרה רקורסיבית של מושג מתקבלת כהגדרה תקפה, אם אפשר להוכיח שהיא מספקת תשובה חד-משמעית בכל מקרה; ההוכחה היא בדרך כלל ב[[אינדוקציה מתמטית|אינדוקציה]] או ב[[אינדוקציה טרנספיניטית]]. הגדרה כזו נקראת ''הגדרה אינדוקטיבית''. דוגמאות:
# ההגדרה "<math>\ n!</math> שווה ל- <math>\ 1</math> אם <math>\ n=0</math>, ול- <math>\ n \cdot (n-1)!</math> אחרת" היא הגדרה אינדוקטיבית של [[פונקציית העצרת]].
# ב[[מערכת פאנו]] בונים את פעולת ה[[חיבור]] של [[מספר טבעי|מספרים טבעיים]] מתוך פעולת העוקב <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+?".
# ב[[לוגיקה מתמטית]], [[פסוק (לוגיקה מתמטית)|פסוק]] תקני הוא אטום, או פסוק שנבנה באופן חוקי מפסוקים תקניים. זו הגדרה רקורסיבית, שבעזרת אינדוציה על אורך הפסוק אפשר לראות אותה כהגדרה אינדוקטיבית.
# בתאוריה של [[מספר סוריאליסטי|מספרים סוריאליסטיים]], מגדירים "משחק הוא [[זוג סדור]] שכל רכיב שלו הוא קבוצת משחקים". ממבט ראשון זו הגדרה בעייתית, שכן לכאורה ההנחה שבכלל לא קיימים משחקים היא עקבית. אבל אם נשים לב ש[[הקבוצה הריקה]] היא בוודאי קבוצה של משחקים ([[באופן ריק]], ללא קשר להגדרה), יתברר שאפשר לבנות את המשחק שבכל רכיב שלו יש קבוצה ריקה, ועוד רבים אחרים. אפשר להגדיר 'תאריכי לידה' למשחקים (המשחק שבנינו נולד ביום 0, אלו שהרכיבים שלהם משתמשים רק בו נולדו ביום 1, וכן הלאה), וכך לקבל הגדרה אינדוקטיבית תקפה.
# עבור [[מספר טבעי|מספרים טבעיים]] אפשר להגדיר: "מספר חצילי הוא כזה שלפחות מחצית מן המספרים הקטנים ממנו אינם חציליים". לפי ההגדרה הזו 1 הוא חצילי [[באופן ריק]] (אין מספרים קטנים ממנו, וממילא הם ''כולם'' לא חציליים). הקורא מוזמן לבדוק שחציליות היא שם חדש לאי-זוגיות.
# ל[[קבוצה (מתמטיקה)|קבוצות]] כדוגמת [[קבוצת קנטור]] אפשר לתת הגדרה רקורסיבית: "תת-קבוצה C של הקטע [0,1] היא 'קנטורית' אם היא שווה לאיחוד של קבוצה קנטורית המכווצת לשליש השמאלי של הקטע, עם קבוצה קנטורית המכווצת לשליש הימני שלו". יש הרבה קבוצות קנטוריות (ביניהן קבוצת קנטור עצמה, אבל גם הקבוצה הריקה). כעת, את קבוצת קנטור אפשר להגדיר כאיחוד כל הקבוצות הקנטוריות - אלא שזו בנייה מפורשת ולא רקורסיבית. נעיר שהגדרה כדוגמת "תת-קבוצה C של הקטע [0,1] היא 'קנטורית במובן החזק' אם היא שווה לאיחוד של הקבוצה C מכווצת לשליש השמאלי של הקטע, עם הקבוצה C מכווצת לשליש העליון שלו", אינה הגדרה רקורסיבית: כדי לבחון את C צריך אמנם לבדוק את C עצמה, אבל זו לא רקורסיביות, וגם לא מעגליות; הבדיקה האם C קנטורית-במובן-החזק אינה תלויה בקנטוריות-במובן-החזק של קבוצות אחרות, וגם לא בזו של C עצמה.

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:מושגים במתמטיקה]]
[[קטגוריה:רקורסיה]]