אכן בעיה
רקורסיה היא נושא מאוד לא פשוט, שהרבה מאוד אנשים מתקשים בו בהתחלה. מאוד לא טבעי לחשוב על רקורסיה ולכן הבלבול, אבל אני יכול לנחם אותך בכך שככל שתעבדי על זה יותר ותראי יותר דוגמאות, כך ישתפר מצבך ותצליחי להבין יותר טוב, עד שבסוף תגיעי למצב שרקורסיה תהיה מאוד פשוטה עבורך. בכל מקרה, לשאלתך - כן, אפשר לעבוד עם eclipse או עם כל סביבה אחרת כדי להבין "מה קורה". ניקח את הדוגמה הקלאסית והפשוטה ביותר - עצרת. עצרת של מספר n מוגדרת כך:
n!=1*2*...*(n-1)*n
אבל אפשר להגדיר את זה בצורה שונה:
n!=
*(n-1)!
כלומר, התוצאה של !n היא מכפלה של n בתוצאה של !(n-1). נכון? נכון. זה לא קשור לתכנות, זו פשוט מתימטיקה. עכשיו, אם הייתי נותן לך פונקציה שיודעת לחשב את !(n-1), היית יודעת לחשב את !n בקלות, נכון? ואיך היית מחשבת את !(n-1)? אה... בשביל זה הייתי נותן לך פונקציה נוספת שיודעת לחשב את !(n-2), ואז היית מכפילה את התוצאה של הפונקציה הזו ב-(n-1) והיית מקבלת בסה"כ את !(n-1). אם לא עקבת אחריי ואת מבולבלת, תקראי שוב עד שתביני. ככה התהליך ממשיך ל-n-3 ואז ל-n-4 וכן הלאה. מתי תעצרי? שימי לב שבסוף את יורדת עד ל-(n-(n-1, שזה בעצם 1. מה התוצאה של !1? את זה את יודעת - זה 1. ולכן במקרה הספציפי הזה, את תחזירי 1. ננסח את זה ככה: בואי נכתוב פונקציה שמבקשים ממנה את התוצאה של !n, והיא מחזירה את !(n*(n-1. זה יעבוד, נכון? יפה. רק מה שחסר פה זה את
תנאי העצירה, שהוא - נכון - n==1. במקרה הזה נחזיר פשוט - 1. עכשיו תראי את הקוד:
public class Recursion { static int atzeret(int n) { if (n==1) { return 1; } else { return (n*atzeret(n-1)); } } public static void main(String[] args) { System.out.println(atzeret(10)); } }
הגדרתי פה פונקציה שנקראת atzeret, והיא עושה בדיוק את מה שהבטחתי. אם n הוא 1, היא תחזיר פשוט 1. אם לא, היא תחזיר את n כפול התוצאה של atzeret על n-1. בנוסף לתוכנית הזו, הכנתי תוכנית זהה עם קצת הדפסות DEBUG, והפלט שלה מאוד מעניין, שימי לב:
Atzeret called with 10 .Atzeret called with 9 ..Atzeret called with 8 ...Atzeret called with 7 ....Atzeret called with 6 .....Atzeret called with 5 ......Atzeret called with 4 .......Atzeret called with 3 ........Atzeret called with 2 .........Atzeret called with 1 ........Atzeret returned with the result of 1 .......Atzeret returned with the result of 2 ......Atzeret returned with the result of 6 .....Atzeret returned with the result of 24 ....Atzeret returned with the result of 120 ...Atzeret returned with the result of 720 ..Atzeret returned with the result of 5040 .Atzeret returned with the result of 40320 Atzeret returned with the result of 362880 The result of atzeret(10) is 3628800
שימי לב מה קורה. קראנו ל-(atzeret(10. היא יורדת פנימה ל-9, שיורדת פנימה ל-8, שיורדת פנימה ל-7, וככה עד הירידה ל-1. הקריאה ל-1 חוזרת מייד בתוצאה 1. כעת מכפילים את 1 במספר הנוכחי - אם תעקבי באופן אנכי אחרי הנקודות, תראי שהמספר הנוכחי הוא 2. התוצאה שתחזור היא 2*1. היא תחזור כמובן ל-(atzeret(3 שתוסיף את ההכפלה ב-3, לתוצאה כוללת של 6, שתחזור ל-(atzeret(4, שתכפיל ב-4 לתוצאה של 24, וכו'. ככה אנחנו חוזרים בקריאות אחורה עוד ועוד, עד שמגיעים ל-!10. את יכולה גם לעקוב אחרי המתרחש עם DEBUGGER, ואם יש לך שאלות נוספות, תשאלי. בין הדוגמה הזו של עצרת לבין חשיבה בצורה רקורסיבית יש עוד זמן רב, אבל תחשבי על זה גם ככה - כשאני הופך חולצה, אני מכניס את היד עד לסוף השרוול, תופס אותו בקצה ומושך אותו
בחזרה. תנסי לחשוב בצורה כזו. לפעמים את צריכה לרוץ ברשימה מקושרת, נגיד, עד הסוף ואז לחזור את כל הדרך אחורה, כשבדרך את נעזרת בעובדה שאת
חוזרת. הנה התוכנית עם הודעות ה-DEBUG, את יכולה להריץ אותה ולבדוק:
public class Recursion { static int level; static int atzeret(int n) { for (int i=0; i < level; i++) { System.out.print("."); } System.out.println("Atzeret called with " + n); if (n==1) { return 1; } else { level = level + 1; // Because we're going deeper now int result = atzeret(n-1); level = level - 1; // Because we have returned up for (int i=0; i < level; i++) { System.out.print("."); } System.out.println("Atzeret returned with the result of " + result); return (n*result); } } public static void main(String[] args) { level = 0; int result = atzeret(10); System.out.println("The result of atzeret(10) is " + result); } }
