- למה יהודים עונים על שאלה בשאלה נוספת?
- למה לא?
רקורסיה (-נסיגה) זו דרך שונה לפתור בעיה. במקום לפתור את הבעיה מיד, השיטה היא להעמיק עוד את הבעיה עד נקודה מסויימת ואז הפתרון מתקבל תוך כדי נסיגה לאחור.
דיברתי סינית?! קחו דוגמא:
במתמטיקה משתמשים בנוסחה רקורסיבית כדרך לתאר סידרת מספרים. למשל הסידרה הזו
1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | ...
לסידרת המספרים הזו קוראים "סידרת פיבונאצ'י", והיא מוגדרת באופן הרקורסיבי הבא: כל איבר בסידרה הוא סכום שני האיברים שלפניו.
במתמטיקה זה מתואר כך:
A(n) = A(n-1) + A(n-2)
אם למשל ניקח את האיבר השביעי בסידרה, מספר 13, נראה שבאמת הערך שלו הוא חיבור של שני האיברים הקודמים 5+8. נהדר!
עכשיו מה קורה כשאנחנו מנסים למצוא איבר מסויים, נניח איבר מספר 25. אז לפי ההגדרה הערך של איבר מספר 25 הוא חיבור בין הערך של איבר מספר 24 והערך של איבר מספר 23. הנה פתרנו את החידה בקלי קלות. מדהים! נכון?
אההה.... אופס.
אבל מהם הערכים של האיברים 24 ו23??
במקום לפתור את השאלה, הוספנו עוד 2 שאלות עכשיו! רק עוד בלאגן. במקום לתת פתרון, העמקנו את הבעיה. בדיוק כמו היהודי המעצבן הזה שבתחילת הפוסט.
אז הפתרון הוא להמשיך בדרך זו. גם האיברים 24 ו23 ננסה למצוא אותם באמצעות הנוסחה. איבר 24 הוא סכום איברים 23 ו22, ואיבר 23 הוא סכום 22 ו21... אוף. שוב בלאגן. כמה שאלות פתוחות יש פה, אמאל'ה!!!
אין מה לעשות, צריך להמשיך.
בואו נדמיין שהמשכתם עד שהגעתם לאיבר מספר 3 שהוא סכום של איבר מספר 1 ואיבר מספר 2. כאן בעצם אנו נתקלים בהגדרה נוספת, שבלעדיה הנוסחה לא תהיה פתירה. ההגדרה שבאה לעזרתנו היא: ידוע שאיבר מספר 1 הוא 1, ואיבר מספר 2 הוא גם 1. אז הנה מצאנו את איבר מספר 3 שהוא חיבור של איבר מספר 2 (שאנו יודעים שהוא 1) ואיבר מספר 1 (שהוא גם 1): והתשובה היא 2!! איזה כיף!
אפשר לחגוג?
עוד לא. כי השאלה שלנו היתה בכלל מהו איבר מספר 25. איזה כאב ראש. אמא.
אבל היי, יש לנו עכשיו קצה חוט וצריך פשוט להמשיך איתו. עכשיו התנועה היא נסיגה לאחור. מהודאות שיש לנו לגבי איבר 3 ואיבר מספר 2 אנו יכולים לפתור את הבעיה הקודמת שעלתה לנו בתהליך - מהו איבר מספר 4 -- אם כן התשובה היא: 3 (2+1)! מדהים. ממשיכים לפתור את השאלות שנפתחו בתהליך, מהו איבר מספר 5 - 5 (3+2) יופי יופי!!!
בעצם אנו פותרים את השאלות עכשיו בסדר הפוך מהסדר שבו הן נפתחו מלכתחילה. ורק בסוף אנו מקבלים תשובה לשאלה הראשונה, מהו איבר מספר 25. ואגב התשובה היא 75025.
הכל מתחיל מאמונה
אז הבנו מהי רקורסיה, ולמה היא נקראת נסיגה. רקורסיה דורשת מאיתנו אמונה בפתרון, גם כשהכיוון הוא הפוך מהפתרון. ראינו שחוץ מההגדרה הרקורסיבית, באה ההגדרה של מהי הודאות שדרכה מתחיל הפתרון, וזו נקראת תנאי עצירה, השלב שבו אנו מפסיקים לפתוח עוד ועוד בעיות, ומגלים פתרון שמאפשר לנו לחזור אחורה ולפתור את הכל.
במחשבים יש שימוש רחב ומגוון בשיטה רקורסיבית מכיון שמאוד קל להגדיר נוסחה כזו עבור מחשב, ובשונה מבנאדם שצריך להחזיק בראש את כל המהלך המפותל הזה, מחשב עושה את זה די בקלות.
המגדל של האנוי
בעיה מעניינת שאפשר להציע לה פתרון בדרך של רקורסיה, נקראת מגדלי האנוי
קרדיט: Evanherk CC BY-SA 3.0
עליכם להעביר את כל הטבעות מהמגדל השמאלי למגדל הימני תוך שמירה על 2 כללים:
- אפשר להעביר טבעת אחת בכל פעם.
- אסור שטבעת רחבה תהיה על גבי טבעת צרה ממנה.
זו בעיה שעשויה להיראות סבוכה לאדם רגיל, אבל עבור מחשב אם נתאר לו את הפתרון בצורה רקורסיבית זה יהיה קלי קלות.
והפתרון הרקורסיבי הינו:
**כדי להעביר N טבעות ממגדל אחד (מקור) למגדל אחר (יעד) יש:
א. להעביר כמות של N-1 טבעות ממגדל המקור למגדל הנותר
ב. להעביר את הטבעת שנותרה במגדל המקור אל מגדל היעד
ג. להעביר את הטבעות מהמגדר הנותר למגדל היעד.
מכיון שיש לנו 3 מגדלים, אנו יכולים להיעזר במגדל הנותר לפתרון החידה.
הפתרון המוצג נראה פשוט למדי, אלא שביצוע שורה א' ושורה ג' הוא בלתי אפשרי לפי כלל מספר 1. אם למשל במקרה שלנו יש 8 טבעות, שורה א' דורשת ממנו להעביר 7 טבעות בבת אחת, וזה אסור! למעשה נפתחה לנו כאן תת בעיה שהדרך לפתור אותה היא על ידי שימוש באותה דרך פתרון עצמה:
על מנת להעביר 7 טבעות ממגדל המקור למגדל הנותר, עלינו להעביר 6 טבעות תחילה ממגדל המקור למגדל היעד (שהוא הנותר של הנותר) ואז להעביר את הטבעת השביעית למגדל הנותר, ואז להעביר את כל 6 הטבעות למגדל הנותר.
ושוב - איך מעבירים 6 טבעות? אז שוב נשתמש בתיאור הפתרון הרקורסיבי... נעביר 5 טבעות למגדל הנותר ....
אחרי שנסיים את כל החישובים הללו, נגיע לשלב שאנו רוצים להעביר 2 טבעות בלבד, ובשביל לעשות את זה נצטרך להעביר טבעת אחת למקום מסויים וטבעת אחרת למקום אחר, וזה כבר אפשרי. שיוףףףף.. הגענו לתנאי עצירה! מכאן והלאה מבצעים את ההוראות. העברנו 2 טבעות, יופי, מעבירים את הטבעת התחתונה, עכשיו שוב צריך להעביר 2 טבעות, את זה מבצעים דרך הנוסחה, בום. העברנו 2 טבעות. בסוף התהליך יצא שהעברנו 3 טבעות - יופי! עכשיו מעבירים את הטבעת התחתונה, עכשיו שוב צריך להעביר 3 טבעות, אז צריך בשביל זה להעביר 2 טבעות, טבעת תחתונה, ושוב 2 טבעות. וכו'...
הבנתם?
למחשב זה לא בעיה.
מה זה רקורסיה ומה זה לא?
בגלל שההסבר האמיתי של רקורסיה הוא קצת מורכב. יש כאלה שמעדיפים לעשות לעצמם קיצורי דרך ולהגדיר רקורסיה כמצב שפונקציה מסויימת משתמשת בעצמה. למשל פה: כדי להעביר טבעות צריך להעביר טבעות. אנו קוראים ל'פונקציה' העברת טבעות בתוך עצמה כדי לפתור את עצמה.
הגדרה כזו היא לא מדוייקת כי לא כל קריאה עצמית היא רקורסיה. רקורסיה תתקיים רק בהינתן תנאי עצירה שיאפשר את הנסיגה לאחור. זיכרו - רקורסיה פירושה נסיגה. לא מעגליות.
אז זהו. רקורסיה זו דרך מדהימה להסתכל על העולם, במבט של אמונה, להבין שתהליכים מסובכים יכולים להיות מוגדרים בצורה מאוד פשוטה. גם אם הפתרון בפועל הוא סבוך וארוך, ההגדרה נשארת פשוטה.