אז מהי רקורסיה?
רקורסיה היא פונקציה שקוראת לעצמה.
ולמה פונקציה צריכה לקרוא לעצמה ולא לפתור את הבעיה? או – איך כל הסיפור הזה לא יכנס ללולאה אינסופית שלא נצא ממנה (הפונקציה תקרא לעצמה ושוב תקרא לעצמה ולא תצא מזה)?
העניין די פשוט – הפונקציה הרקורסיבית "פותרת קצת מהבעיה", ואת שאר הפתרון "משאירה לפונקציה הרקורסיבית".
הדוגמא הקלאסית של פונקציה רקורסיבית היא פונקציה לחישוב 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 תגובות על “הבנת הרקורסיה”
אחלה דוגמה לרקורסיה!
דוגמה נוספת לרקורסיה היא כתיבת תוכנה שקוראת קובץ XML כמו בפורמט RSS
אם מחפשים בגוגל את המילה recursion הוא שואל Did you mean recursion ולחיצה על הקישור מובילה לאותו דף עצמו, עם אותה שאלה.
http://www.google.com/search?q=recursion
הומור של מתכנתים.
ומזכיר את הבדיחה הידועה:
בארה"ב התקיים כנס מתכנתי מחשבים ואחד המתכנתים לא הגיע למרות שנרשם למלון. הלכו ובדקו ומצאו אותו מת במקלחת שכולו מלא קצף. הרימו את בקבוק השמפו ומצאו כתוב בהוראות: "קח מעט סבון, הרטב במים וחפוף את הראש. חזור על הפעולה".
לאה – (כמעט) כל כלי תכנותי שלא יודע עד איזה עומק של קינון המידע הוא צריך לחפש משהו מסוים, עושה זאת ברקורסיה. אחת הדוגמאות הנפוצות, כמו שהזכרת, הוא xml parser. דוגמא נפוצה אחרת היא חיפוש קובץ בתוך עץ הספריות (רקורסיה ועצים תמיד הולכים טוב יחד), שבפשטות אומר: "אם מצאת קובץ כנדרש בספריה זו, הדפס את שמו, כעת חפש את הקובץ בכל תתי הספריות של ספריה זו"
אריאל – בדקתי עכשיו בגוגל, זה עובד גם בעברית. קטע ענק.
את האמת רציתי לעשות לינק של "חזור אחורה" בתנאי העצירה של הרקורסיה שלי, אבל הוורדפרס לא מאפשר לעשות לינק משולב ג'אוה-סקריפט (כמו שיש בדף שגיאה 404 שלי).
ואני לתומי חשבתי שנכשלת באיזה קורס באוניברסיטה הפתוחה ואתה צריך רה-קורסיה
😉
שושוו – נפלתי בקורס שבו לומדים את הרקורסיה בגלל שלא עמדתי בתנאי העצירה. 🙂
אני חייב לציין שזה הפוסט הראשון שאני באמת לא מבין כלום.
אם לא הבנת מהי רקורסיה, אולי תבין מקריאת המאמר הזה.
הרקורסיה בסוף הפוסט לא טובה.
שכחת תנאי עצירה. (-:
ניסיתי להכניס לינק לתנאי העצירה, אבל הוורדפרס מונע ממני לשלב ג'אווה-סקריפט בלינקים.
חתול – הרקורסיה דווקא מצויינת, תנאי העצירה שלה הוא כאשר האדם קרא מספיק פעמים את הפוסט בשביל להגיע לרמת הבנה של רקורסיה….