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

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

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

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

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

הדוגמא הקלאסית של פונקציה רקורסיבית היא פונקציה לחישוב 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. ההגדרה שלי:

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

אם לא – קרא כאן ^[1] מהי רקורסיה".

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

האו"פ ^[2]

איןציקלופדיה ^[3]

יהונתן קלינגר ^[4]

אראל סגל ^[5]