הבנת הרקורסיה
אז מהי רקורסיה?
רקורסיה היא פונקציה שקוראת לעצמה.
ולמה פונקציה צריכה לקרוא לעצמה ולא לפתור את הבעיה? או – איך כל הסיפור הזה לא יכנס ללולאה אינסופית שלא נצא ממנה (הפונקציה תקרא לעצמה ושוב תקרא לעצמה ולא תצא מזה)?
העניין די פשוט – הפונקציה הרקורסיבית "פותרת קצת מהבעיה", ואת שאר הפתרון "משאירה לפונקציה הרקורסיבית".
הדוגמא הקלאסית של פונקציה רקורסיבית היא פונקציה לחישוב 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. ההגדרה שלי:
"אם הבנת מהי רקורסיה, חזור אל הדף ממנו הגעת,
אם לא – קרא כאן מהי רקורסיה".
כתבו על זה כבר לפני:
הדפס מאמר זה
31 ביולי, 2009 בשעה 0:51
משתמש בדפדפן Mozilla Firefox 3.5.1 ובמערכת הפעלה Linux
אחלה דוגמה לרקורסיה!
דוגמה נוספת לרקורסיה היא כתיבת תוכנה שקוראת קובץ XML כמו בפורמט RSS
31 ביולי, 2009 בשעה 9:37
משתמש בדפדפן Mozilla Firefox 3.5.1 ובמערכת הפעלה Linux
אם מחפשים בגוגל את המילה recursion הוא שואל Did you mean recursion ולחיצה על הקישור מובילה לאותו דף עצמו, עם אותה שאלה.
http://www.google.com/search?q=recursion
הומור של מתכנתים.
ומזכיר את הבדיחה הידועה:
בארה"ב התקיים כנס מתכנתי מחשבים ואחד המתכנתים לא הגיע למרות שנרשם למלון. הלכו ובדקו ומצאו אותו מת במקלחת שכולו מלא קצף. הרימו את בקבוק השמפו ומצאו כתוב בהוראות: "קח מעט סבון, הרטב במים וחפוף את הראש. חזור על הפעולה".
31 ביולי, 2009 בשעה 10:53
משתמש בדפדפן Epiphany 2.22 ובמערכת הפעלה Linux
לאה – (כמעט) כל כלי תכנותי שלא יודע עד איזה עומק של קינון המידע הוא צריך לחפש משהו מסוים, עושה זאת ברקורסיה. אחת הדוגמאות הנפוצות, כמו שהזכרת, הוא xml parser. דוגמא נפוצה אחרת היא חיפוש קובץ בתוך עץ הספריות (רקורסיה ועצים תמיד הולכים טוב יחד), שבפשטות אומר: "אם מצאת קובץ כנדרש בספריה זו, הדפס את שמו, כעת חפש את הקובץ בכל תתי הספריות של ספריה זו"
אריאל – בדקתי עכשיו בגוגל, זה עובד גם בעברית. קטע ענק.
את האמת רציתי לעשות לינק של "חזור אחורה" בתנאי העצירה של הרקורסיה שלי, אבל הוורדפרס לא מאפשר לעשות לינק משולב ג'אוה-סקריפט (כמו שיש בדף שגיאה 404 שלי).
31 ביולי, 2009 בשעה 19:59
משתמש בדפדפן Epiphany 2.22 ובמערכת הפעלה Linux
ואני לתומי חשבתי שנכשלת באיזה קורס באוניברסיטה הפתוחה ואתה צריך רה-קורסיה
😉
31 ביולי, 2009 בשעה 20:33
משתמש בדפדפן Epiphany 2.22 ובמערכת הפעלה Linux
שושוו – נפלתי בקורס שבו לומדים את הרקורסיה בגלל שלא עמדתי בתנאי העצירה. 🙂
1 באוגוסט, 2009 בשעה 13:39
משתמש בדפדפן Mozilla Firefox 3.5.1 ובמערכת הפעלה Linux
אני חייב לציין שזה הפוסט הראשון שאני באמת לא מבין כלום.
1 באוגוסט, 2009 בשעה 19:19
משתמש בדפדפן Epiphany 2.22 ובמערכת הפעלה Linux
אם לא הבנת מהי רקורסיה, אולי תבין מקריאת המאמר הזה.
4 באוגוסט, 2009 בשעה 23:48
משתמש בדפדפן Mozilla Firefox 3.5.2 ובמערכת הפעלה Windows XP
הרקורסיה בסוף הפוסט לא טובה.
שכחת תנאי עצירה. (-:
4 באוגוסט, 2009 בשעה 23:52
משתמש בדפדפן Epiphany 2.22 ובמערכת הפעלה Linux
ניסיתי להכניס לינק לתנאי העצירה, אבל הוורדפרס מונע ממני לשלב ג'אווה-סקריפט בלינקים.
5 באוגוסט, 2009 בשעה 0:34
משתמש בדפדפן Mozilla Firefox 3.5.2 ובמערכת הפעלה Linux
חתול – הרקורסיה דווקא מצויינת, תנאי העצירה שלה הוא כאשר האדם קרא מספיק פעמים את הפוסט בשביל להגיע לרמת הבנה של רקורסיה….