הבנת הרקורסיה

אז מהי רקורסיה?

רקורסיה היא פונקציה שקוראת לעצמה.

ולמה פונקציה צריכה לקרוא לעצמה ולא לפתור את הבעיה? או – איך כל הסיפור הזה לא יכנס ללולאה אינסופית שלא נצא ממנה (הפונקציה תקרא לעצמה ושוב תקרא לעצמה ולא תצא מזה)?

העניין די פשוט – הפונקציה הרקורסיבית "פותרת קצת מהבעיה", ואת שאר הפתרון "משאירה לפונקציה הרקורסיבית".

הדוגמא הקלאסית של פונקציה רקורסיבית היא פונקציה לחישוב n! (אן-עצרת). זה תוצאת המכפלה של 1 כפול 2 כפול 3… כפול n.

פונקציה רקורסיבית תחשב את n עצרת כך:

"אם הארגומנט הוא 1 (כלומר רוצים לחשב את 1 עצרת), התוצאה היא 1,

אחרת – התוצאה היא [עצרת של n-1] כפול n"

כאן אנחנו לא יודעים ולא מחָשבים במפורש מהו (n-1) עצרת, וע"י קריאה לפונקציה לחישוב עצרת, עם הארגומנט n-1, אנחנו מגיעים לתוצאה, שבדרך מופלאה מתקבלת ע"י קריאה לפונקציה לחישוב n-2 עצרת, שהיא בתורה קוראת לפונקציה לחישוב……. שבתורה קוראת לפונקציה לחישוב עצרת של 1. אבל הפונקציה יודעת מהו 1 עצרת – זה 1. אז היא מחזירה 1 כתשובה.

כעת, הפונקציה לחישוב 2 עצרת מקבלת את התשובה ש-1 עצרת הוא 1, הפונקציה מכפילה אותו ב-2 ומחזירה את הערך 2 לפונקציה שקראה לה.

כעת, הפונקציה לחישוב 3 עצרת מקבלת את התשובה ש-2 עצרת הוא 2, הפונקציה מכפילה אותו ב-3 ומחזירה את הערך 6 לפונקציה שקראה לה.

…..

כעת, הפונקציה לחישוב n עצרת מקבלת את התשובה ש-n-1 עצרת הוא (n-1 עצרת), הפונקציה מכפילה אותו ב-n ומחזירה את הערך n עצרת.

עד כאן השעמום. מעכשיו העניין הרציני שילמד אתכם אחת ולתמיד מהי רקורסיה:

1. ההגדרה המילונית.

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

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

2. ההגדרה שלי:

"אם הבנת מהי רקורסיה, חזור אל הדף ממנו הגעת,

אם לא – קרא כאן מהי רקורסיה".

כתבו על זה כבר לפני:

האו"פ

איןציקלופדיה

יהונתן קלינגר

אראל סגל

שלח מאמר זה באימייל שלח מאמר זה באימייל
הדפס מאמר זה הדפס מאמר זה

10 תגובות ל“הבנת הרקורסיה”

  1. מאת לאה צחור:

    אחלה דוגמה לרקורסיה!
    דוגמה נוספת לרקורסיה היא כתיבת תוכנה שקוראת קובץ XML כמו בפורמט RSS

  2. מאת אריאל:

    אם מחפשים בגוגל את המילה recursion הוא שואל Did you mean recursion ולחיצה על הקישור מובילה לאותו דף עצמו, עם אותה שאלה.

    http://www.google.com/search?q=recursion

    הומור של מתכנתים.

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

  3. מאת tsabar:

    לאה – (כמעט) כל כלי תכנותי שלא יודע עד איזה עומק של קינון המידע הוא צריך לחפש משהו מסוים, עושה זאת ברקורסיה. אחת הדוגמאות הנפוצות, כמו שהזכרת, הוא xml parser. דוגמא נפוצה אחרת היא חיפוש קובץ בתוך עץ הספריות (רקורסיה ועצים תמיד הולכים טוב יחד), שבפשטות אומר: "אם מצאת קובץ כנדרש בספריה זו, הדפס את שמו, כעת חפש את הקובץ בכל תתי הספריות של ספריה זו"
    אריאל – בדקתי עכשיו בגוגל, זה עובד גם בעברית. קטע ענק.
    את האמת רציתי לעשות לינק של "חזור אחורה" בתנאי העצירה של הרקורסיה שלי, אבל הוורדפרס לא מאפשר לעשות לינק משולב ג'אוה-סקריפט (כמו שיש בדף שגיאה 404 שלי).

  4. מאת shooshooo:

    ואני לתומי חשבתי שנכשלת באיזה קורס באוניברסיטה הפתוחה ואתה צריך רה-קורסיה
    😉

  5. מאת tsabar:

    שושוו – נפלתי בקורס שבו לומדים את הרקורסיה בגלל שלא עמדתי בתנאי העצירה. 🙂

  6. מאת Ddorda:

    אני חייב לציין שזה הפוסט הראשון שאני באמת לא מבין כלום.

  7. מאת tsabar:

    אם לא הבנת מהי רקורסיה, אולי תבין מקריאת המאמר הזה.

  8. מאת חתול:

    הרקורסיה בסוף הפוסט לא טובה.
    שכחת תנאי עצירה. (-:

  9. מאת tsabar:

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

  10. מאת לאה צחור:

    חתול – הרקורסיה דווקא מצויינת, תנאי העצירה שלה הוא כאשר האדם קרא מספיק פעמים את הפוסט בשביל להגיע לרמת הבנה של רקורסיה….

השארת תגובה