רקורסיה בג'אווה
1. הקדמה
במאמר זה נתמקד בתפיסת ליבה בכל שפת תכנות - רקורסיה.
נסביר את המאפיינים של א פונקציה רקורסיבית ולהראות כיצד להשתמש ברקורסיה לפתרון בעיות שונות בג'אווה.
2. להבין רקורסיה
2.1. ההגדרה
ב- Java תומך מנגנון קריאת הפונקציות האפשרות שיש שיטה להתקשר לעצמה. פונקציונליות זו ידועה בשם רקורסיה.
לדוגמא, נניח שאנחנו רוצים לסכם את המספרים השלמים מ- 0 לערך כלשהו נ:
סכום int ציבורי (int n) {if (n> = 1) {סכום החזר (n - 1) + n; } להחזיר n; }ישנן שתי דרישות עיקריות לפונקציה רקורסיבית:
- תנאי עצירה - הפונקציה מחזירה ערך כאשר מתקיים תנאי מסוים, ללא שיחה רקורסיבית נוספת
- השיחה הרקורסיבית - הפונקציה קוראת לעצמה עם קֶלֶט שהוא צעד קרוב יותר למצב העצירה
כל שיחה רקורסיבית תוסיף מסגרת חדשה לזיכרון הערימה של ה- JVM. כך, אם אנו לא שמים לב עד כמה עמוק השיחה הרקורסיבית שלנו יכולה לצלול, עלול להתרחש חריג מחוץ לזיכרון.
ניתן למנוע את הבעיה הפוטנציאלית הזו באמצעות מינוף אופטימיזציה של זנב-רקורסיה.
2.2. רקורסציית זנב לעומת ראש ראש
אנו מתייחסים לפונקציה רקורסיבית כ- זנב-רקורסיהכאשר השיחה הרקורסיבית היא הדבר האחרון שמבצעת הפונקציה. אחרת, זה ידוע בשם ראש-רקורסיה.
היישום שלנו מעל סְכוּם() פונקציה היא דוגמה לרקורסיה של הראש וניתן לשנות אותה לרקורסיה של הזנב:
public int tailSum (int currentSum, int n) {if (n <= 1) {return currentSum + n; } להחזיר tailSum (currentSum + n, n - 1); }עם רקורסיבית זנב, השיחה הרקורסיבית היא הדבר האחרון שהשיטה עושה, ולכן לא נותר מה לבצע במסגרת הפונקציה הנוכחית.
לפיכך, מבחינה לוגית אין צורך לאחסן את מסגרת המחסנית של הפונקציה הנוכחית.
למרות שהמהדר פחית השתמש בנקודה זו כדי לייעל את הזיכרון, יש לציין כי מהדר Java אינו מותאם לעת עתה לרקורסיביות זנב.
2.3. רקרציה לעומת איטרציה
רקורסיה יכולה לעזור לפשט יישום של כמה בעיות מסובכות על ידי הפיכת הקוד לברור וקריא יותר.
אך כפי שכבר ראינו הגישה הרקורסיבית דורשת לעתים קרובות יותר זיכרון כאשר זיכרון הערימה הנדרש גדל עם כל שיחה רקורסיבית.
כחלופה, אם נוכל לפתור בעיה עם רקורסיה, נוכל גם לפתור אותה באמצעות איטרציה.
למשל, שלנו סְכוּם ניתן ליישם את השיטה באמצעות איטרציה:
public int iterativeSum (int n) {int sum = 0; אם (n <0) {החזר -1; } עבור (int i = 0; i <= n; i ++) {sum + = i; } סכום החזר; }בהשוואה לרקורסיה, הגישה האיטרטיבית עשויה לתת ביצועים טובים יותר. עם זאת, איטרציה תהיה מורכבת יותר וקשה יותר להבנה בהשוואה לרקורציה, למשל: חציית עץ בינארי.
הבחירה הנכונה בין רקורסציית ראש, רקורסיבית זנב וגישה איטרטיבית תלויה בבעיה ובמצב הספציפי.
3. דוגמאות
עכשיו, בואו ננסה לפתור כמה בעיות בצורה רקורסיבית.
3.1. מציאת כוח N-Th של עשרה
נניח שעלינו לחשב את נ-העוצמה של 10. הנה הקלט שלנו נ. לחשוב בצורה רקורסיבית, אנחנו יכולים לחשב (n-1)הכוח ה- 10 של הראשון, והכפל את התוצאה ב- 10.
ואז, כדי לחשב את (n-1)הכוח העשירי של 10 יהיה (n-2)הכוח ה -10 של הכפל את התוצאה ב- 10 וכן הלאה. נמשיך כך עד שנגיע לנקודה בה עלינו לחשב את הכוח (n-n) -th של 10, שהוא 1.
אם היינו רוצים ליישם זאת ב- Java, היינו כותבים:
public int powerOf10 (int n) {if (n == 0) {return 1; } להחזיר powerOf10 (n-1) * 10; }3.2. מציאת אלמנט ה- N של רצף פיבונאצ'י
מתחיל עם 0 ו 1, ה רצף פיבונאצ'י הוא רצף של מספרים כאשר כל מספר מוגדר כסכום של שני המספרים שעוברים עליו: 0 1 1 2 3 5 8 13 21 34 55 …
אז, נתון מספר נהבעיה שלנו היא למצוא את נאלמנט של רצף פיבונאצ'י. כדי ליישם פתרון רקורסיבי, עלינו להבין את עצור מצב וה שיחה רקורסיבית.
למרבה המזל, זה ממש פשוט.
בוא נתקשר f (n) ה נערך ה- של הרצף. אז יהיה לנו f (n) = f (n-1) + f (n-2) (ה שיחה רקורסיבית).
בינתיים, f (0) = 0 ו f (1) = 1 ( עצור מצב).
ואז, ברור לנו באמת להגדיר שיטה רקורסיבית לפתרון הבעיה:
ציבורי ציבורי int (int n) {if (n <= 1) {return n; } השוואה פיבונאטית (n-1) + פיבונאצי (n-2); }3.3. המרה מעשרוני לבינארי
בואו ניקח בחשבון את הבעיה של המרת מספר עשרוני לבינארי. הדרישה היא ליישם שיטה המקבלת ערך שלם חיובי נ ומחזיר בינארי חוּט יִצוּג.
גישה אחת להמרת מספר עשרוני לבינארי היא לחלק את הערך ב -2, לרשום את השאר ולהמשיך לחלק את המנה ב -2.
אנחנו ממשיכים לחלק כך עד שנקבל מנת 0. ואז, על ידי כתיבת כל השאריות בסדר מילואים, אנו מקבלים את המחרוזת הבינארית.
לפיכך, הבעיה שלנו היא לכתוב שיטה שמחזירה את השאריות האלה בסדר מילואים:
מחרוזת ציבורית toBinary (int n) {if (n <= 1) {return String.valueOf (n); } חזור ל- Binary (n / 2) + String.valueOf (n% 2); }3.4. גובה עץ בינארי
גובהו של עץ בינארי מוגדר כמספר הקצוות מהשורש ועד העלה העמוק ביותר. הבעיה שלנו כעת היא לחשב ערך זה עבור עץ בינארי נתון.
גישה אחת פשוטה תהיה למצוא את העלה העמוק ביותר ואז לספור את הקצוות בין השורש לעלה הזה.
אך כשמנסים לחשוב על פיתרון רקורסיבי, אנו יכולים לשנות את ההגדרה לגובה של עץ בינארי כגובה המקסימלי של הענף השמאלי של השורש והענף הימני של השורש, בתוספת 1.
אם לשורש אין ענף שמאלי וענף ימין, גובהו הוא אֶפֶס.
הנה היישום שלנו:
public int calcTreeHeight (שורש BinaryNode) {if (root! = null) {if (root.getLeft ()! = null || root.getRight ()! = null) {החזר 1 + מקסימום (calcTreeHeight (root.left), CalcTreeHeight (root.right)); }} להחזיר 0; }לפיכך אנו רואים זאת ניתן לפתור כמה בעיות באמצעות רקורסיה בצורה ממש פשוטה.
4. מסקנה
במדריך זה הצגנו את מושג הרקורסיה בג'אווה והדגמנו אותו בכמה דוגמאות פשוטות.
יישום מאמר זה ניתן למצוא באתר Github.
