הסבר כללי על רקורסיה

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

5! = 4! * 5

כך, בעצם, אנחנו מפשטים את המשימה.
עכשיו אנחנו רוצים לעשות את זה בפונקציה. נמשיך בשיטה המילולית:
נשאל את הפונקציה "עצרת" כמה זה 5 עצרת. היא תגיד – "לא יודעת, תנו לי את 4 עצרת, אני אכפיל את התוצאה ב 5 ואתן לכם את התשובה". עכשיו קראנו לאותה פונקציה, ושלחנו אליה את 4. היא תשיב: "אני לא יודעת כמה זה 4 עצרת, אבל אם תתנו לי את 3 עצרת, אני אכפיל את זה ב4 ואתן לכם את התשובה"…. וחוזר חלילה….
אם נמשיך ככה בעצם, לא נגיע לכלום. כל פונקציה תשלח לפונקציה חדשה את המספר פחות אחד והתהליך לא יסתיים אף פעם.
כאן אנחנו מגיעים לחלק השני של הרקורסיה: מקרה פשוט שאנחנו בוודעות יודעים להתמודד איתו… במקרה שלנו, אנחנו יודעים כמה זה 1 עצרת (1). מה שיקרה זה שכשנגיע ל 1 הפונקציה שלנו לא תצטרך לקרוא לפונקציה חדשה עוד הפעם, אלא תדע להחזיר אחד. ואז יתחיל תהליך של חזרה. הפונקציה שחיכתה לתוצאה, עצרת 2, תקבל אחד ותכפיל ב 2. היא תחזיר לפונקציה עצרת 3 את 2, והיא תכפיל ב 3 ותחזיר לעצרת 4 וכו'….

האלגוריתם צריך להראות כך:

עצרת(X)
אם X=1 אז החזר 1
אחרת
  החזר(עצרת(X-1)*X)

הבעייה עם רקורסיה, היא שאנו זוללים זכרון (מה אם היינו מחשבים 10000 עצרת?). כלומר כל פעם שקוראים לפונקציה זה משתנה בזכרון…

עוד הסבר