דלגו לתוכן הראשי
גאמא קוד

High Level Programming

By Value Recursion Exception

העברת פרמטרים by value, רקורסיה וטיפול בחריגות ב-Java וב-C#, כולל קביעת פלט של קוד.

בחרו את הרמה שמתאימה לכם ואת הסט שתרצו לתרגל

חומר לימוד

By Value Recursion Exception: העברת פרמטרים, רקורסיה וחריגות

הפרק מחבר שלושה כלים שמופיעים כמעט בכל תוכנית בשפה עילית: הדרך שבה ערכים עוברים מהקוד הקורא אל מתודה, מתודה שמפעילה את עצמה, והמנגנון שמטפל בתקלות בזמן ריצה. הדוגמאות כתובות ב-Java וב-C#.

  • By Value: מה בדיוק מגיע למתודה כשמעבירים לה משתנה, למה שינוי בתוכה נראה לפעמים אצל הקורא ולפעמים נעלם, ומה משנות ב-C# המילים ref, out ו-in.
  • Recursion: מקרה בסיס וצעד שמתקרב אליו, מה נבנה על מחסנית הקריאות בכל הפעלה, איך עוקבים אחרי קוד רקורסיבי עד הפלט שלו, ומתי עדיף לעבור ללולאה.
  • Exception: זריקה ותפיסה, ההבדל בין checked ל-unchecked, הסדר של בלוקי catch, ומה מובטח על ידי finally ו-try-with-resources.

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

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

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

By Value: מה מקבלת מתודה כשמעבירים לה משתנה

העברה By Value: לפרמטר יש תא זיכרון משלו

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

בהעברה By Value (העברה לפי ערך) הקשר נגמר ברגע הקריאה. הפרמטר נוצר כמשתנה חדש, הערך של הארגומנט נכתב לתוכו, ומכאן והלאה יש בזיכרון שני תאים נפרדים: אחד של הקורא ואחד של המתודה.

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

הפרמטר הוא משתנה מקומי לכל דבר. הוא חי במסגרת (frame) שנפתחת עבור הקריאה הזו על מחסנית הקריאות (Stack), ונעלם יחד איתה כשהמתודה חוזרת.

Java
public class Main {
    static void addBonus(int score) {
        score += 50;                                     // changes the local copy
        System.out.println("in method:  " + score);
    }

    public static void main(String[] args) {
        int points = 120;
        addBonus(points);
        System.out.println("after call: " + points);
    }
}
פלט
in method:  170
after call: 120

ההוספה של 50 אכן קרתה, אבל על score ולא על points. אחרי החזרה נשאר רק המשתנה של הקורא, עם הערך שהיה בו מלכתחילה.

גם שם זהה לא משנה את התמונה. אם הפרמטר נקרא בדיוק כמו המשתנה של הקורא, עדיין יש שני משתנים, כל אחד בתחום שלו ובתא שלו. השם הוא תווית בתוך המתודה, לא חוט שמחבר אותה למשתנה שבחוץ.

שפהברירת המחדלאיך מקבלים את המשתנה של הקורא עצמו
Javaתמיד By Value, בלי שום חריגאין דרך, השפה לא מציעה מנגנון כזה
C#By Valueרק כשהפרמטר מסומן ref, out או in

בטיפוס פרימיטיבי כמו int, double או boolean, מה שעובר הוא הערך עצמו: המספר, או true או false. אין כאן כתובת ואין מצביע שמוביל חזרה אל המשתנה המקורי.

תוצאה ידועה של הכלל: ב-Java אי אפשר לכתוב מתודה שמחליפה בין שני משתני int של הקורא. המתודה מחליפה בין שני העותקים שלה, והקורא לא מרגיש בכך. הדרך המקובלת להוציא ערך חדש החוצה היא להחזיר אותו ב-return ולתת לקורא לבצע את ההשמה בעצמו:

Java
public class Main {
    static void exchange(int left, int right) {
        int tmp = left;
        left = right;
        right = tmp;          // only the two copies trade places
    }

    static int withBonus(int score) {
        return score + 50;    // hand the new value back
    }

    public static void main(String[] args) {
        int low = 4, high = 9;
        exchange(low, high);
        System.out.println(low + " " + high);

        int points = 120;
        points = withBonus(points);   // the caller writes it into its own variable
        System.out.println(points);
    }
}
פלט
4 9
170

exchange החליפה רק בין left ל-right, ולכן מודפס 4 9. ב-withBonus הקורא עצמו כתב את הערך שחזר לתוך points, ולכן השינוי נשמר.

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

תכונה נוחה נובעת מכאן: קריאה למתודה שמקבלת רק ערכים לא תשנה אף משתנה בקוד הקורא. מי שקורא קוד כזה יכול לסמוך על כך שכל שינוי אצל הקורא כתוב בהשמות שלו עצמו.

נראה את זה עם שני threads, A ו-B, שקוראים באותו רגע ל-addBonus, אחד עם 120 והשני עם 300. כל אחד מריץ את הקריאה על המחסנית הפרטית שלו, ולכן נפתחות שתי מסגרות ובכל אחת score אחר. A מגיע ל-170 ו-B ל-350, ואף אחד מהם לא יכול לדרוס את המספר של השני.

מה מועבר למתודהמה מקבל כל threadהאם הגישה צריכה סנכרון
ערך פרימיטיביעותק פרטי במסגרת שלולא, אין כאן שום דבר משותף
הפניה לאובייקטעותק פרטי של ההפניה, ולא של האובייקטכן, כולם מגיעים לאותו אובייקט בערימה, ולכן צריך synchronized או lock (וב-.NET גם Mutex)

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

תרחיש 1: המלאי שלא התאפס

במערכת של מחסן נכתבה המתודה static void clearStock(int stock) { stock = 0; }. בקוד הקורא יש משתנה שגם הוא נקרא stock, והוא מחזיק 12. אחרי clearStock(stock) מדפיסים אותו, ועל המסך מופיע 12.

  • ברגע הקריאה נפתחת מסגרת עבור clearStock, ובה משתנה חדש בשם stock שמקבל את המספר 12.
  • ההשמה stock = 0 כותבת לתא שבמסגרת הזו.
  • בחזרה מהמתודה המסגרת מתפרקת, ואיתה התא שהתאפס.
  • התא של הקורא לא היה מעורב באף שלב, ולכן הוא עדיין מחזיק 12.

התיקון: המתודה מחזירה את הערך החדש והקורא כותב stock = clearStock(stock);, או שמאפסים את המשתנה ישירות במקום שבו הוא מוגדר.

טעויות נפוצות
  • המתודה מקבלת את המשתנה המקורי, ולכן מה שהיא כותבת בו מגיע גם לקוד שקרא לה. היא מקבלת ערך שהועתק לתא חדש. כתיבה לתא הזה נשארת בתוך המתודה.
  • אחרי שמעבירים משתנה By Value הוא נעשה קבוע, או משתחרר מהזיכרון. למשתנה של הקורא לא קורה דבר. הוא נשאר משתנה רגיל עם אותו ערך, ואפשר להמשיך לשנות אותו.
  • עבור int עובר למתודה מצביע אל המשתנה של הקורא. בפרימיטיב עובר המספר עצמו. אין כתובת שהמתודה יכולה לכתוב דרכה.
  • כשהפרמטר נקרא בשם של המשתנה של הקורא, שניהם הופכים למשתנה אחד. לכל אחד יש תא משלו ותחום משלו. השם הזהה הוא צירוף מקרים ותו לא.
  • אם מוסיפים static לפרמטר, השינוי יגיע גם לקורא. המהדר לא מקבל static על פרמטר בכלל. המילה הזו שייכת לשדות ולמתודות.
  • העברה By Value מגינה על threads בזכות נעילה של הערך, או בזכות חיסכון בהעתקה. ההגנה נובעת מכך שלכל קריאה יש עותק פרטי. אין שום נעילה, וההעתקה היא דווקא עבודה נוספת.
בדקו את עצמכם
static void halve(double price) { price = price / 2; } נקראת עם משתנה שמחזיק 9.0. מה יודפס כשהקורא ידפיס את המשתנה שלו אחרי הקריאה, ומה צריך לשנות כדי שיקבל 4.5?

יודפס 9.0, כי החלוקה נעשתה על העותק. משנים את המתודה כך שתחזיר double ותבצע return price / 2;, והקורא כותב price = halve(price);.

שני threads קוראים באותו רגע ל-static int square(int n), אחד עם 3 ואחד עם 5. האם צריך לנעול משהו כדי ששתי התוצאות יהיו נכונות?

לא. כל קריאה מקבלת n משלה במסגרת משלה, ואין ביניהן משתנה משותף. נעילה הייתה נחוצה רק אם שתיהן היו כותבות לאותו אובייקט.

חזרה לתוכן העניינים

הפניות ב-Java: האובייקט משותף, המשתנה לא

נתחיל במה שיש בתוך משתנה כמו Wallet mine. האובייקט שנוצר ב-new מוקצה בערימה (Heap), ואילו mine מחזיק רק הפניה (reference) אליו, מעין כתובת. אותו דבר נכון לכל משתנה מטיפוס מערך.

כשמעבירים משתנה כזה למתודה, הכלל של Java לא משתנה: התוכן של המשתנה מועתק, והתוכן הוא ההפניה. התוצאה היא שתי הפניות נפרדות, של הקורא ושל הפרמטר, שמכוונות לאותו אובייקט יחיד. שום עותק עמוק (Deep Copy) של האובייקט לא נוצר.

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

מהתמונה הזו יוצאים שני מקרים שונים, ושאלות קוד בודקות בדיוק את ההבדל ביניהם:

מה המתודה עושה עם הפרמטרדוגמההאם הקורא רואה
משנה את האובייקט שהפרמטר מכוון אליוw.coins += 40, items[1] = 0, names.add("Lior")כן, יש רק אובייקט אחד
מציבה בפרמטר אובייקט אחרw = new Wallet(40)לא, רק העותק של ההפניה הוסט
Java
public class Main {
    static class Wallet {
        int coins;
        Wallet(int coins) { this.coins = coins; }
    }

    static void replace(Wallet w) { w = new Wallet(40); }   // points the copy elsewhere
    static void topUp(Wallet w)   { w.coins += 40; }        // edits the object both sides share

    public static void main(String[] args) {
        Wallet mine = new Wallet(3);
        replace(mine);
        System.out.println(mine.coins);
        topUp(mine);
        System.out.println(mine.coins);
    }
}
פלט
3
43

נעקוב אחרי replace(mine), ונקרא לארנק המקורי W1:

רגעmine אצל הקוראהפרמטר w
לפני הקריאהמכוון ל-W1, שבו coins = 3עוד לא קיים
כניסה ל-replaceמכוון ל-W1מקבל עותק של ההפניה, ולכן גם הוא מכוון ל-W1
אחרי w = new Wallet(40)ממשיך להיות מכוון ל-W1מכוון לארנק חדש W2, שבו coins = 40
אחרי החזרהW1 לא השתנה, ולכן מודפס 3נמחק עם המסגרת, ו-W2 כבר לא נגיש לאף אחד

שימו לב שהשורה w = new Wallet(40) עברה הידור בלי שום תלונה. ההשפעה שלה מוגבלת לפרמטר: W1 שומר על 3 המטבעות שלו, ו-mine ממשיך להחזיק את אותה הפניה, שלא הפכה ל-null.

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

Java
public class Main {
    static class Wallet {
        int coins;
        Wallet(int coins) { this.coins = coins; }
    }

    static void replace(final Wallet w) {
        w.coins = 7;            // allowed: the object itself may change
        w = new Wallet(40);     // not allowed: w is final
    }
}
פלט
Main.java:9: error: final parameter w may not be assigned
        w = new Wallet(40);     // not allowed: w is final
        ^
1 error
איך לנסח את זה בשאלת הגדרה: מה שעובר ב-Java הוא הפניה, By Value. מי שאומר שאובייקטים עוברים By Reference טועה, כי By Reference אמיתי פירושו שהפרמטר הוא כינוי (alias) של המשתנה שבצד הקורא, ושהשמה אליו מגיעה לשם. Java לא מציעה את זה בשום צורה, וב-C# זה זמין דרך ref ו-out.
תרחיש 2: כרטיס שהוחלף באמצע

מתודה assignSeat(Ticket t) פותחת בשורה t = cache.find(t.id);, שמחזירה אובייקט כרטיס אחר מתוך מטמון, וממשיכה ב-t.seat = "12A";. הקורא מעביר כרטיס משלו. אילו שינויים יראה?

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

עכשיו הפכו את סדר השורות: קודם t.seat = "12A" ורק אחר כך ההשמה. המושב נכתב לכרטיס של הקורא בזמן ש-t עוד הפנה אליו, ולכן השינוי הזה נשאר. ההשמה שבאה אחריו עדיין לא יוצאת מהמתודה.

טעויות נפוצות
  • ב-Java אובייקט עובר By Reference, ולכן הפרמטר הוא שם נוסף למשתנה של הקורא. עובר עותק של ההפניה. שם נוסף למשתנה של הקורא אפשר לקבל רק ב-C#, ורק כשהפרמטר מסומן ref או out.
  • אחרי w = new Wallet(40) בתוך המתודה, גם המשתנה של הקורא מכוון לארנק החדש. רק העותק הוסט. המשתנה של הקורא נשאר מכוון לאובייקט שהיה לו קודם.
  • לפני הקריאה נבנה שכפול שלם של האובייקט, ולכן המתודה לא יכולה לשנות את המקורי. האובייקט לא משוכפל. בדיוק בגלל זה שינוי שדה דרך הפרמטר כן מגיע לקורא.
  • הצבה של אובייקט טרי בפרמטר מאפסת את השדות של האובייקט הישן, או משאירה את הקורא עם null. האובייקט הישן וההפניה של הקורא אליו יוצאים מהקריאה בלי שום שינוי.
  • המהדר של Java דוחה השמה לפרמטר מטיפוס מחלקה. ההשמה חוקית לגמרי. רק פרמטר שהוצהר final חוסם אותה.
בדקו את עצמכם
static void tweak(Account a) { a.balance -= 10; a = new Account(); a.balance = 999; } נקראת עם חשבון שבו balance הוא 100. מה היתרה אצל הקורא אחרי הקריאה?

90. ההפחתה בוצעה כשהפרמטר עוד הפנה לחשבון של הקורא. אחרי ההשמה a מכוון לחשבון חדש, וה-999 נכתב שם.

אם היו מצהירים על הפרמטר של topUp כ-final, האם ההוספה של 40 המטבעות הייתה נחסמת?

לא. final חוסם רק השמה חדשה לפרמטר. שינוי של שדה באובייקט שהוא מכוון אליו נשאר מותר.

חזרה לתוכן העניינים

מערכים, String ואיך מחזירים שינוי לקורא ב-Java

מערך ב-Java הוא אובייקט שחי בערימה, ולכן שני הכללים מהחלק הקודם חלים עליו כמו שהם. כתיבה לתא דרך הפרמטר מגיעה למערך של הקורא, והצבה של מערך אחר בפרמטר מסיטה רק את העותק של ההפניה.

Java
import java.util.Arrays;

public class Main {
    static void mark(char[] seats) {
        seats[2] = 'X';           // the caller's array
        seats = new char[4];      // from now on: a brand new array
        seats[0] = 'Y';           // touches the new array only
    }

    public static void main(String[] args) {
        char[] seats = {'a', 'b', 'c'};
        mark(seats);
        System.out.println(Arrays.toString(seats));
    }
}
פלט
[a, b, X]

התו X נכתב לפני ההסטה, ולכן הוא במערך של הקורא. ה-Y נכתב למערך החדש בן ארבעת התאים, שנעלם בסוף הקריאה.

כדי לכתוב לתאים של מערך שהתקבל לא צריך שום הצהרה מיוחדת. המתודה מקבלת גישה מלאה לאותו מערך, שלא שוכפל ולא סומן לקריאה בלבד. אילו הייתם מוסיפים final לפרמטר, רק השורה seats = new char[4] הייתה נכשלת בהידור.

String מתנהג אחרת מסיבה שאין לה קשר להעברה עצמה: הוא immutable (לא ניתן לשינוי). אף מתודה שלו לא נוגעת בתווים של מחרוזת קיימת. פעולות כמו שרשור או trim() מחזירות מחרוזת, וכשהתוכן אמור להשתנות זו מחרוזת חדשה, בעוד המקורית נשארת כפי שהייתה.

לכן tag = tag + " ok" בתוך מתודה הוא בעצם השמה לפרמטר: נוצרת מחרוזת חדשה, והעותק של ההפניה מוסט אליה. גם טיפוסי העטיפה, כמו Integer, Long ו-Double, הם immutable. StringBuilder הוא המקרה ההפוך: אובייקט שנועד לשינוי, ו-append כותב לתוכו.

Java
public class Main {
    static void decorate(StringBuilder log, String tag, Integer count) {
        log.append(" ok");        // mutates the shared builder
        tag = tag + " ok";        // a new String, stored in the copy
        count = count + 1;        // a new Integer, stored in the copy
    }

    public static void main(String[] args) {
        StringBuilder log = new StringBuilder("boot");
        String tag = "boot";
        Integer count = 7;
        decorate(log, tag, count);
        System.out.println(log + " | " + tag + " | " + count);
    }
}
פלט
boot ok | boot | 7

רק log השתנה אצל הקורא. גם count = count + 1 יצר Integer חדש ושמר אותו בעותק, בדיוק כמו שקרה למחרוזת.

נניח שבכל זאת אתם צריכים שמתודה תעדכן מונה שנמצא אצל הקורא. ב-Java יש לכך שני פתרונות שמקובל להשתמש בהם:

  1. להחזיר את הערך מהמתודה ולתת לקורא להציב אותו, כמו points = withBonus(points). זו הדרך הפשוטה והקריאה ביותר כשמדובר בערך אחד.
  2. לעטוף את הערך באובייקט שניתן לשנות: מחלקה קטנה עם שדה יחיד, או מערך בגודל 1, ולשנות בתוך המתודה את השדה או את התא.
Java
public class Main {
    static class IntBox { int value; }

    static void bump(IntBox box)  { box.value += 5; }   // a tiny mutable holder
    static void bump(long[] slot) { slot[0] += 5; }     // a one-slot array does the same job

    public static void main(String[] args) {
        IntBox box = new IntBox();
        box.value = 10;
        long[] slot = {10};
        bump(box);
        bump(slot);
        System.out.println(box.value + " " + slot[0]);
    }
}
פלט
15 15

למה העטיפה עובדת? bump מקבלת עותק של ההפניה ל-box, אבל שני העותקים מובילים לאותו IntBox בערימה. הכתיבה ל-value היא שינוי של האובייקט ולא הסטה של הפרמטר, ולכן היא נראית בחוץ, וכך גם הכתיבה לתא של המערך הקטן.

תרחיש 3: שלושה פרמטרים, שלוש תוצאות

המתודה apply(long attempts, double[] balances, String status) מבצעת attempts++; balances[1] -= 20; status = status.trim();. הקורא שולח את 2, את המערך {50, 80} ואת המחרוזת " open ".

  • attempts הוא פרימיטיב, וההגדלה נשארת בעותק. אצל הקורא עדיין 2.
  • balances הוא הפניה למערך, וההפחתה בתא נוחתת במערך של הקורא: התא השני יורד ל-60.
  • trim() מחזירה מחרוזת חדשה בלי הרווחים, וההשמה מסיטה אליה רק את status של המתודה. אצל הקורא הרווחים נשארים.

בהרצה הקורא מדפיס 2 60.0 [ open ]: מכל שלושת השינויים, רק התא במערך שרד.

טעויות נפוצות
  • כל קריאה למתודה מקבלת שכפול של המערך, ולכן כתיבה לתא לא תגיע לקורא. רק ההפניה מועתקת, והמתודה כותבת לאותו מערך שהקורא מחזיק.
  • כדי לשנות תאים במערך שהתקבל צריך להצהיר על הפרמטר final, ובלי זה המערך נהיה לקריאה בלבד. final לא קשור לכתיבה לתאים, ושום מערך לא נהיה לקריאה בלבד. final רק אוסר להציב בפרמטר מערך אחר.
  • שרשור למחרוזת שהתקבלה כפרמטר משנה את המחרוזת שהקורא מחזיק. String לא ניתן לשינוי. השרשור יוצר מחרוזת חדשה, והיא נשמרת רק בפרמטר.
  • כדי להעביר By Reference ב-Java כותבים ref בחתימה ובקריאה. ref קיימת ב-C# בלבד. ב-Java היא פשוט לא מתקמפלת.
  • Integer הוא אובייקט, ולכן count = count + 1 בתוך מתודה יגדיל את המספר גם אצל הקורא. Integer הוא immutable, והחיבור יוצר אובייקט חדש שמוצב רק בפרמטר.
  • אם מסמנים את הפרמטר final, הערך שהמתודה חישבה יחזור לקורא בסוף הקריאה. final רק חוסם השמה לפרמטר. שום ערך לא מועתק בחזרה לקורא.
  • עטיפה של מספר בתוך String תאפשר למתודה לעדכן אותו עבור הקורא. במחרוזת אין מה לשנות, כי היא immutable. עוטף מתאים הוא אובייקט עם שדה שאפשר לכתוב אליו.
בדקו את עצמכם
מתודה מקבלת Map<String, Integer> stock, מבצעת stock.put("pens", 1);, אחר כך stock = new HashMap<>(); ולבסוף stock.put("cups", 2);. המפה של הקורא הייתה ריקה. מה היא מכילה אחרי הקריאה?

רק את pens=1. ההכנסה הראשונה נעשתה במפה המשותפת, וההשמה העבירה את הפרמטר למפה חדשה שאף אחד מחוץ למתודה לא רואה.

צריך מתודה שמוסרת לקורא גם את המינימום וגם את המקסימום של מערך. אילו מהדרכים שראינו מתאימות ב-Java?

להחזיר אובייקט קטן עם שני שדות, או לקבל אובייקט עוטף (או מערך בגודל 2) שהמתודה ממלאת. ref לא קיים, ו-final או String לא יחזירו דבר.

חזרה לתוכן העניינים

C#: struct מול class

ב-C# כל טיפוס שייך לאחת משתי משפחות, וההשתייכות הזו קובעת מה עובר לפרמטר בקריאה רגילה.

משפחהמי שייך אליהמה שמור במשתנה
טיפוס ערך (value type)int, double, bool וכל structהנתונים עצמם
טיפוס הפניה (reference type)כל class, כל מערך, ו-stringהפניה לאובייקט, בדיוק כמו ב-Java

בקריאה רגילה, בלי מילת מפתח, C# מעבירה By Value בשתי המשפחות. ההבדל הוא רק במה שמשוכפל, כי תמיד משוכפל התוכן של המשתנה:

הפרמטר הואמה משוכפל בקריאהשינוי שדה בתוך המתודה
structכל המבנה, שדה אחרי שדהנשאר בשכפול, והקורא לא רואה אותו
classההפניה בלבדנוחת על האובייקט המשותף, והקורא רואה אותו
C#
using System;

struct Pixel { public int R; }
class  Layer { public int Alpha; }

class Program {
    static void Dim(Pixel p, Layer l) {
        p.R = 200;       // edits the private copy of the struct
        l.Alpha = 200;   // edits the object the caller also holds
    }

    static void Main() {
        Pixel px = new Pixel();
        Layer layer = new Layer();
        Dim(px, layer);
        Console.WriteLine(px.R + " " + layer.Alpha);
    }
}
פלט
0 200

px.R נשאר 0, ערך ברירת המחדל של שדה int. המתודה כתבה 200 לתוך השכפול של המבנה, והשכפול נעלם בסוף הקריאה.

כמה שאלות על השכפול הזה חוזרות שוב ושוב. הנה התשובות, מרוכזות:

שאלההתשובה עבור struct בהעברה רגילה
מתי נוצר השכפול?ברגע הקריאה, בכל קריאה, גם כשהמתודה רק קוראת מהמבנה ולא כותבת בו
האם ה-CLR (סביבת הריצה של .NET) מחליף אותו בהפניה כדי לחסוך?לא, המבנה מועתק כפי שהקוד ביקש
כמה זה עולה?כל השדות מועתקים, לעומת כתובת אחת בהעברה של class. במבנה גדול ההבדל מורגש
איך חוסכים?מעבירים עם in (מ-C# 7.2, הפניה לקריאה בלבד) או עם ref
ומה אם המבנה מחזיק שדה מטיפוס class?מועתקת ההפניה שבשדה, והאובייקט עצמו נשאר משותף (הדוגמה הבאה)
האם יש כאן boxing?לא. boxing, אריזה של טיפוס ערך בתוך אובייקט בערימה, קורה רק כשממירים את המבנה ל-object או לממשק

הדוגמה הבאה ממחישה את השורה של שדה ה-class: מבנה Order שמחזיק הפניה ללקוח עובר למתודה שמשנה גם את הכמות וגם את שם הלקוח.

C#
using System;

class Customer { public string Name; }

struct Order {
    public int Qty;
    public Customer Buyer;   // a reference stored inside a struct
}

class Program {
    static void Edit(Order o) {
        o.Qty = 99;              // the copied struct only
        o.Buyer.Name = "Noa";    // the copied reference still reaches the same Customer
    }

    static void Main() {
        Order order = new Order { Qty = 1, Buyer = new Customer { Name = "Avi" } };
        Edit(order);
        Console.WriteLine(order.Qty + " " + order.Buyer.Name);
    }
}
פלט
1 Noa

התוצאה מתפצלת. הכמות 99 נכתבה לגרסה המשוכפלת ונעלמה, ולכן הקורא עדיין רואה 1. השם Noa נכתב דרך הפניה שהועתקה כמו שהיא, אל אותו Customer שהקורא מחזיק, ולכן הוא נשאר: השכפול שטחי.

בשאלות קוד ב-C#, המילה שבהגדרת הטיפוס (struct או class) חשובה יותר מכל שורה בתוך המתודה. התרחיש הבא מראה למה.
תרחיש 4: מילה אחת בהגדרה משנה את הפלט

נתונה static void Paint(Brush b) { b.Width = 4; }. הקורא מעביר משתנה brush שבו Width הוא 1, ואחר כך מדפיס את brush.Width.

  • אם Brush מוגדר struct: b הוא שכפול מלא של brush, השינוי נשאר בשכפול, ומודפס 1.
  • אם מחליפים בהגדרה את struct ב-class ולא נוגעים בשום שורה אחרת: b הוא עותק של ההפניה, השינוי נוחת על האובייקט המשותף, ומודפס 4.

מכאן כלל עבודה לשאלות קוד ב-C#: לפני שקובעים מה יודפס, בדקו איך הטיפוס מוגדר. אותה קריאה בדיוק נותנת תוצאה שונה עבור struct ועבור class.

טעויות נפוצות
  • בקריאה רגילה עם struct עוברת הפניה, ולכן שינוי שדה יופיע אצל הקורא. עובר שכפול של כל המבנה, והשינוי נשאר בשכפול.
  • ה-CLR מעביר struct כהפניה מאחורי הקלעים, כך שההעברה שלו לא עולה דבר. ההעתקה מתבצעת בכל קריאה. בגלל זה struct גדול מעבירים עם in או ref.
  • השכפול נוצר רק כשהמתודה כותבת לשדה. השכפול נוצר בכניסה למתודה, בלי קשר למה שהיא עושה בו אחר כך.
  • העברה רגילה משכפלת גם את האובייקטים שהמבנה מפנה אליהם, ואף אורזת אותו ב-boxing. שדה מטיפוס class משוכפל כהפניה בלבד, ו-boxing מתרחש כשממירים מבנה ל-object או לממשק, ולא בהעברה.
  • struct אי אפשר להעביר By Value. זו בדיוק ההעברה הרגילה שלו, בלי שום מילת מפתח.
בדקו את עצמכם
struct Temperature { public double Celsius; public string Unit; } ומתודה static void Freeze(Temperature t) { t.Celsius = 0; }. הקורא מחזיק מדידה של 21.5 ומדפיס אותה אחרי הקריאה. מה יודפס, ומה ישתנה אם Temperature יוגדר class?

כ-struct יודפס 21.5, כי המתודה כתבה לשכפול. כ-class יודפס 0, כי שני הצדדים מחזיקים הפניה לאותו אובייקט.

מתודה מקבלת struct בן 40 שדות, נקראת מיליון פעמים בלולאה ורק קוראת ממנו. מה אפשר לשנות בחתימה כדי לחסוך עבודה, בלי לאפשר לה לשנות אותו?

להעביר אותו עם in. כך עוברת הפניה במקום שכפול של כל השדות, והמהדר אוסר על המתודה לכתוב לפרמטר.

חזרה לתוכן העניינים

C#: ref, out ו-in

שלוש מילות מפתח ב-C# מעבירות את המשתנה עצמו במקום ערך שהועתק ממנו. עם ref ועם out הפרמטר הופך לשם נוסף (alias) לאותו תא של הקורא, ולכן כל השמה אליו נוחתת אצל הקורא. in גם הוא מעביר הפניה למשתנה, אבל לקריאה בלבד: מותר לקרוא דרכו ואסור להציב בו.

מילהמה נדרש מהקורא לפני הקריאהמה מותר ונדרש בתוך המתודהבשורת הקריאה
refמשתנה שכבר קיבל ערךקריאה וכתיבה בלי הגבלהחובה לכתוב ref
outאין צורך באתחולחובה להציב ערך בכל נתיב ריצה לפני היציאה, ואסור לקרוא ממנו לפני ההצבה הראשונהחובה לכתוב out
in (מ-C# 7.2)משתנה שכבר קיבל ערךקריאה בלבד, כתיבה אסורהלא חובה לכתוב in

דוגמה שמשלבת פרמטר רגיל ופרמטר ref באותה חתימה:

C#
using System;

class Program {
    static void Charge(int fee, ref int balance) {
        fee *= 2;          // fee is a copy of the caller's value
        balance -= fee;    // balance is the caller's variable under another name
    }

    static void Main() {
        int fee = 5, balance = 100;
        Charge(fee, ref balance);
        Console.WriteLine(fee + " " + balance);
    }
}
פלט
5 90

fee הוכפל בתוך המתודה, אבל רק בעותק, ולכן הקורא מדפיס 5. ההפחתה מ-balance נעשתה ישירות במשתנה של הקורא, ולכן נשארו 90.

גם החלפה בין שני משתנים, שב-Java לא הייתה אפשרית, עובדת עם ref:

C#
using System;

class Program {
    static void Rotate(ref string first, ref string second) {
        string tmp = first;
        first = second;
        second = tmp;
    }

    static void Main() {
        string from = "north", to = "south";
        Rotate(ref from, ref to);
        Console.WriteLine(from + " " + to);
    }
}
פלט
south north

ref הוא חלק מהחוזה של המתודה, ולכן צריך לכתוב אותו גם בצד הקורא. כשמשמיטים אותו, ההידור נכשל:

C#
using System;

class Program {
    static void Rotate(ref string first, ref string second) {
        string tmp = first;
        first = second;
        second = tmp;
    }

    static void Main() {
        string from = "north", to = "south";
        Rotate(from, ref to);   // ref is missing on the first argument
        Console.WriteLine(from + " " + to);
    }
}
פלט
Program.cs(12,16): error CS1620: Argument 1 must be passed with the 'ref' keyword

ref ומשתנה בלי ערך. מתודה שמקבלת ref רשאית לקרוא את מה שכבר נמצא במשתנה, ולכן חייב להיות שם ערך. ב-C# משתנה מקומי שהוצהר בלי השמה לא מחזיק אפילו 0, כך שהמהדר עוצר את הקריאה:

C#
using System;

class Program {
    static void Bump(ref int hits) { hits += 2; }

    static void Main() {
        int hits;            // declared, never given a value
        Bump(ref hits);
        Console.WriteLine(hits);
    }
}
פלט
Program.cs(8,18): error CS0165: Use of unassigned local variable 'hits'

התוכנית נעצרת עוד לפני שהיא נבנית, כך שאין ריצה לדבר עליה: לא מודפס כלום, ושום חריגה לא נזרקת. מספיק לשנות את ההצהרה ל-int hits = 0; כדי שיודפס 2.

out: הכיוון ההפוך. ב-out הערך זורם רק החוצה, מהמתודה אל הקורא. לכן לא אכפת למהדר אם במשתנה של הקורא היה ערך קודם, אבל הוא מחייב את המתודה: אין יציאה ממנה, באף ענף, לפני שהוצב ערך בפרמטר.

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

C#
using System;

class Program {
    static void ReadPort(string text, out int port) {
        if (text.Length > 0)
            port = 8080;     // nothing is assigned when text is empty
    }

    static void Main() {
        int p;
        ReadPort("x", out p);
        Console.WriteLine(p);
    }
}
פלט
Program.cs(4,17): error CS0177: The out parameter 'port' must be assigned to before control leaves the current method

גם קריאה מפרמטר out לפני ההצבה הראשונה בו נחסמת:

C#
using System;

class Program {
    static void Peek(out int code) {
        Console.WriteLine(code);   // read before anything was assigned
        code = 3;
    }

    static void Main() {
        Peek(out int c);
    }
}
פלט
Program.cs(5,27): error CS0269: Use of unassigned out parameter 'code'

הצורה התקינה מציבה ערך בכל ענף. זה הדפוס של מתודות Try ב-.NET, כמו int.TryParse: הערך המוחזר אומר אם הפעולה הצליחה, והתוצאה יוצאת דרך out. אפשר להצהיר על המשתנה בתוך הקריאה עצמה (out int q2), ו-out מתאים לכל טיפוס, גם לטיפוס הפניה:

C#
using System;

class Layer { public int Alpha; }

class Program {
    static bool TryDivide(int a, int b, out int quotient) {
        if (b == 0) { quotient = 0; return false; }   // every path assigns
        quotient = a / b;
        return true;
    }

    static void NewLayer(out Layer l) { l = new Layer { Alpha = 80 }; }   // out of a class type

    static void Main() {
        int q;                                         // no starting value needed
        Console.WriteLine(TryDivide(17, 4, out q) + " " + q);
        Console.WriteLine(TryDivide(5, 0, out int q2) + " " + q2);
        NewLayer(out Layer made);
        Console.WriteLine(made.Alpha);
    }
}
פלט
True 4
False 0
80

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

C#
using System;

struct Matrix { public int Rows; public int Cols; }

class Program {
    static int Cells(in Matrix m) {
        m.Rows = 3;              // in means read only
        return m.Rows * m.Cols;
    }

    static void Main() {
        Matrix m = new Matrix { Rows = 2, Cols = 5 };
        Console.WriteLine(Cells(m));
    }
}
פלט
Program.cs(7,9): error CS8332: Cannot assign to a member of variable 'in Matrix' or use it as the right hand side of a ref assignment because it is a readonly variable

בצד הקורא in הוא רשות. שתי הצורות מתקמפלות ונותנות אותה תוצאה:

C#
using System;

struct Matrix { public int Rows; public int Cols; }

class Program {
    static int Cells(in Matrix m) => m.Rows * m.Cols;   // reads only

    static void Main() {
        Matrix m = new Matrix { Rows = 2, Cols = 5 };
        Console.WriteLine(Cells(m) + " " + Cells(in m));    // in at the call site is optional
    }
}
פלט
10 10

ref מול struct ומול class. כשהפרמטר הוא struct, ref הוא מה שמביא שינוי שדה אל המבנה של הקורא, כי בלעדיו המתודה עובדת על שכפול:

C#
using System;

struct Size { public int W; }

class Program {
    static void Grow(Size s)        { s.W = 30; }
    static void GrowRef(ref Size s) { s.W = 30; }

    static void Main() {
        Size first = new Size { W = 10 };
        Size second = new Size { W = 10 };
        Grow(first);
        GrowRef(ref second);
        Console.WriteLine(first.W + " " + second.W);
    }
}
פלט
10 30

עבור class התמונה אחרת. שינוי שדה ממילא מגיע לקורא, כי שני הצדדים מחזיקים הפניה לאותו אובייקט. ref נחוץ רק כשהמתודה רוצה להשאיר בידי הקורא אובייקט אחר לגמרי:

C#
using System;

class Session { public string User; }

class Program {
    static void Relog(Session s)        { s = new Session { User = "guest" }; }
    static void RelogRef(ref Session s) { s = new Session { User = "guest" }; }

    static void Main() {
        var plain = new Session { User = "admin" };
        var byRef = new Session { User = "admin" };
        Relog(plain);
        RelogRef(ref byRef);
        Console.WriteLine(plain.User + " " + byRef.User);
    }
}
פלט
admin guest
ההבדל במשפט אחד: הפניה שהועתקה (מה ש-Java עושה תמיד, ו-C# עושה כברירת מחדל) מאפשרת לשנות את האובייקט, אבל לא להחליף אותו אצל הקורא. כינוי אמיתי, שבו גם החלפה מגיעה לקורא, מתקבל רק עם ref או out.
תרחיש 5: ספירה של הכפלות

נתונות static void Twice(int v) { v *= 2; } ו-static void TwiceRef(ref int v) { v *= 2; }. הקורא מתחיל ב-int n = 3;, קורא ל-Twice(n), אחר כך פעמיים ל-TwiceRef(ref n), ומדפיס את n.

  • Twice(n) מכפילה את העותק שלה, ו-n עדיין 3.
  • הקריאה הראשונה ל-TwiceRef עובדת על n עצמו, שעולה ל-6.
  • הקריאה השנייה מביאה אותו ל-12.

מודפס 12, וכך התקבל גם בהרצה. מי שעונה 24 התייחס לקריאה בלי ref כאילו שינתה את n, ומי שעונה 3 שכח ש-ref כותב ישירות למשתנה של הקורא.

טעויות נפוצות
  • משתנה מקומי ב-C# מתחיל ב-0, ולכן מותר להעביר אותו עם ref לפני שהוצב בו ערך. למשתנה מקומי אין ערך ברירת מחדל, והמהדר עוצר עם CS0165.
  • העברה של משתנה לא מאותחל עם ref תסתיים ב-NullReferenceException בזמן ריצה. התוכנית לא מגיעה לריצה בכלל: זו שגיאת הידור.
  • גם עם out הקורא חייב לאתחל את המשתנה לפני הקריאה. זו הדרישה של ref. ב-out החובה עוברת לצד השני: המתודה היא שחייבת להציב.
  • אם הקורא מעביר ארגומנט שבזכותו התנאי מתקיים, הצבה בתוך if מספיקה ל-out. המהדר לא יודע מה יעבור בזמן ריצה. הוא בוחן כל נתיב אפשרי, ונתיב יחיד בלי הצבה מספיק ל-CS0177.
  • מותר לקרוא פרמטר out בתחילת המתודה, ו-out מיועד רק לטיפוסי ערך. קריאה לפני הצבה נותנת CS0269, ו-out עובד עם כל טיפוס, כולל class.
  • כשהחתימה דורשת ref, אפשר לקרוא למתודה בלי לכתוב ref ליד הארגומנט. ref ו-out חייבים להופיע גם בקריאה. בלעדיהם מתקבלת CS1620.
בדקו את עצמכם
static void Classify(int n, out string kind) { if (n > 0) kind = "positive"; else if (n < 0) kind = "negative"; }. האם הקוד מתקמפל, ומה התיקון הקטן ביותר?

לא. כש-n שווה 0 אף ענף לא מציב ב-kind, והמהדר מדווח CS0177, גם אם בפועל תמיד מעבירים מספר חיובי. מוסיפים else kind = "zero";, או מציבים ערך התחלתי בראש המתודה.

מתודה מוגדרת static double Area(in Rect r). האם הקריאה Area(rect) בלי in תקינה, והאם המתודה יכולה לכתוב r.Width = 0?

הקריאה תקינה, כי בצד הקורא in אינו חובה. הכתיבה לשדה נעצרת בהידור, כי in מעביר הפניה לקריאה בלבד.

static void Relog(Session s) ו-static void RelogRef(ref Session s) מבצעות שתיהן רק s.User = "guest". במה תהיה שונה התוצאה אצל הקורא?

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

חזרה לתוכן העניינים

Recursion: רקורסיה, מתודה שמפעילה את עצמה

מקרה בסיס וצעד רקורסיבי: שני החלקים של כל רקורסיה

רקורסיה (Recursion) היא דרך לפתור בעיה שבה מתודה מפעילה את עצמה על גרסה מוקטנת של אותה בעיה. התשובה שחוזרת מהגרסה הקטנה היא חומר הגלם לתשובה הגדולה.

ההפעלה העצמית מגיעה בשתי צורות. בקריאה ישירה שם המתודה מופיע בתוך הגוף שלה עצמה. בקריאה עקיפה A מפעילה את B, ו-B היא זו שמפעילה שוב את A.

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

כל מתודה רקורסיבית שעובדת נשענת על שני רכיבים:

רכיבמה הוא עושהמה קורה בלעדיו
מקרה בסיס (base case), שנקרא גם תנאי עצירהמזהה קלט קטן מספיק שהתשובה עליו ידועה, ומחזיר אותה מיד בלי להפעיל שוב את המתודהשום דבר לא עוצר את שרשרת הקריאות
צעד רקורסיבי (recursive case)מפעיל את המתודה על קלט שקרוב יותר למקרה הבסיס, ומשתמש בתשובה שחוזרתאין דרך לפרק בעיה גדולה לחלקים

הדוגמה שחוזרת כמעט בכל מבחן היא עצרת (Factorial): מכפלת כל השלמים מ-1 ועד n, כשלפי ההגדרה העצרת של 0 שווה 1.

מההגדרה נובע הקשר n! = n * (n - 1)!, כלומר העצרת של n היא n כפול העצרת של המספר שמתחתיו.

Java
public class Factorial {
    public static void main(String[] args) {
        System.out.println("0! = " + factorial(0));
        System.out.println("6! = " + factorial(6));
        System.out.println("12! = " + factorial(12));
    }

    static long factorial(int n) {
        if (n == 0) return 1;            // base case: 0! is defined as 1
        return n * factorial(n - 1);     // recursive case: n! = n * (n - 1)!
    }
}
פלט
0! = 1
6! = 720
12! = 479001600

כל הפעלה מורידה את הארגומנט באחד. השרשרת factorial(6), factorial(5) וכן הלאה נגמרת ב-factorial(0), שמחזירה 1 בלי קריאה נוספת, ומשם כל המכפלות שהמתינו נסגרות.

בשאלות על עצרת מופיעות לצד התשובה הנכונה שלוש נוסחאות שנראות דומות. זה מה שכל אחת מהן היא באמת:

מה מתואר במסיחמה זה באמת
n כפול n כפול n, סך הכול n גורמיםחזקה: n בחזקת n
הפעלה עצמית עם חצי מהערך, עד שמגיעים ל-1הצעד שמאפיין חיפוש בינארי
1 + 2 + ... + nסכום, צבירה בחיבור ולא בכפל

ב-factorial שלמעלה הארגומנט יורד בדיוק ב-1, הפעולה היא כפל, והשרשרת נעצרת ב-0.

הסתכלו שוב על השורה if (n == 0) return 1; ב-factorial. שלושה דברים נכונים לגביה: היא עומדת לפני factorial(n - 1), היא מחזירה ערך מוכן, ואין בתוכה הפעלה של factorial. כל אחד מהם הוא כלל:

  • הסדר. נניח שהבדיקה הייתה מתחת לקריאה. factorial(0) הייתה מפעילה את factorial(-1) עוד לפני שבדקה משהו, וזו את factorial(-2), בלי שום בלם, עד שמחסנית הקריאות (נכיר אותה בתת-הפרק הבא) מתמלאת.
  • ערך מוכן. אפשר להציב כמה תחנות עצירה, למשל if (k == 0) return 2; ומתחתיה if (k == 1) return 1;, ובלבד שכולן בפתיחת המתודה וכל אחת מחזירה תשובה ישירות.
  • בלי הפעלה עצמית. שורה כמו if (n == 0) return factorial(n - 1); נראית כמו מקרה בסיס, אבל היא רק עוד צעד, ולא עוצרת דבר.

ומה לגבי הצעד? בדקו איזה ארגומנט הוא שולח: ב-factorial זה n - 1, כך שכל הפעלה קרובה יותר ל-0. אילו היה כתוב factorial(n), כל הפעלה הייתה מקבלת את אותו n כמו קודמתה, ההשוואה ל-0 הייתה נכשלת בכל פעם מחדש, והריצה הייתה נגמרת ב-StackOverflowError.

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

ומה עם משתנה static int calls שעוצר את הכול כשהוא מגיע ל-50? מונה כזה עוצר באותה נקודה לא משנה מה הקלט, ולכן ברשימה של 200 איברים יסוכמו רק 50 והתוצאה תצא שגויה. מקרה בסיס אמיתי נגזר מהקלט עצמו.

תרחיש 6: מדרגות, צעד אחד או שניים

כמה דרכים יש לעלות n מדרגות, כשבכל צעד עולים מדרגה אחת או שתיים? למדרגה n מגיעים מהמדרגה שמתחתיה או משתיים מתחתיה, ולכן ways(n) = ways(n - 1) + ways(n - 2). זו התבנית של סדרת פיבונאצ'י: שני האיברים הראשונים הם 0 ו-1, ומכל אינדקס 2 והלאה מחברים את שני האיברים שקודמים לו.

הצעד הזה מוריד את n פעם ב-1 ופעם ב-2. מי שכותב מקרה בסיס רק עבור 0 שוכח את n שווה 1: משם הענף של n - 2 קופץ ישר ל-1-, מדלג מעל 0, ומאותו רגע רק ממשיך לרדת.

Java
public class Stairs {
    public static void main(String[] args) {
        System.out.println("ways(5) = " + ways(5));
        try {
            System.out.println(waysBroken(5));
        } catch (StackOverflowError e) {
            System.out.println("waysBroken(5): StackOverflowError");
        }
    }

    // number of ways to climb n stairs, one or two stairs per move
    static long waysBroken(int n) {
        if (n == 0) return 1;                        // a single base case
        return waysBroken(n - 1) + waysBroken(n - 2);
    }

    static long ways(int n) {
        if (n <= 1) return 1;                        // covers both n == 0 and n == 1
        return ways(n - 1) + ways(n - 2);
    }
}
פלט
ways(5) = 8
waysBroken(5): StackOverflowError

התיקון הוא לכסות את שתי הנקודות שבהן הצעד יכול לנחות. אפשר לכתוב שני if נפרדים בראש המתודה, אחד ל-0 ואחד ל-1, ואפשר בדיקה אחת n <= 1 שתופסת את שניהם, כמו ב-ways. בפיבונאצ'י עצמו הבדיקה המאוחדת מחזירה את n, וכך 0 נותן 0 ו-1 נותן 1.

טעויות נפוצות
  • רקורסיה היא סוג של לולאה שרצה מספר קבוע של סבבים. ברקורסיה המתודה מפעילה את עצמה ופותחת קריאה חדשה בכל שלב. לולאה חוזרת על אותו גוף קוד בתוך קריאה אחת, בלי להפעיל מחדש את המתודה.
  • כל ההפעלות של מתודה רקורסיבית עובדות על אותם משתנים, שיושבים בזיכרון משותף. כל הפעלה מקבלת מסגרת משלה (פירוט בתת-הפרק הבא) ובה עותק פרטי של הפרמטרים והמשתנים המקומיים.
  • רקורסיה פירושה לשמור תוצאות קודמות כדי לא לחשב אותן שוב. זו Memoization, טכניקה נפרדת שאפשר להוסיף לרקורסיה. היא לא ההגדרה של רקורסיה.
  • אפשר לבדוק את מקרי הקצה בסוף, אחרי שההפעלה העצמית חזרה. ההפעלה לא תחזור אם שום דבר לא עצר אותה לפני כן. הבדיקה חייבת לבוא קודם.
  • מספיק שיש תנאי עצירה, גם אם הארגומנט עובר הלאה בלי שינוי. תנאי שהערך אף פעם לא מגיע אליו לא עוצר דבר.
  • מקטינים את הבעיה כדי לחסוך זמן ריצה, או כדי לאפשר אופטימיזציית זנב (עליה בהמשך הפרק). מקטינים אותה כדי שהשרשרת תגיע למקרה הבסיס ותיעצר. זו שאלה של נכונות.
  • מונה גלובלי שעוצר אחרי 50 הפעלות הוא תנאי עצירה לגיטימי. העצירה לא תלויה בקלט, והתוצאה נחתכת באמצע החישוב.
בדקו את עצמכם
המתודה static String repeat(String s, int k) { if (k == 0) return ""; return s + repeat(s, k); } אמורה לשרשר את s לעצמו k פעמים. מה יקרה ב-repeat("ab", 3), ואיך מתקנים?

k עובר הלאה בלי שינוי, ולכן k == 0 לא יתקיים אף פעם והריצה תסתיים ב-StackOverflowError. התיקון הוא repeat(s, k - 1), ואז מתקבל ababab.

במתודה מסוימת הבדיקה if (n == 1) return 5; כתובה רק אחרי השורה int r = f(n - 1);. למה היא אף פעם לא נעצרת?

כי f(n - 1) יוצאת עוד לפני שהבדיקה רצה, וכך כל הפעלה שולחת הפעלה נוספת בלי לבדוק אם הגיעה לסוף. מעבירים את הבדיקה אל לפני הקריאה.

חזרה לתוכן העניינים

מחסנית הקריאות: מסגרות, עומק והגבול שלו

כדי לנמק מה רקורסיה עושה צריך תמונה של מחסנית הקריאות (call stack). זה אזור זיכרון שכל thread מקבל לעצמו, ושבו רשומה כל קריאה שעדיין לא הסתיימה.

דמיינו ערימת פתקים על שולחן. מי שמתחיל משימה כותב פתק ומניח אותו למעלה; מי שגומר זורק את הפתק העליון וחוזר לזה שמתחתיו, בדיוק לשורה שבה עצר. ככה עובדת המחסנית, והפתק נקרא מסגרת (stack frame).

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

Java
public class Frames {
    static int layers(int n) {
        int mine = n * 100;                  // a local variable of this frame only
        if (n == 0) return mine;
        int below = layers(n - 1);           // execution resumes here when the deeper call returns
        System.out.println("n=" + n + " mine=" + mine + " below=" + below);
        return mine + below;
    }

    public static void main(String[] args) {
        System.out.println("total = " + layers(3));
    }
}
פלט
n=1 mine=100 below=0
n=2 mine=200 below=100
n=3 mine=300 below=300
total = 600

בשורה של n=3 מודפס mine=300, למרות ששלוש הפעלות עמוקות יותר הגדירו בינתיים משתנה בשם mine משלהן. אף אחת לא דרסה אותו, כי כל אחת כתבה על פתק אחר.

וכמה פתקים היו על השולחן ברגע השיא? ארבעה, של n=3 עד n=0, וכולם תפוסים עד ש-n=0 מסיימת. כל רמה נוספת מוסיפה פתק, ולכן הזיכרון שהרקורסיה תופסת במחסנית הוא O(depth).

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

סביבהכמה מקום ישכשהמקום נגמר
Javaנקבע פעם אחת, כשה-thread נוצר, לפי -Xss. במערכות 64 סיביות זה בדרך כלל 1 MBנזרקת StackOverflowError, שהיא Error ולא Exception
C# / .NETב-Windows, 1 MB ל-thread הראשינוצרת StackOverflowException, שאי אפשר לתפוס, והתהליך כולו נסגר
Python (CPython)הגבול נמדד ברמות: 1000 כברירת מחדלנזרקת RecursionError

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

ההצעהלמה העומק לא משתנה
להריץ עם -Xmx גדולהדגל קובע את גודל הערימה (Heap), שבה יושבים אובייקטים. את המחסנית מגדילים עם -Xss
לקרוא ל-System.gc()איסוף הזבל מנקה אובייקטים בערימה. מסגרות של הפעלות פתוחות אינן זבל, והוא לא נוגע בהן
לסמן את הפרמטר finalfinal רק אוסר להשים לפרמטר ערך חדש
להגדיר את המתודה staticגם מתודה סטטית מקבלת מסגרת בכל הפעלה, בדיוק באותו אופן
להחליף int ב-short או ב-longמספר ההפעלות לא משתנה, ולכן גם העומק לא
לפצל לשתי מתודות שמפעילות זו את זוהמחסנית שייכת ל-thread ולא למתודה, ושתיהן נערמות על אותה מחסנית
תרחיש 7: המחסנית של חזקה, מסגרת אחר מסגרת

המתודה pow(b, e) מחזירה 1 כש-e שווה 0, ואחרת מחזירה b * pow(b, e - 1). מה קורה במחסנית בקריאה pow(2, 3)?

  1. main מפעילה את pow(2, 3). נוספת מסגרת עם e = 3, והיא נעצרת באמצע הביטוי, כי הכפל צריך את התשובה של pow(2, 2).
  2. באותה צורה נוספות מסגרות עם e = 2, e = 1 ולבסוף e = 0. ברגע השיא יש מעל main ארבע מסגרות של pow, וכל אחת מחזיקה e משלה.
  3. המסגרת של e = 0 פוגשת את מקרה הבסיס, מחזירה 1 ויורדת מהמחסנית.
  4. המסגרת של e = 1 ממשיכה מאמצע הביטוי, מחשבת 2 * 1 = 2 ויורדת. אחריה e = 2 מחשבת 2 * 2 = 4, ו-e = 3 מחשבת 2 * 4 = 8.

כל הכפל קרה בשלב החזרה: כל מסגרת קיבלה את התשובה מזו שמעליה והשלימה את הביטוי שלה. בקריאה pow(1, 500000) היו צריכות להיות פתוחות חצי מיליון מסגרות בבת אחת, ובמחסנית בגודל ברירת המחדל זה נגמר ב-StackOverflowError.

טעויות נפוצות
  • ה-JVM מרחיבה את המחסנית כשהיא מתמלאת, ולכן רק הזיכרון הפנוי מגביל את העומק. הגודל קבוע מרגע יצירת ה-thread, לפי -Xss.
  • אם תקצו לתוכנית יותר זיכרון עם -Xmx, הקריאות העמוקות ייכנסו. -Xmx שייך לערימה. מחסנית הקריאות לא גדלה ממנו.
  • System.gc() מפנה מסגרות ישנות מהמחסנית. המסגרות של הפעלות פתוחות עדיין בשימוש, ואיסוף הזבל עוסק בערימה בלבד.
  • ה-JVM זוכרת תוצאות של הפעלות שכבר חושבו ומדלגת עליהן. אין שמירת תוצאות אוטומטית. אם רוצים אותה, כותבים Memoization בעצמכם.
  • כשהעומק גדול, הסביבה מעבירה את ההמשך ל-thread חדש עם מחסנית נקייה. זה לא קורה, לא ב-Java ולא ב-Python.
  • רקורסיה הדדית מחלקת את העומק בין שתי מחסניות, אחת לכל מתודה. יש מחסנית אחת לכל thread, וכל המסגרות של שתי המתודות נערמות עליה.
בדקו את עצמכם
שירות ב-Java נופל עם StackOverflowError. מישהו מציע להריץ עם -Xmx16g ולהוסיף System.gc() לפני כל הפעלה. מה תענו?

שתי ההצעות עוסקות בערימה, לא במחסנית, ולכן העומק המרבי לא ישתנה. -Xss כן מגדיל את המחסנית, אבל רק דוחה את הנפילה לקלט גדול יותר; הפתרון היסודי הוא לולאה.

תוכנית C# נכנסת לרקורסיה עמוקה מדי, ומתכנתת עוטפת את הקריאה ב-catch (StackOverflowException). מה יקרה?

ה-catch לא יעזור: ב-.NET את החריגה הזו אי אפשר לתפוס, והתהליך כולו מסתיים.

חזרה לתוכן העניינים

מעקב אחרי קוד רקורסיבי: מה יופיע בפלט

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

  • הדפסה לפני הקריאה רצה בדרך פנימה, בזמן שהשרשרת מעמיקה. הסדר הוא מההפעלה החיצונית אל הפנימית.
  • הדפסה אחרי הקריאה מחכה עד שההפעלה הפנימית מסיימת. היא רצה בדרך חזרה, ולכן הסדר מתהפך.
Java
public class Trace {
    static void say(int v) { System.out.print(v + " "); }

    static void down(int k) {
        if (k < 1) return;
        say(k);            // runs on the way in
        down(k - 1);
    }

    static void up(int k) {
        if (k < 1) return;
        up(k - 1);
        say(k);            // runs on the way out
    }

    static void mirror(int k) {
        if (k < 1) return;
        say(k);
        mirror(k - 1);
        say(k);
    }

    public static void main(String[] args) {
        down(4);   System.out.println();
        up(4);     System.out.println();
        mirror(4); System.out.println();
    }
}
פלט
4 3 2 1 
1 2 3 4 
4 3 2 1 1 2 3 4 

עקבו אחרי up(4). היא מפעילה את up(3) עוד לפני שהדפיסה משהו, זו מפעילה את up(2), וכך עד up(0), שנתקלת ב-k < 1 וחוזרת בלי לעשות דבר.

רק כש-up(0) חוזרת, up(1) מקבלת שוב שליטה, והשורה הבאה שלה היא say(k): היא כותבת 1 ומסיימת, ואז מגיע תורה של up(2) להגיע לאותה שורה. ל-0 אין רגע כזה, כי אצל up(0) ה-return קודם ל-say.

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

הפעלהמדפיסה בכניסהמדפיסה ביציאה
mirror(4)4, ראשון בפלט4, אחרון בפלט
mirror(3)33
mirror(2)22
mirror(1)11, פותח את החצי השני
mirror(0)כלום, יוצאת מידאין

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

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

Java
public class DigitSum {
    static int digitSum(int x) {
        if (x < 10) return x;                 // a single digit is its own sum
        return x % 10 + digitSum(x / 10);     // last digit + digit sum of the rest
    }

    public static void main(String[] args) {
        System.out.println(digitSum(9075) + " " + digitSum(58));
    }
}
פלט
21 13

הקוד נשען על שני אופרטורים של חשבון שלמים: השארית בחלוקה ב-10 מחלצת את ספרת האחדות, והמנה של חלוקה ב-10 משאירה את כל מה שמשמאלה. למשל, מ-907 מתקבלים 7 ו-90.

פתיחת הביטוי עבור 9075: digitSum(9075) = 5 + digitSum(907) = 5 + 7 + digitSum(90) = 5 + 7 + 0 + digitSum(9). את 9 מחזיר מקרה הבסיס, והסכום הוא 21.

תרחיש 8: ביטוי שמפרק מספר ומרכיב אותו מחדש
Java
public class DropZeros {
    static int dropZeros(int x) {
        if (x < 10) return x;
        int last = x % 10;                    // keep the last digit
        int rest = dropZeros(x / 10);         // rebuild everything before it
        return last == 0 ? rest : rest * 10 + last;
    }

    public static void main(String[] args) {
        System.out.println(dropZeros(4050));
    }
}
פלט
45

נעקוב אחרי dropZeros(4050). כל הפעלה שומרת את הספרה האחרונה ב-last, ושולחת את שאר המספר פנימה:

  1. dropZeros(4050): last = 0, ממתינה ל-dropZeros(405).
  2. dropZeros(405): last = 5, ממתינה ל-dropZeros(40).
  3. dropZeros(40): last = 0, ממתינה ל-dropZeros(4).
  4. dropZeros(4): 4 קטן מ-10, ומקרה הבסיס מחזיר 4.

בדרך חזרה, dropZeros(40) רואה את הספרה 0 ומחזירה את rest כמו שהוא, כלומר 4, ואילו dropZeros(405) מצרפת את הספרה 5 ומחשבת 4 * 10 + 5, כלומר 45. ב-dropZeros(4050) הספרה שוב 0, ולכן התשובה הסופית נשארת 45.

המתודה מרכיבה את הספרות מחדש בסדר המקורי ומשמיטה את האפסים. ההרכבה קורית רק בשלב החזרה, ולכן בלי פתיחה מסודרת קל להפוך את הסדר בטעות.

טעויות נפוצות
  • mirror(3) מדפיסה את הרצף היורד פעמיים: קודם 3 2 1 ואז שוב 3 2 1. ביציאה כל הפעלה מדפיסה את ה-k שלה, והעמוקה מסיימת ראשונה. לכן החצי השני עולה: 1, 2, 3.
  • גם 0 מופיע בפלט, כי גם mirror(0) מופעלת. היא מופעלת, אבל מקרה הבסיס מחזיר לפני שורת ההדפסה.
  • הדפסה שכתובה אחרי הקריאה העצמית יוצאת בסדר יורד. הסדר היורד שייך להדפסה שלפני הקריאה. הדפסה אחרי הקריאה רצה בשלב החזרה ויוצאת בסדר עולה.
  • digitSum(9075) מחזירה 5, או את מכפלת הספרות, או את 907 + 90 + 9. 5 יוצא אם מתעלמים מההפעלה הרקורסיבית, מכפלה אם מחליפים את החיבור בכפל, ו-1006 אם מחברים את המספרים המקוצרים במקום הספרות. התשובה הנכונה היא 21.
בדקו את עצמכם
מה יודפס בקריאה g(7) עבור static void g(int n) { if (n <= 0) return; g(n - 3); System.out.print(n + ","); }?

הפלט הוא 1,4,7,. ההפעלות הן g(7), g(4), g(1) ו-g(-2). האחרונה יוצאת בלי להדפיס, ובדרך חזרה מודפסים 1, אחריו 4 ולבסוף 7.

מה מחזירה digitSum(58), וכמה הפעלות היא עושה?

13. ההפעלה הראשונה מחשבת 8 ועוד digitSum(5), והשנייה היא מקרה הבסיס ומחזירה 5. סך הכול שתי הפעלות.

חזרה לתוכן העניינים

סוגי רקורסיה, והמחיר של חישוב שחוזר על עצמו

ממיינים רקורסיות לפי שתי שאלות: כמה פעמים המתודה מפעילה את עצמה בכל הרצה, והאם ההפעלה עוברת דרך מתודה אחרת.

סוגסימן היכרדוגמה
רקורסיה לינארית (linear recursion)הפעלה עצמית אחת בכל קריאה. הקריאות יוצרות שרשרת ישרה, בלי פיצוליםעצרת, digitSum
רקורסיה כפולה, או עץ קריאותשתי הפעלות עצמיות או יותר בכל קריאה, ולכן כל קריאה מתפצלתפיבונאצ'י הנאיבי, ספירת המדרגות
רקורסיה הדדית או עקיפה (mutual, indirect)A מפעילה את B, ו-B מפעילה חזרה את AisEven(n) שמפעילה את isOdd(n - 1), וההפך
רקורסיית זנב (tail recursion)ההפעלה העצמית היא הצעד האחרון, ושום חישוב לא מחכה לתוצאה שלהחזקה עם צובר, בתת-הפרק הבא

ברקורסיה כפולה האויב הוא עבודה שחוזרת על עצמה: שני ענפים שונים בעץ מגיעים לאותה תת-בעיה, וכל אחד פותר אותה מאפס. כך זה נראה בפיבונאצ'י הנאיבי:

Java
static int fibNaive(int n) {
    if (n < 2) return n;                        // two base cases in one test: 0 and 1
    return fibNaive(n - 1) + fibNaive(n - 2);   // two self-calls: the calls branch
}

זה עץ ההפעלות של fibNaive(5), כשכל שורה היא הפעלה אחת:

Text
fib(5)
+- fib(4)
|  +- fib(3)
|  |  +- fib(2)
|  |  |  +- fib(1)
|  |  |  +- fib(0)
|  |  +- fib(1)
|  +- fib(2)
|     +- fib(1)
|     +- fib(0)
+- fib(3)
   +- fib(2)
   |  +- fib(1)
   |  +- fib(0)
   +- fib(1)

ספירה: fib(5) ו-fib(4) מופיעות פעם אחת כל אחת, fib(3) פעמיים, fib(2) שלוש פעמים, fib(1) חמש פעמים ו-fib(0) שלוש פעמים. יחד 15 הפעלות, כולל הראשונה.

החלק העליון של הציור הוא תת-העץ של fib(4), ויש בו 9 הפעלות כולל fib(4) עצמה. fib(3) מחושבת בו פעם אחת, אבל בעץ המלא היא מחושבת פעמיים, כי לכל ענף אין מושג מה הענף השני כבר מצא.

כמה מהר זה גדל? הוספנו מונה הפעלות והרצנו:

Java
public class FibCount {
    static long calls = 0;

    static int fibNaive(int k) {
        calls++;
        if (k < 2) return k;
        return fibNaive(k - 1) + fibNaive(k - 2);
    }

    static long[] memo = new long[100];
    static long memoCalls = 0;

    static long fibMemo(int k) {
        memoCalls++;
        if (k < 2) return k;
        if (memo[k] != 0) return memo[k];              // already computed: reuse it
        memo[k] = fibMemo(k - 1) + fibMemo(k - 2);
        return memo[k];
    }

    public static void main(String[] args) {
        for (int n : new int[] {5, 12, 25, 40}) {
            calls = 0;
            int r = fibNaive(n);
            System.out.println("fib(" + n + ") = " + r + ", calls = " + calls);
        }
        System.out.println("memo: fib(40) = " + fibMemo(40) + ", calls = " + memoCalls);
    }
}
פלט
fib(5) = 5, calls = 15
fib(12) = 144, calls = 465
fib(25) = 75025, calls = 242785
fib(40) = 102334155, calls = 331160281
memo: fib(40) = 102334155, calls = 79

הגרסה הנאיבית צריכה יותר מ-331 מיליון הפעלות עבור 40, ומספר ההפעלות גדל מעריכית עם n. עם Memoization אותה תשובה מגיעה אחרי 79 הפעלות, כי כל ערך נשמר במערך בפעם הראשונה ומשם רק נשלף.

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

  • fibNaive(40) לא מתקרבת לגבול המחסנית. בכל רגע פתוחות לכל היותר 40 מסגרות, אחת לכל רמה בעץ, וכל ענף נסגר במקרה בסיס.
  • אין ריבוי threads. ההפעלות מתבצעות בתור, אחת אחרי השנייה, על ה-thread של main.
  • אין העתקה של המחסנית. כל הפעלה מוסיפה רק את המסגרת הקטנה שלה.
  • אין ArithmeticException. 102334155 קטן מהמקסימום של int, ו-Java ממילא לא זורקת חריגה על גלישה בחשבון int: הערך מתהפך בשקט.

הבעיה היא זמן ריצה בלבד. שתי דרכים הופכות את העבודה ללינארית, O(n): Memoization, שראיתם בפלט למעלה, או לולאה שבונה את הסדרה מלמטה עם שני משתנים:

Java
public class FibLoop {
    static long fibLoop(int n) {
        long prev = 0, cur = 1;                 // fib(0), fib(1)
        for (int step = 1; step <= n; step++) {
            long next = prev + cur;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        System.out.println(fibLoop(12) + " " + fibLoop(40));
    }
}
פלט
144 102334155

עוד אלגוריתמים רקורסיביים שכדאי להכיר, ומה הם עולים:

  • חיפוש בינארי רקורסיבי: כל הפעלה זורקת חצי מהטווח, ולכן O(log n) הפעלות.
  • מגדלי האנוי (Towers of Hanoi): מספר המהלכים המינימלי הוא 2^n - 1, כש-n הוא מספר הדיסקיות.
  • מיון מיזוג (merge sort), סריקה של עץ, ו-GCD לפי אוקלידס.
Java
public class Classics {
    public static void main(String[] args) {
        int[] sorted = {4, 9, 15, 23, 42, 57, 80};
        System.out.println(find(sorted, 57, 0, sorted.length - 1) + " " + find(sorted, 10, 0, sorted.length - 1));
        System.out.println(hanoiMoves(3) + " " + hanoiMoves(10));
    }

    // index of key in sorted[lo..hi], or -1; every call keeps only half of the range
    static int find(int[] sorted, int key, int lo, int hi) {
        if (lo > hi) return -1;                          // base case: empty range
        int mid = (lo + hi) / 2;
        if (sorted[mid] == key) return mid;              // base case: found
        if (key < sorted[mid]) return find(sorted, key, lo, mid - 1);
        return find(sorted, key, mid + 1, hi);
    }

    static long hanoiMoves(int discs) {
        if (discs == 0) return 0;
        // move discs-1 aside, move the largest, move discs-1 back on top
        return hanoiMoves(discs - 1) + 1 + hanoiMoves(discs - 1);
    }
}
פלט
5 -1
7 1023

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

Java
public class TreeSearch {
    static class Node {
        int value; Node left, right;
        Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; }
    }

    static boolean hasNegative(Node t) {
        if (t == null) return false;                      // base case: empty subtree
        if (t.value < 0) return true;                     // base case: found one
        return hasNegative(t.left) || hasNegative(t.right);
    }

    public static void main(String[] args) {
        Node tree = new Node(8,
                new Node(3, null, new Node(-6, null, null)),
                new Node(11, null, null));
        System.out.println(hasNegative(tree) + " " + hasNegative(tree.right));
    }
}
פלט
true false

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

בזיכרון היא אפילו מחזיקה מסגרת לכל רמה פתוחה של העץ. ושימו לב לשורה t == null: גם בעץ של שלושה צמתים כמו בדוגמה, בלעדיה ההפעלה על ילד חסר הייתה נופלת עם NullPointerException.

תרחיש 9: שלושה חשודים בתוכנית ש"נתקעת"

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

  1. גלישת int? לא. 102334155 נכנס בטווח, וגם אילו לא היה נכנס, Java לא הייתה זורקת בגלל זה חריגה.
  2. גלישת מחסנית? לא. העומק המרבי הוא 40 מסגרות, והתוכנית בכלל לא נופלת. היא רק איטית.
  3. חישוב חוזר? כן. אותם ערכים נפתרים שוב ושוב בענפים שונים, ומצטברים ליותר מ-331 מיליון הפעלות.

הוספת מערך Memoization מורידה את המספר ל-79 הפעלות, והתשובה מתקבלת מיד.

טעויות נפוצות
  • fib(4) מפעילה את עצמה 4 פעמים, פעם אחת לכל ערך של n. ערכים חוזרים בענפים שונים, והמספר הוא 9. מי שמקבל 8 שכח את ההפעלה הראשונה, ו-15 שייך ל-fib(5).
  • מתודה שמפעילה את עצמה פעם אחת בכל קריאה היא רקורסיה הדדית או עקיפה. זו רקורסיה לינארית. הדדית ועקיפה פירושן שההפעלה עוברת דרך מתודה אחרת.
  • fib(40) איטית כי היא פותחת threads, גולשת מהמחסנית או נופלת על ArithmeticException. אף אחד מאלה. הבעיה היא מספר הפעלות שגדל מעריכית.
  • חיפוש רקורסיבי בעץ מהיר יותר מלולאה, או צורך פחות זיכרון. היתרון הוא התאמה למבנה העץ ובהירות הקוד, לא ביצועים.
  • בעץ קטן מספיק אפשר לוותר על מקרה בסיס. בלי בדיקת null ההפעלה על ילד שלא קיים תיכשל. מקרה בסיס נדרש בכל גודל.
בדקו את עצמכם
בעץ ההפעלות של fib(5), כמה פעמים מופעלת fib(1)?

חמש פעמים: שלוש מתוך הענף של fib(4) ושתיים מתוך הענף של fib(3).

כמה הפעלות בסך הכול עושה fibNaive(6), כולל הראשונה?

25: ההפעלה עצמה, 15 מהענף של fib(5) ועוד 9 מהענף של fib(4).

isEven מפעילה את isOdd, ו-isOdd מפעילה את isEven. איזה סוג רקורסיה זה, והאם זה מוסיף עומק אפשרי?

רקורסיה הדדית, כלומר עקיפה. היא לא מוסיפה עומק: שתי המתודות נערמות על אותה מחסנית של אותו thread.

חזרה לתוכן העניינים

רקורסיית זנב (Tail Recursion), ומי באמת מנצל אותה

שאלו על כל הפעלה עצמית: כשהיא חוזרת עם ערך, מה המתודה עושה איתו? אם התשובה היא שהיא מעבירה אותו החוצה כמו שהוא ולא נוגעת בו, זו קריאת זנב, ומתודה שכל ההפעלות העצמיות שלה כאלה היא רקורסיית זנב (Tail Recursion).

מיקום הקריאה בקוד לא מכריע. גם קריאה בשורה האחרונה של המתודה אינה בזנב אם כפל, חיבור או השוואה ממתינים לתוצאה שלה.

Java
public class Power {
    // not tail recursive: the multiplication waits for the call to return
    static long pow(long b, int e) {
        if (e == 0) return 1;
        return b * pow(b, e - 1);
    }

    // tail recursive: the partial product travels in acc
    static long powTail(long b, int e, long acc) {
        if (e == 0) return acc;
        return powTail(b, e - 1, acc * b);
    }

    public static void main(String[] args) {
        System.out.println(pow(3, 4) + " " + powTail(3, 4, 1));
    }
}
פלט
81 81

הפעילו את השאלה על שתי המתודות. ב-pow, מה שחוזר מ-pow(b, e - 1) עוד צריך לעבור הכפלה ב-b, ולכן זו לא קריאת זנב. ב-powTail הערך החוזר יוצא החוצה ישר, כי את ההכפלה כבר ביצע הארגומנט acc * b, שחושב לפני שהקריאה יצאה.

מאותה דוגמה יוצאות עוד שתי מסקנות. pow קוראת לעצמה פעם אחת בלבד, כלומר היא לינארית, ובכל זאת אינה זנבית, כך שאין לבלבל בין שתי התכונות. ול-powTail יש שורת e == 0 משלה, כי גם רקורסיית זנב לא נעצרת בלי מקרה בסיס.

מה זה נותן בפועל? במסגרת של powTail אין שום דבר לשמור אחרי שהקריאה יוצאת, ולכן מהדר או סביבת ריצה יכולים למחזר אותה במקום לערום מסגרת חדשה. לטכניקה קוראים Tail Call Optimization, או tail call elimination, והתוצאה היא רקורסיה שתופסת מסגרת אחת, כאילו נכתבה כלולאה.

האם Java, C# ו-Python עושות את זה? בקצרה: לא, לא בהבטחה, ולא.

שפהאופטימיזציית זנב
Javaלא קיימת בשום שלב: לא בקומפילציה של javac, לא בפירוש בתוך ה-JVM ולא בקומפילציית ה-JIT. סוג המתודה (private, final, static) לא משנה דבר
C#בלי הבטחה: לפעמים ה-JIT של .NET ממחזר מסגרת כזו ולפעמים לא, ולכן כותבים קוד כאילו אין
Python (CPython)לא קיימת. ברירת המחדל מרשה 1000 רמות, מעבר לכך נזרקת RecursionError, ו-sys.setrecursionlimit מזיז את הגבול

אפשר לבדוק את זה ב-Java בעצמכם. כאן שלוש גרסאות סופרות כמה כפולות של 3 יש בין 1 ל-3,000,000:

Java
public class NoTco {
    // how many numbers in 1..m are multiples of 3
    static long plain(long m) { if (m < 1) return 0; return (m % 3 == 0 ? 1 : 0) + plain(m - 1); }
    static long tail(long m, long found) { if (m < 1) return found; return tail(m - 1, found + (m % 3 == 0 ? 1 : 0)); }
    static long loop(long m) { long found = 0; for (long i = 1; i <= m; i++) if (i % 3 == 0) found++; return found; }

    public static void main(String[] args) {
        long m = 3_000_000;
        System.out.println("loop  -> " + loop(m));
        try { System.out.println("tail  -> " + tail(m, 0)); }
        catch (StackOverflowError e) { System.out.println("tail  -> StackOverflowError"); }
        try { System.out.println("plain -> " + plain(m)); }
        catch (StackOverflowError e) { System.out.println("plain -> StackOverflowError"); }
    }
}
פלט
loop  -> 1000000
tail  -> StackOverflowError
plain -> StackOverflowError

אילו ה-JVM היה ממחזר מסגרות, השורה של tail הייתה מדפיסה 1000000 כמו הלולאה. היא מדפיסה StackOverflowError, בדיוק כמו plain. גם ב-CPython קריאת זנב לא מצילה (נוסח ההודעה של RecursionError משתנה מעט בין גרסאות; בגרסאות ישנות יותר נוספות לו המילים in comparison):

Python
import sys

def count_tail(n, acc=0):
    if n == 0:
        return acc
    return count_tail(n - 1, acc + 1)   # a tail call, yet CPython still adds a frame

print(sys.getrecursionlimit())
print(count_tail(900))
try:
    count_tail(50_000)
except RecursionError as e:
    print("RecursionError:", e)

sys.setrecursionlimit(6000)
print(count_tail(5000))
פלט
1000
900
RecursionError: maximum recursion depth exceeded
5000

לכן, כשקלט ב-Java או ב-C# עלול לייצר שרשרת של מאות אלפי הפעלות, הדרך הבטוחה היא לולאה, כמו בשורה הראשונה של הפלט. צובר וקריאת זנב הם שם סגנון כתיבה, לא הגנה על המחסנית.

תרחיש 10: איזו שורה היא קריאת זנב

כמה מתודות עוברות על רשימה מקושרת. בכל שורה שאלו שאלה אחת: מה קורה לערך שחוזר מהקריאה?

שורהזנב?מה נשאר אחרי הקריאה
return walk(node.next, steps + 1);כןכלום, התוצאה עוברת הלאה כמו שהיא
return walk(node.next) + 1;לאחיבור של 1
walk(node.next, steps); return steps;לאמוחזר ערך אחר, ולכן הקריאה איננה הפעולה האחרונה
return 3 * walk(node.next);לאכפל ב-3
return Math.max(node.value, best(node.next));לאההשוואה בתוך Math.max

הכלל: אם הערך שהקריאה מחזירה הוא בדיוק הערך שהמתודה מחזירה, זו קריאת זנב.

טעויות נפוצות
  • בקריאת זנב ההפעלה העצמית היא הפעולה הראשונה במתודה. היא האחרונה. אחריה לא נשאר שום חישוב.
  • return n * f(n - 1); היא קריאת זנב, כי היא כתובה בשורה האחרונה. הכפל מתבצע אחרי שהקריאה חוזרת. המיקום בקוד לא קובע.
  • כל רקורסיה עם הפעלה עצמית אחת היא זנבית. pow ועצרת הרגילה מפעילות את עצמן פעם אחת ואינן זנביות.
  • ברקורסיית זנב אין צורך בתנאי עצירה, או שהוא חייב להיות מורכב משני תנאים. תנאי העצירה נדרש כרגיל, וצורתו לא קשורה להגדרה של זנב.
  • Java הופכת קריאת זנב ללולאה, לפחות במתודות private או final, או אחרי שה-JIT מקמפל אותן. Java לא עושה זאת באף אחד מהמקרים.
  • CPython ממיר רקורסיה ללולאה, ומטמון המעבד הופך אותה למהירה מלולאה. כל הפעלה מוסיפה מסגרת, ובעומק גדול נזרקת RecursionError.
בדקו את עצמכם
האם static int maxFrom(int[] a, int i) { if (i == a.length - 1) return a[i]; return Math.max(a[i], maxFrom(a, i + 1)); } היא רקורסיית זנב? ואם תוסיפו לה צובר, האם ב-Java היא תעבור מערך של שמונה מיליון איברים?

היא לא זנבית, כי Math.max רצה אחרי שהקריאה חוזרת. גם עם צובר היא תיפול ב-StackOverflowError, כי Java לא מבצעת אופטימיזציית זנב; רק לולאה תעבור.

ב-Python מגדילים את הגבול עם sys.setrecursionlimit(6000). האם עכשיו הרקורסיה בטוחה לכל קלט?

לא. הגבול רק זז, כמו -Xss ב-Java, וקלט עמוק יותר ייתקל בו שוב.

חזרה לתוכן העניינים

מרקורסיה ללולאה

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

מה הציל את loop? הגוף שלה רץ שלושה מיליון פעמים בתוך מסגרת אחת. i ו-found מקבלים ערכים חדשים בכל סבב, אבל שום מסגרת לא נוספת, כך שהמחסנית נראית אותו דבר בסבב הראשון ובאחרון.

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

מצבאיך ממירים
רקורסיה לינאריתהפרמטרים הופכים למשתני לולאה, מקרה הבסיס הופך לתנאי היציאה, והצעד הרקורסיבי הופך לעדכון של המשתנים בכל סבב
רקורסיה מסתעפת (עץ, גרף)מחזיקים אוסף של עבודות ממתינות, למשל ArrayDeque שמשמש כמחסנית. הוא אובייקט בערימה, שגדולה בהרבה ממחסנית הקריאות, ולכן -Xss כבר לא מגביל את העומק
Java
import java.util.ArrayDeque;
import java.util.Deque;

public class ExplicitStack {
    static class Node {
        int value; Node left, right;
        Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; }
    }

    static boolean hasNegative(Node t) {
        if (t == null) return false;
        if (t.value < 0) return true;
        return hasNegative(t.left) || hasNegative(t.right);
    }

    static boolean hasNegativeLoop(Node root) {
        Deque<Node> pending = new ArrayDeque<>();      // our own stack, allocated on the heap
        if (root != null) pending.push(root);
        while (!pending.isEmpty()) {
            Node t = pending.pop();
            if (t.value < 0) return true;
            if (t.left != null) pending.push(t.left);
            if (t.right != null) pending.push(t.right);
        }
        return false;
    }

    public static void main(String[] args) {
        // a lopsided tree: 2,000,000 nodes, each one the left child of the next
        Node chain = new Node(-1, null, null);
        for (int i = 0; i < 2_000_000; i++) chain = new Node(i, chain, null);

        System.out.println("loop: " + hasNegativeLoop(chain));
        try { System.out.println("recursion: " + hasNegative(chain)); }
        catch (StackOverflowError e) { System.out.println("recursion: StackOverflowError"); }
    }
}
פלט
loop: true
recursion: StackOverflowError

העץ כאן הוא בעצם שרשרת: כל צומת הוא הילד השמאלי של הבא אחריו, ולכן העומק שווה למספר הצמתים, שני מיליון. הגרסה עם ArrayDeque מגיעה לערך השלילי שבתחתית, והגרסה הרקורסיבית נופלת בדרך.

כמה תיקונים נראים מפתים, אבל אף אחד מהם לא פותר את הבעיה מיסודה:

הצעהלמה היא לא מספיקה
לתפוס StackOverflowError ולנסות שובהקלט לא השתנה, ולכן הניסיון השני יגיע לאותו עומק וייפול שוב
לתפוס ולהמשיך מהנקודה שבה נפלאין לאן לחזור: המסגרות כבר נפרקו כשהשגיאה עלתה למעלה
להגדיל את המחסנית עם -Xssהגבול זז רחוק יותר אבל נשאר קיים, וקלט גדול יותר יגיע אליו
Memoizationחוסכת חישובים שחוזרים על עצמם, אבל שרשרת הפעלות ארוכה נשארת ארוכה באותה מידה
לנסח את הקריאה כקריאת זנבב-Java אין לזה שום השפעה
-Xmx, System.gc(), final, static, או טיפוס אחר לפרמטראף אחד מהם לא משנה כמה מסגרות פתוחות בבת אחת
תרחיש 11: היסטוריה של שלושה מיליון גרסאות

מערכת לניהול מסמכים שומרת כל גרסה עם הפניה לגרסה הקודמת. מתודה רקורסיבית ב-Java סופרת את הגרסאות: הפעלה אחת לכל גרסה, ועצירה כשההפניה היא null.

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

הצוות מחפש פתרון שלא תלוי בכמה מחסנית הוקצתה. התשובה היא לולאה שבה משתנה אחד צועד אחורה בהיסטוריה:

Java
static long countVersions(Version v) {
    long count = 0;
    while (v != null) {      // the old base case is now the exit condition
        count++;
        v = v.previous;      // the old recursive step is now an update
    }
    return count;
}

בכל סבב מתעדכנים משתנים מקומיים של אותה מסגרת, ולכן גם שלושה מיליון גרסאות לא מוסיפות אף מסגרת למחסנית.

טעויות נפוצות
  • עוטפים את הקריאה ב-try/catch ומריצים שוב עד שזה מצליח. אותו קלט, אותו עומק, אותה שגיאה בכל ניסיון.
  • ערך גדול מספיק ל--Xss פותר את הבעיה לתמיד. הוא רק מרחיק את הגבול. קלט גדול יותר יגיע אליו.
  • שמירת תוצאות ביניים מקצרת את שרשרת ההפעלות. היא חוסכת חישובים חוזרים, לא עומק.
  • חלוקה לשתי מתודות שמפעילות זו את זו מכפילה את המקום הפנוי. שתיהן משתמשות באותה מחסנית של אותו thread.
בדקו את עצמכם
תארו במילים איך תכתבו את powTail(b, e, acc) מתת-הפרק הקודם כלולאה.

מתחילים מ-acc שהתקבל (בדרך כלל 1). כל עוד e גדול מ-0, כופלים את acc ב-b ומורידים את e באחד, ובסוף מחזירים את acc. מקרה הבסיס e == 0 הפך לתנאי היציאה, והארגומנטים החדשים של הקריאה הפכו להשמות.

למה מחסנית מפורשת מסוג ArrayDeque לא נתקלת בגבול של -Xss?

כי היא אובייקט רגיל שיושב בערימה. מחסנית הקריאות מחזיקה רק את המסגרת של המתודה שמריצה את הלולאה.

חזרה לתוכן העניינים

Exception: חריגות וטיפול בתקלות

חריגה מהי, ולמה מטפלים בה

נתחיל מתוכנית קטנה. הפונקציה book מקבלת מספר מושב כטקסט וממירה אותו ל-int, וזה מצליח רק אם הטקסט הוא באמת מספר:

Java
public class SeatDesk {
    static void book(String seatText) {
        try {
            int seat = Integer.parseInt(seatText);   // may throw NumberFormatException
            System.out.println("seat " + seat + " booked");
        } catch (NumberFormatException e) {
            System.out.println("'" + seatText + "' is not a seat number");
        }
    }

    public static void main(String[] argv) {
        book("14");
        book("14B");
        System.out.println("booking desk still open");
    }
}
פלט
seat 14 booked
'14B' is not a seat number
booking desk still open

בקריאה עם 14B ההמרה נכשלה. באותו רגע Java יצרה אובייקט מסוג NumberFormatException, שמחזיק את סוג הבעיה, הודעה ואת רשימת המתודות שהיו פעילות. לאובייקט כזה קוראים חריגה (Exception).

שלושה מקומות בקוד קובעים מה קורה אחרי שחריגה נוצרת:

מילת מפתחהתפקיד שלהמתי הקוד שבה רץ
tryתוחמת את הקוד שעלול להיכשלתמיד, עד הנקודה שבה נזרקה חריגה (אם נזרקה)
catch (Type e)מגיבה לחריגה מטיפוס מסוים: הודעה למשתמש, ניסיון נוסף, כתיבה ליומןרק כשנזרקה בפועל חריגה שמתאימה לטיפוס שלה
finallyקוד שחייב לרוץ בסוף, בהצלחה או בכישלוןבכל יציאה מה-try (נרחיב בהמשך)

בזכות ה-catch, הקלט השגוי לא הפיל את התוכנית: הודפסה הודעה מסודרת, והשורה האחרונה מראה שהדלפק ממשיך לעבוד. זו כל התכלית של Exception Handling: תקלה שעלולה לקרות בזמן ריצה מקבלת תגובה מתוכננת, והתוכנית ממשיכה או נסגרת בכבוד.

אותו מנגנון נכנס לפעולה גם במצבים אחרים, ובהם: קובץ שנמחק לפני שפתחו אותו, הפעלת מתודה על הפניה שערכה null, חילוק int באפס, ופנייה לתא שמעבר לסוף המערך.

בשתי השפות כל מחלקות החריגה הן צאצאיות של Exception. ב-Java זה לא ראש העץ: מעל Exception עומדת Throwable, ו-Error היא ילדה נוספת של Throwable, לא של Exception. נחזור לזה בהמשך.

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

סוג הטעותאיך היא נראיתהאם catch יעזור?
תקלה בזמן ריצה (חריגה)int חלקי 0, קובץ חסר, אינדקס מחוץ לטווח, גישה דרך nullכן, זה בדיוק התפקיד שלו
שגיאת קומפילציה (תחביר)סוגר מסולסל חסר, נקודה-פסיק שנשמטה, שם מחלקה עם שגיאת כתיבלא. הקוד לא עובר הידור ולכן אינו רץ בכלל
טעות לוגיתנוסחה לא נכונה, תנאי שנכתב הפוך, לולאה שסופרת לא נכוןלא. אף אחד לא זורק כלום, פשוט יוצאת תוצאה שגויה
אזהרת מהדרAPI שהוצא משימוש (deprecated), import מיותרלא. אזהרה אינה מונעת הרצה ואינה חריגה
שפת C בנויה אחרת: אין בה חריגות, ולכן פונקציה מדווחת על כישלון דרך ערך ההחזרה, בדרך כלל מספר שהקורא אמור לבדוק. ב-Java וב-C# הערוץ לדיווח על כישלון הוא זריקת חריגה, וה-try-catch הוא הצד שמקשיב לו.

שני הרגלים רעים שכדאי להימנע מהם:

  • catch שבולע בשקט. בלוק ריק לא פותר דבר. המצב השבור שגרם לחריגה ממשיך להתקיים, ובדרך כלל מתפוצץ מאוחר יותר, רחוק מהמקור.
  • try סביב כל שורה. הקוד מתנפח ונעשה קשה לקריאה. מקומו של try-catch הוא בנקודה שיודעת מה התגובה הנכונה, למשל לבקש קלט מחדש.
תרחיש 12: ארבע תקלות באפליקציית הזמנות, ומה מהן מגיע ל-catch
  • בקובץ Booking.java חסר סוגר מסולסל בסוף מתודה.
  • קובץ ההגדרות prices.cfg לא נמצא בתיקייה כשהתוכנית מנסה לפתוח אותו.
  • הקוד פונה ל-seats[10] במערך שיש בו 10 תאים בלבד (אינדקסים 0 עד 9).
  • ההנחה מחושבת כ-price * 0.15 במקום price * 0.85, והלקוח מחויב בסכום לא נכון.

רק הפריט השני והשלישי מגיעים ל-catch. הם נכשלים בזמן ריצה, וזורקים FileNotFoundException ו-ArrayIndexOutOfBoundsException.

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

טעויות נפוצות
  • try-catch יתריע על נקודה-פסיק חסרה עוד לפני שהתוכנית מתחילה. בדיקת התחביר היא עבודה של המהדר. try-catch פועל רק על קוד שכבר רץ.
  • כשנזרקת חריגה, מנגנון הטיפול מאתחל את התוכנית ומריץ אותה שוב. שום דבר לא מתחיל מחדש. הביצוע עובר לגוף ה-catch שכתבתם, וממשיך משם.
  • גם ב-Java המוסכמה היא להחזיר מספר שלילי כשפונקציה נכשלת. זו הדרך המקובלת ב-C, שאין בה חריגות. ב-Java וב-C# מדווחים על כישלון בזריקת חריגה.
  • כדי להיות בטוחים, עוטפים כל שורה ב-try משלה. מוסיפים try-catch רק היכן שיודעים איך להגיב. עטיפה גורפת מסתירה תקלות ומקשה על הקריאה.
  • בלוק catch רץ בכל מקרה בסוף ה-try, או לחלופין עוצר את התוכנית ברגע התקלה. catch מופעל רק אם נזרקה חריגה מהטיפוס שלו, ומטרתו לאפשר המשך. הקוד שרץ תמיד הוא finally.
בדקו את עצמכם
פונקציה שמחשבת מס טועה בשיעור המס. מישהו מציע לעטוף אותה ב-try-catch. האם זה יעזור?

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

במה שונה הרגע שבו catch רץ מהרגע שבו finally רץ?

catch רץ רק אם בתוך ה-try נזרקה חריגה שמתאימה לטיפוס שלו. finally רץ בכל יציאה מה-try, גם כשהכול עבר בהצלחה.

חזרה לתוכן העניינים

throw, עלייה במחסנית וחריגה שאיש לא תפס

בדוגמה הבאה main קוראת ל-shipDay, shipDay קוראת ל-packOrder, ו-packOrder קוראת ל-pick, שמנסה לגעת בתא 4 במערך של שני תאים. עקבו אחרי הפלט:

Java
public class Warehouse {
    static int[] stock = {5, 3};
    static int attempts = 0;

    static void pick(int slot) {
        attempts++;                               // a change made before the failure
        stock[slot]--;                            // slot 4 does not exist
        System.out.println("picked slot " + slot);
    }

    static void packOrder() {
        try { pick(4); }
        finally { System.out.println("packOrder: cart released"); }
    }

    static void shipDay() {
        packOrder();
        System.out.println("shipDay: this line is skipped");
    }

    public static void main(String[] argv) {
        try { shipDay(); }
        catch (ArrayIndexOutOfBoundsException e) {
            System.out.println("main caught index " + e.getMessage());
        }
        System.out.println("attempts = " + attempts);
    }
}
פלט
packOrder: cart released
main caught index 4
attempts = 1

ב-pick, ה-JVM זרק ArrayIndexOutOfBoundsException בעצמו, ושורת ההדפסה שאחרי הגישה לא רצה. אותה תוצאה הייתה מתקבלת מ-throw new ... שכתבתם בקוד: לחריגות יש שני מקורות, סביבת הריצה והקוד שלכם, והמנגנון זהה.

ל-pick אין catch, ולכן היא ננטשת והחריגה עוברת למי שקרא לה. packOrder מחזיקה רק finally: הוא מדפיס cart released ביציאה, והחריגה ממשיכה הלאה.

גם shipDay לא תופסת כלום, ולכן השורה שלה מדולגת. רק ב-main נמצא catch שמתאים לטיפוס, והחיפוש נעצר שם.

המהלך הזה, שבו מסגרת אחרי מסגרת מוסרת מהמחסנית עד שמגיעים ל-catch, ובדרך מורצים בלוקי finally, נקרא stack unwinding (פריקת המחסנית).

ועוד פרט מהפלט: המונה attempts הוא 1. הוא עלה לפני הזריקה, ואיש לא החזיר אותו לאחור, כי לחריגה אין Rollback אוטומטי.

ומה קורה כשהחיפוש מגיע לראש המחסנית ואין שם catch? ב-Java מסתיים ה-thread (תהליכון, ובחלק מהטקסטים גם שרשור) שבו נזרקה החריגה. לפני כן מודפסים שם המחלקה של החריגה, ההודעה שלה וה-stack trace (עקבות המחסנית): רשימת המתודות שהיו פתוחות, מהעמוקה ביותר החוצה.

Java
public class Reports {
    static int average(int total, int count) {
        return total / count;
    }

    static void report(int total, int count) {
        System.out.println("report start");
        System.out.println("average: " + average(total, count));
        System.out.println("report end");
    }

    public static void main(String[] argv) {
        report(90, 3);
        report(90, 0);
        System.out.println("all reports done");
    }
}
פלט
report start
average: 30
report end
report start
Exception in thread "main" java.lang.ArithmeticException: / by zero
	at Reports.average(Reports.java:3)
	at Reports.report(Reports.java:8)
	at Reports.main(Reports.java:14)

ה-JVM אינו מטפל בחריגה במקום הקוד ואינו ממשיך לשורה הבאה: all reports done לא הודפס. וכיוון שה-thread שמת הוא ה-thread הראשי, התהליך יצא עם קוד יציאה 1.

כדאי לדייק: ב-Java מת רק ה-thread שבו החריגה לא נתפסה. בדוגמה הבאה thread עזר נופל על null, וה-thread הראשי ממשיך כרגיל (וקוד היציאה של התהליך הוא 0):

Java
public class Workers {
    public static void main(String[] argv) throws InterruptedException {
        Thread worker = new Thread(() -> {
            String code = null;
            System.out.println("worker: length " + code.length());
        }, "worker-1");
        worker.start();
        worker.join();
        System.out.println("main: still running after the worker died");
    }
}
פלט
Exception in thread "worker-1" java.lang.NullPointerException
	at Workers.lambda$main$0(Workers.java:5)
	at java.lang.Thread.run(Thread.java:750)
main: still running after the worker died

ב-.NET הכלל מחמיר יותר: חריגה שלא נתפסה, בכל thread שהוא, מפילה את התהליך כולו. בתוכנית C# מקבילה מודפס Unhandled exception עם פרטי החריגה, והשורה של ה-thread הראשי כבר לא מגיעה.

חלוקה באפס. כאן התשובה תלויה בטיפוס. כששני הצדדים שלמים, גם / וגם % מסרבים לחלק באפס: Java זורקת ArithmeticException ו-C# זורקת DivideByZeroException.

ב-double המצב אחר בשתי השפות. התקן של נקודה צפה מגדיר ערכים מיוחדים לחלוקה כזו, ולכן מתקבלים Infinity, מינוס Infinity, או NaN עבור 0.0 חלקי 0.0, ושום דבר לא נזרק.

Java
public class ZeroDiv {
    public static void main(String[] argv) {
        double ratio = 7.5 / 0;
        double unknown = 0.0 / 0.0;
        System.out.println(ratio + " " + (-3 / 0.0) + " " + unknown);

        try { System.out.println(17 % 0); }
        catch (ArithmeticException e) { System.out.println("int remainder: " + e.getMessage()); }

        try { Integer.parseInt("3,5"); }
        catch (NumberFormatException e) {
            System.out.println(e.getMessage());
            System.out.println("also IllegalArgumentException? " + (e instanceof IllegalArgumentException));
        }
    }
}
פלט
Infinity -Infinity NaN
int remainder: / by zero
For input string: "3,5"
also IllegalArgumentException? true
C#
using System;

class Program
{
    static void Main()
    {
        int zero = 0;
        Console.WriteLine(7.5 / zero);           // floating point: no exception
        try { Console.WriteLine(17 % zero); }
        catch (DivideByZeroException e) { Console.WriteLine("int remainder: " + e.GetType().Name); }
        try { int.Parse("3,5"); }
        catch (FormatException e) { Console.WriteLine("parse: " + e.GetType().Name); }
    }
}
פלט
∞
int remainder: DivideByZeroException
parse: FormatException

גרסאות .NET החדשות מציגות את האינסוף כסימן ∞, אבל זה אותו ערך בדיוק. הטבלה מרכזת את הזוגות שכדאי להכיר בשתי השפות:

מה קרהJavaC#
שלם חולק בשלם שערכו 0ArithmeticExceptionDivideByZeroException
הפעלת מתודה או גישה לשדה דרך nullNullPointerExceptionNullReferenceException
אינדקס שחורג מגבולות המערךArrayIndexOutOfBoundsExceptionIndexOutOfRangeException
המרת אובייקט לטיפוס שאינו מתאים לוClassCastExceptionInvalidCastException
טקסט שאינו מספר הומר למספרNumberFormatException (מ-Integer.parseInt)FormatException (מ-int.Parse)
ערך פסול הועבר כארגומנטIllegalArgumentExceptionArgumentException, ומשפחתה כמו ArgumentNullException

שתי הערות לשורה של המרת הטקסט. ההדפסה true בפלט של Java נובעת מהירושה: NumberFormatException היא מקרה פרטי של IllegalArgumentException, ולכן catch של האב לוכד גם אותה. ואם מופיעה לכם InputMismatchException, היא שייכת לקריאת קלט עם Scanner (nextInt על קלט לא מספרי), ול-Integer.parseInt אין איתה קשר.

תרחיש 13: חריגה שחוצה שתי מתודות עד שמישהו תופס אותה

main קוראת ל-importCsv, זו קוראת ל-parseAmount, ושם Integer.parseInt("1O0") (עם האות O במקום אפס) זורקת NumberFormatException.

  • parseAmount: אין בה try בכלל, והחריגה יוצאת ממנה מיד.
  • importCsv: יש בה try, אבל ה-catch שלה מקבל רק IOException. NumberFormatException אינה IOException, ולכן גם המתודה הזו ננטשת באמצע.
  • main: יש בה catch (IllegalArgumentException e). כאן נמצאה התאמה, כי NumberFormatException יורשת מ-IllegalArgumentException.

נניח שגם ל-main חסר catch שמתאים. אז ה-thread הראשי נגמר, וב-stack trace מופיעות שלוש המתודות, מ-parseAmount ועד main.

טעויות נפוצות
  • int חלקי 0 נותן 0, או שהוא מומר אוטומטית ל-double ונותן Infinity. בשלמים נזרקת ArithmeticException. Infinity ו-NaN קיימים רק בחישוב עם נקודה צפה.
  • כשאין catch, ה-JVM בולע את החריגה והריצה ממשיכה בשורה שאחריה. ה-thread נגמר עם stack trace, ואף שורה אחרי הזריקה לא רצה.
  • ה-finally הקרוב לנקודת הזריקה לוכד את החריגה, והריצה חוזרת לשגרה. finally רץ בדרך החוצה, אבל החריגה ממשיכה לעלות עד catch מתאים.
  • מה שהמתודה שינתה לפני הזריקה מתבטל מעצמו. אין Rollback. שדות שעודכנו ופריטים שנוספו נשארים כפי שהם.
  • חריגה שלא נתפסה במתודה נעצרת שם ולא מגיעה לקורא. היא עולה לקורא, ולקורא שלו, עד שנמצא catch או שה-thread מסתיים.
  • Integer.parseInt על טקסט עם אותיות זורק ClassCastException, כי הטיפוס לא מתאים. ClassCastException שייכת להמרת אובייקטים. כאן נזרקת NumberFormatException, ו-InputMismatchException היא של Scanner.
בדקו את עצמכם
int done = 7, total = 0; double pct = done * 100 / total; האם נזרקת חריגה? ומה אם total מוצהר double?

כשכל האופרנדים int, החילוק נעשה בשלמים ונזרקת ArithmeticException, עוד לפני ההמרה ל-double. אם total הוא double, החילוק בנקודה צפה ו-pct מקבל Infinity בלי חריגה (ואילו גם המונה היה 0, NaN).

בתוכנית Java יש שני threads. בזה המשני נזרקת NullPointerException שאיש לא תופס. מה קורה ל-thread הראשי? ומה היה קורה בתוכנית .NET מקבילה?

ב-Java הראשי ממשיך לרוץ, ורק המשני מסתיים עם stack trace. ב-.NET התהליך כולו נסגר.

חזרה לתוכן העניינים

Throwable, Error ו-Exception: checked מול unchecked

ב-Java כל מה שמותר לזרוק עם throw הוא אובייקט של Throwable או של מחלקה שיורשת ממנה. זה העץ שחשוב להכיר:

Text
Throwable
 +-- Exception                        (checked, except the RuntimeException branch)
 |    +-- RuntimeException            (unchecked, with every class below it)
 |    |    +-- IllegalArgumentException
 |    |    |    +-- NumberFormatException
 |    |    +-- ArithmeticException
 |    |    +-- NullPointerException
 |    |    +-- ClassCastException
 |    |    +-- IndexOutOfBoundsException
 |    |         +-- ArrayIndexOutOfBoundsException
 |    +-- IOException                 (checked)
 |    |    +-- FileNotFoundException
 |    |    +-- EOFException
 |    +-- SQLException                (checked)
 |    +-- ClassNotFoundException      (checked)
 |    +-- InterruptedException        (checked)
 +-- Error                            (unchecked: trouble inside the JVM itself)
      +-- VirtualMachineError
           +-- OutOfMemoryError
           +-- StackOverflowError

Error ו-Exception. בעץ שלמעלה הן נמצאות באותה קומה: שתיהן ילדות של Throwable, ואף אחת לא יורשת מהשנייה.

ההבדל ביניהן הוא במי שאמור להגיב. Error מדווחת שהמכונה הווירטואלית עצמה בצרה, למשל כשאין עוד מקום בערימה או במחסנית, ובשלב הזה לקוד האפליקציה אין דרך סבירה לתקן את המצב. Exception מדווחת על בעיה שהקוד שלכם יכול לצפות, להגיב לה ב-catch, ולהמשיך לעבוד.

checked מול unchecked (חריגה בדוקה מול לא בדוקה). ההבחנה עונה על שאלה אחת: האם javac יסרב לקמפל קוד שמתעלם מהחריגה. במקום לשנן רשימות, אפשר לשאול על כל מחלקה שאלה פשוטה, וזה מה שהתוכנית הבאה עושה: האם יש לה אב קדמון RuntimeException או Error?

Java
public class Classify {
    static void classify(Class<?> c) {
        boolean unchecked = RuntimeException.class.isAssignableFrom(c) || Error.class.isAssignableFrom(c);
        System.out.println(c.getSimpleName() + " -> " + (unchecked ? "unchecked" : "checked"));
    }

    public static void main(String[] argv) {
        classify(java.sql.SQLException.class);
        classify(NullPointerException.class);
        classify(InterruptedException.class);
        classify(OutOfMemoryError.class);
        classify(NumberFormatException.class);
        classify(Exception.class);
    }
}
פלט
SQLException -> checked
NullPointerException -> unchecked
InterruptedException -> checked
OutOfMemoryError -> unchecked
NumberFormatException -> unchecked
Exception -> checked
תשובה לשאלהסוגמה javac מצפה מכם
כן, אחת משתי המחלקות האלה נמצאת מעליה בעץuncheckedשום דבר. אפשר לא לתפוס ולא להכריז
לא. זה נכון גם ל-Exception ול-Throwable עצמןchecked (בדוקה)catch שלוכד אותה, או הכרזת throws בחתימה

בפלט רואים את זה: SQLException ו-InterruptedException יצאו checked, וכך גם Exception עצמה. NullPointerException, OutOfMemoryError ו-NumberFormatException יצאו unchecked. מהעץ אפשר להוסיף ש-IOException ו-ClassNotFoundException נמצאות בצד ה-checked.

למה דווקא כך? חריגות checked מתארות כשלים שתלויים בעולם שמחוץ לתוכנית: קובץ שנמחק, שרת שלא עונה, טבלה נעולה. בדיקה מוקדמת בקוד לא יכולה לשלול אותם, ולכן המהדר מחייב את המתכנת להחליט מראש מה יקרה כשהם יגיעו.

חריגות unchecked מעידות בדרך כלל על באג: null שלא היה אמור להיות שם, אינדקס שחושב לא נכון, המרה לא חוקית. בהן לא מטפלים, אלא מתקנים את הקוד.

שאלות שההבחנה הזו לא עונה עליהן, למרות שנוטים לייחס לה אותן:

שאלההתשובה, בלי קשר ל-checked או unchecked
מי זורק את החריגה, ה-JVM או המתכנת?שניהם. גם ה-JVM, גם ספריות וגם הקוד שלכם זורקים משני הסוגים
מה קורה אם איש לא לוכד אותה?אותו דבר בשני הסוגים: ה-thread נגמר עם עקבות המחסנית
באיזה שלב היא נזרקת, בהידור או בריצה?תמיד בריצה. בהידור javac רק מוודא שהקוד ערוך לחריגות הבדוקות

כך נראה קוד שמתעלם מחריגה checked:

Java
import java.io.*;

public class Loader {
    static void openConfig() {
        FileInputStream in = new FileInputStream("app.cfg");   // the constructor declares FileNotFoundException
        System.out.println("config opened");
    }

    public static void main(String[] argv) { openConfig(); }
}

javac דוחה אותו ומצביע על השורה של FileInputStream: unreported exception FileNotFoundException. בהמשך ההודעה הוא מסביר שהחריגה הזו צריכה להיתפס כאן, או להופיע בהצהרת throws של המתודה.

יש שתי דרכים לרצות את המהדר: לטפל במקום, או להצהיר ולהעביר את ההחלטה למי שקורא למתודה.

Java
import java.io.*;

public class ConfigFix {
    // fix 1: handle it right here
    static void openConfigHere() {
        try {
            FileInputStream in = new FileInputStream("app.cfg");
            System.out.println("config opened");
        } catch (FileNotFoundException e) {
            System.out.println("no app.cfg, using defaults");
        }
    }

    // fix 2: declare it, and the caller decides
    static void openConfigDeclared() throws FileNotFoundException {
        FileInputStream in = new FileInputStream("app.cfg");
        System.out.println("config opened");
    }

    public static void main(String[] argv) {
        openConfigHere();
        try { openConfigDeclared(); }
        catch (FileNotFoundException e) { System.out.println("caller handles: " + e.getMessage()); }
    }
}
פלט
no app.cfg, using defaults
caller handles: app.cfg (The system cannot find the file specified)

בהרצה הזו הקובץ באמת לא קיים, ולכן שתי הגרסאות הגיעו ל-catch. הטקסט שבסוגריים אחרי שם הקובץ מגיע ממערכת ההפעלה (כאן Windows).

מה throws עושה, ומה לא. הסתכלו על openConfigDeclared. המילה throws בחתימה שלה לא לכדה את החריגה: היא רק סיפרה ל-javac שהמתודה עשויה להוציא FileNotFoundException (או תת-מחלקה שלה). לכן ההחלטה עברה ל-main, ושם נדרש try-catch, אחרת main הייתה צריכה להכריז throws משלה.

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

הדרישה הזו חלה רק על checked. חריגה unchecked יכולה לעבור דרך עשר מתודות בשרשרת בלי שאף אחת מהן תזכיר אותה בחתימה.

ב-C# אין checked. כל החריגות יורשות מ-System.Exception, אין סעיף throws בחתימות, והמהדר לעולם אינו דורש לתפוס חריגה כלשהי.

תרחיש 14: שלוש מתודות מול javac
  • validate() זורקת new UnsupportedOperationException("todo"), בלי try ובלי throws. היא מתקמפלת: זו צאצאית של RuntimeException, כלומר unchecked.
  • loadPlugin() קוראת ל-Class.forName("Plugin"), בלי try ובלי throws. היא נדחית, כי forName מצהירה על ClassNotFoundException, שהיא checked.
  • backup() כותבת throw new IOException("disk") ומצהירה throws IOException. היא מתקמפלת, אבל מעכשיו כל מתודה שקוראת ל-backup צריכה לתפוס IOException או להצהיר עליה בעצמה.
טעויות נפוצות
  • על unchecked חובה להצהיר, ואת checked מותר להשאיר בלי טיפול. בדיוק הפוך. checked מחייבות catch או throws, ו-unchecked פטורות.
  • חריגות checked נזרקות כבר בזמן ההידור. המהדר רק בודק שהקוד ערוך להן. הזריקה עצמה, כמו בכל חריגה, קורית בזמן ריצה.
  • ה-JVM זורק unchecked והמתכנת זורק checked, וזו כל ההבחנה. שני הצדדים זורקים משני הסוגים. ההבחנה נוגעת רק לדרישת המהדר.
  • יש חריגות שמסיימות את התוכנית גם כשכתוב להן catch מתאים, ואלה ה-checked. catch מתאים עוצר חריגה מכל סוג. checked או unchecked משפיע רק על ההידור.
  • unchecked הן בעיקר בעיות של ניהול זיכרון. רובן באגים בלוגיקה: null, אינדקס, המרה. בעיות זיכרון חמורות שייכות ל-Error.
  • Error היא תת-מחלקה של Exception, והיא מסמנת תקלה קלה שחולפת. Error ו-Exception הן אחיות תחת Throwable, ו-Error מסמנת תקלה חמורה.
  • המהדר בודק גם את Error וגם את RuntimeException. שתיהן unchecked, והמהדר לא דורש לגביהן דבר.
  • IOException היא unchecked, ואם לא תופסים אותה ה-JVM כולו נסגר. IOException היא checked. וחריגה שלא נתפסה מסיימת את ה-thread שבו נזרקה, לא כל thread אחר.
  • throws בחתימה מטפל בחריגה, והקורא כבר לא צריך לדאוג. throws רק מכריז. מי שקורא למתודה הוא שצריך לתפוס או להצהיר בעצמו.
בדקו את עצמכם
האם javac יחייב טיפול ב-SQLException? וב-NullPointerException? ובחריגה שאתם כותבים ויורשת מ-RuntimeException?

SQLException כן, היא checked. NullPointerException לא, היא צאצאית של RuntimeException. וגם המחלקה שלכם לא, כי היא יורשת את המעמד unchecked מ-RuntimeException.

בפרויקט C# מתודה זורקת IOException, ואיש לא תופס אותה או מזכיר אותה בחתימה. האם הקוד יתקמפל?

כן. ב-C# אין חריגות checked ואין throws, והמהדר לא דורש טיפול. אם החריגה תיזרק בפועל ולא תיתפס, התהליך ייפול בזמן ריצה.

חזרה לתוכן העניינים

כמה catch אחרי try אחד: סדר, התאמה ו-multi-catch

בתוכנית הבאה אותו try רץ שלוש פעמים, ובכל פעם נזרקת חריגה אחרת. אחרי ה-try יש שלושה בלוקי catch, ולכל אחד תגובה משלו: לבקש מהמשתמש קובץ, לנסות שוב, או להתריע.

Java
import java.io.*;
import java.sql.SQLException;

public class SyncJob {
    static void sync(int step) throws IOException, SQLException {
        if (step == 1) throw new FileNotFoundException("orders.csv");
        if (step == 2) throw new SQLException("table locked");
        throw new EOFException("export cut short");
    }

    public static void main(String[] argv) {
        for (int step = 1; step <= 3; step++) {
            try { sync(step); }
            catch (FileNotFoundException e) { System.out.println(step + ": missing file, ask the user (" + e.getMessage() + ")"); }
            catch (IOException e)           { System.out.println(step + ": I/O problem, retry (" + e.getMessage() + ")"); }
            catch (SQLException e)          { System.out.println(step + ": database problem, alert (" + e.getMessage() + ")"); }
        }
    }
}
פלט
1: missing file, ask the user (orders.csv)
2: database problem, alert (table locked)
3: I/O problem, retry (export cut short)

בכל צעד הודפסה שורה אחת בדיוק. ה-JVM עובר על הבלוקים מלמעלה ועוצר בראשון שהטיפוס שלו הוא הטיפוס של החריגה או אחד האבות שלה, והשאר לא נבדקים כלל, ובטח לא רצים במקביל. כל בלוק גם מכריז משתנה e משלו, מהטיפוס שלו, ואין משתנה משותף.

בצעד 1 נזרקה FileNotFoundException. היא גם IOException, אבל רץ הבלוק הראשון כי הוא נבדק קודם. בצעד 3 נזרקה EOFException: הבלוק הראשון לא מתאים לה, והשני כן, כי EOFException יורשת מ-IOException.

IOException ו-SQLException יושבות בענפים נפרדים של העץ, ולכן catch של אחת לעולם לא יתפוס את השנייה. כך גם NullPointerException ו-FileNotFoundException: האב המשותף הקרוב שלהן הוא Exception, ו-catch של אחת מהן לא נוגע בשנייה.

סדר הבלוקים: מהצר אל הרחב. אם catch של אב מופיע לפני catch של צאצא שלו, הבלוק של הצאצא הופך לקוד מת, כי האב תמיד תופס קודם. המהדר מסרב לקבל את זה, גם ב-Java וגם ב-C#:

Java
public class Order {
    public static void main(String[] argv) {
        try { Integer.parseInt(argv[0]); }
        catch (RuntimeException e)      { System.out.println("general"); }
        catch (NumberFormatException e) { System.out.println("specific"); }
    }
}
פלט
Order.java:5: error: exception NumberFormatException has already been caught
        catch (NumberFormatException e) { System.out.println("specific"); }
        ^
1 error
C#
using System;

class Program
{
    static void Main(string[] args)
    {
        try { int.Parse(args[0]); }
        catch (Exception)       { Console.WriteLine("general"); }
        catch (FormatException) { Console.WriteLine("specific"); }
    }
}
פלט
Program.cs(9,16): error CS0160: A previous catch clause already catches all exceptions of this or of a super type ('Exception')

המסקנה: catch (Exception e), אם הוא בכלל קיים, בא תמיד אחרון ברשימה.

multi-catch. מ-Java 7 אפשר לרכז כמה טיפוסים בבלוק אחד, מופרדים בקו אנכי |, כשהתגובה לכולם זהה:

Java
import java.io.*;
import java.sql.SQLException;

public class MultiCatch {
    static void sync(int step) throws IOException, SQLException {
        if (step == 2) throw new SQLException("table locked");
        throw new EOFException("export cut short");
    }

    public static void main(String[] argv) {
        for (int step = 2; step <= 3; step++) {
            try { sync(step); }
            catch (IOException | SQLException e) {    // one shared body for both types
                System.out.println("logged " + e.getClass().getSimpleName() + ", job postponed");
            }
        }
    }
}
פלט
logged SQLException, job postponed
logged EOFException, job postponed

לבלוק כזה יש גוף אחד בלבד, ולכן הוא מתאים רק כשאין צורך להבדיל בין הטיפוסים. רישום עם פסיק, catch (IOException, SQLException e), אינו תחביר חוקי, ו-javac עונה עליו בשרשרת שגיאות תחביר.

ב-C# 6 נוסף כלי אחר: מסנן חריגה (exception filter). הבלוק catch (T e) when (condition) נכנס לפעולה רק אם הטיפוס מתאים וגם התנאי מתקיים. אחרת החריגה ממשיכה הלאה, כאילו הבלוק לא קיים.

C#
using System;

class Program
{
    static void Main()
    {
        foreach (var msg in new[] { "retry: timeout", "fatal: bad key" })
        {
            try
            {
                try { throw new InvalidOperationException(msg); }
                catch (InvalidOperationException e) when (e.Message.StartsWith("retry"))
                {
                    Console.WriteLine("filter matched: " + e.Message);
                }
            }
            catch (Exception e) { Console.WriteLine("filter skipped, outer got: " + e.Message); }
        }
    }
}
פלט
filter matched: retry: timeout
filter skipped, outer got: fatal: bad key

ואם הייתם כותבים רק catch (Exception e)? דמיינו שיום אחד נכנס ל-sync באג, והיא פונה למשתנה שערכו null. NullPointerException היא צאצאית של Exception, ולכן הבלוק הכללי ילכוד אותה, ידפיס את הודעת הניסיון החוזר שנכתבה בשביל תקלת קלט-פלט, והבאג ייעלם בתוך היומן.

זה המחיר האמיתי של catch רחב: קובץ חסר, טבלה נעולה ובאג בקוד מקבלים תגובה אחת, ומה שלא צפיתם לא מגיע לעיניים של אף אחד. כדי להפריד ביניהם בתוך בלוק כזה הייתם צריכים לבדוק e instanceof ... שוב ושוב, כלומר לכתוב ידנית את מה שבלוקים נפרדים נותנים מעצמם.

שני נימוקים שגויים שנשמעים לפעמים: catch רחב אינו איטי באופן שמורגש, והוא גם לא מבטל את finally. הסיבה להעדיף בלוקים צרים היא תגובה שמתאימה לתקלה, ובאגים שנשארים גלויים ומתגלים מוקדם.
תרחיש 15: ארבע חריגות מול שלושה בלוקים

אחרי try יש, בסדר הזה: catch (NumberFormatException e), catch (IllegalArgumentException e), catch (RuntimeException e).

  • נזרקת NumberFormatException: הבלוק הראשון מתאים ורץ, ושני האחרים מדולגים.
  • נזרקת new IllegalArgumentException("negative qty"): הראשון צר מדי בשבילה, והשני מתאים.
  • נזרקת NullPointerException: היא לא IllegalArgumentException, אבל היא כן RuntimeException, ולכן רק השלישי מתאים.
  • קוד ב-try מצהיר throws IOException, והיא אכן נזרקת: אף בלוק לא מתאים, כי IOException אינה RuntimeException. החריגה ממשיכה לקורא, ולכן המתודה הזו חייבת להצהיר בעצמה throws IOException כדי להתקמפל.

ואם נעביר את catch (RuntimeException e) לראש הרשימה, javac ידחה את הקוד, כי שני הבלוקים שאחריו כבר לא יוכלו לרוץ לעולם.

טעויות נפוצות
  • catch (IOException e) יתפוס גם ArithmeticException, כי שתיהן חריגות. catch תופס רק את הטיפוס שלו ואת צאצאיו. בין שתי אלה אין קשר ירושה.
  • שמים catch (Exception e) ראשון, והוא יעביר את הטיפול לבלוקים הספציפיים שאחריו. זה לא מתקמפל. הבלוקים הספציפיים היו נשארים קוד מת.
  • ל-try אחד מותר catch אחד, ולכן כל חריגה צריכה try משלה. מותר לשרשר כמה catch שרוצים אחרי אותו try.
  • catch (A, B e) מאחד שני טיפוסים. התחביר הנכון הוא catch (A | B e), ורק כשהתגובה לשניהם זהה.
  • multi-catch, או catch (Exception e) יחיד, מריץ לכל טיפוס קוד אחר באופן אוטומטי. בשני המקרים יש גוף אחד. הבחנה בין טיפוסים דורשת בלוקים נפרדים.
  • אפשר לרכז את כל הטיפול ב-finally, והוא יגיב לפי סוג החריגה. finally לא מקבל משתנה חריגה ולא יודע מה נזרק. הוא קוד ניקוי, לא מטפל.
  • מספיק catch ל-IOException, ואת SQLException ה-JVM כבר יסדר. SQLException היא checked. בלי catch או throws בשבילה, הקוד לא יתקמפל.
  • כמה בלוקי catch פוטרים מ-throws, רצים במקביל, או חולקים משתנה אחד. אף אחד מהשלושה. כל בלוק עצמאי ועם משתנה משלו, רק אחד רץ, ו-throws נדרש לכל checked שלא נתפסה.
  • catch (Exception e) לוכד אך ורק אובייקטים שהמחלקה שלהם היא Exception עצמה, ובנוסף מבטל את ה-finally. הוא לוכד גם כל צאצא של Exception, ו-finally ממשיך לרוץ כרגיל.
בדקו את עצמכם
try יוצר new FileInputStream(path), ואחריו בא catch (IOException e) ואז catch (FileNotFoundException e). מה javac יגיד, ואיך מתקנים?

שגיאת הידור: FileNotFoundException כבר נתפסה, כי היא צאצאית של IOException, והבלוק שלה לא יוכל לרוץ לעולם. מחליפים את הסדר: הצר קודם.

מתי multi-catch עדיף על שני בלוקים נפרדים?

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

חזרה לתוכן העניינים

finally ו-try-with-resources

finally מבטיח ריצה בכל דרך שבה יוצאים מה-try:

  • ה-try הסתיים בלי תקלה.
  • נזרקה חריגה, בין אם אחד מבלוקי ה-catch תפס אותה ובין אם היא ממשיכה למעלה.
  • ה-try או ה-catch ביצעו return. ה-finally רץ קודם, ורק אחריו השליטה חוזרת לקורא.

הסדר קבוע: קודם try, אם נזרקה חריגה מתאימה רץ ה-catch שלה, ובסוף finally. אין מצב שבו finally מדלג מעל catch או רץ לפני try.

Java
public class Lookup {
    static String lookup(int id) {
        try {
            System.out.println("try " + id);
            if (id == 0) return "guest";
            if (id < 0) throw new IllegalArgumentException("negative id");
            System.out.println("regular path");
        } catch (IllegalArgumentException e) {
            System.out.println("catch: " + e.getMessage());
            return "invalid";
        } finally {
            System.out.println("finally " + id);
        }
        return "user" + id;
    }

    public static void main(String[] argv) {
        System.out.println(lookup(7));
        System.out.println(lookup(0));
        System.out.println(lookup(-2));
    }
}
פלט
try 7
regular path
finally 7
user7
try 0
finally 0
guest
try -2
catch: negative id
finally -2
invalid

בשלוש הקריאות השורה של finally הודפסה לפני הערך המוחזר: גם אחרי return מתוך ה-try (הקריאה עם 0), וגם אחרי return מתוך ה-catch (הקריאה עם מינוס 2).

בזכות ההבטחה הזו, finally הוא המקום הטבעי לניקוי: סגירת קבצים, ניתוק מבסיס נתונים, שחרור נעילות, כדי שמשאבים לא ידלפו. אבל finally לא סוגר שום דבר מעצמו: את הקריאה ל-close() צריך לכתוב בתוכו.

יש מצב אחד שבו finally לא רץ: כשהתהליך עצמו נגמר באמצע. ב-Java זה System.exit, וב-.NET זה Environment.FailFast.

Java
public class ExitDemo {
    public static void main(String[] argv) {
        try {
            System.out.println("saving draft");
            System.exit(3);                    // the JVM shuts down here
        } finally {
            System.out.println("cleanup");
        }
    }
}
פלט
saving draft

התהליך יצא עם קוד 3, והמילה cleanup לא הודפסה.

מה קורה לערך ההחזרה? בתוכנית הבאה שתי מתודות מבצעות return מתוך try, ו-finally מנסה לשנות את מה שמוחזר:

Java
import java.util.*;

public class ReturnValue {
    static int hits() {
        int count = 10;
        try { return count; }                  // the value 10 is fixed here
        finally {
            count = 0;
            System.out.println("finally set count to " + count);
        }
    }

    static List<String> tags() {
        List<String> list = new ArrayList<>();
        list.add("red");
        try { return list; }                   // the reference is fixed, not the contents
        finally { list.add("blue"); }
    }

    public static void main(String[] argv) {
        System.out.println(hits());
        System.out.println(tags());
    }
}
פלט
finally set count to 0
10
[red, blue]

hits החזירה 10 למרות ש-finally איפס את count: ברגע ה-return הערך 10 כבר הועתק הצידה, ו-finally שינה רק את המשתנה המקומי. ב-tags התמונה הפוכה. מה שנשמר הצידה הוא הפניה לרשימה, ו-finally הוסיף איבר לאותה רשימה, ולכן הקורא ראה גם את blue.

הכלל: הביטוי שאחרי return מחושב לפני ה-finally. משתנה פרימיטיבי מוקפא בערכו, ואילו אובייקט עדיין חשוף לשינויים בתוכו.

ב-Java מותר לכתוב return בתוך finally, וזה הרגל מסוכן. הוא מחליף את ערך ההחזרה של ה-try, וגרוע מזה, מעלים חריגה שהייתה בדרך החוצה:

Java
public class FinallyReturn {
    @SuppressWarnings("finally")
    static int risky() {
        try {
            throw new IllegalStateException("disk full");
        } finally {
            return -1;                         // legal in Java, but it hides the exception
        }
    }

    public static void main(String[] argv) {
        System.out.println("result " + risky());
    }
}
פלט
result -1

ה-IllegalStateException נעלמה בלי סימן. בלי ה-SuppressWarnings, הידור עם javac -Xlint מזהיר על כך: warning: [finally] finally clause cannot complete normally.

C# פשוט אוסרת לצאת מ-finally:

C#
using System;

class Program
{
    static int Risky()
    {
        try { return 1; }
        finally { return -1; }
    }

    static void Main() { Console.WriteLine(Risky()); }
}
פלט
Program.cs(8,19): error CS0157: Control cannot leave the body of a finally clause

try-with-resources. מאז Java 7 אפשר לפתוח משאב בתוך הסוגריים של ה-try עצמו. בסוף הבלוק, איך שלא יסתיים, Java מפעילה בשבילכם את close() של המשאב, ולכן אין צורך לכתוב finally רק בשביל הסגירה.

המחלקה Channel שבדוגמה לא יורשת מאף מחלקה מיוחדת. מה שמכשיר אותה לשבת בסוגריים הוא implements AutoCloseable, הממשק שמגדיר את close.

Java
public class Streaming {
    static class Channel implements AutoCloseable {
        private final String name;
        private final boolean failOnClose;

        Channel(String name, boolean failOnClose) {
            this.name = name;
            this.failOnClose = failOnClose;
            System.out.println("connect " + name);
        }

        @Override
        public void close() {
            System.out.println("disconnect " + name);
            if (failOnClose) throw new IllegalStateException(name + " did not close cleanly");
        }
    }

    public static void main(String[] argv) {
        try (Channel audio = new Channel("audio", false);
             Channel video = new Channel("video", true)) {
            System.out.println("streaming");
            throw new RuntimeException("bandwidth dropped");
        } catch (RuntimeException e) {
            System.out.println("handler sees: " + e.getMessage());
            for (Throwable s : e.getSuppressed())
                System.out.println("  suppressed: " + s.getMessage());
        } finally {
            System.out.println("session over");
        }
    }
}
פלט
connect audio
connect video
streaming
disconnect video
disconnect audio
handler sees: bandwidth dropped
  suppressed: video did not close cleanly
session over

קראו את הפלט לפי הסדר, והכללים עולים ממנו:

  • video נפתח אחרון ונסגר ראשון: משאבים נסגרים בסדר ההפוך לזה שבו נפתחו.
  • שתי שורות ה-disconnect מופיעות לפני handler sees. הסגירה הסתיימה עוד לפני שה-catch קיבל את החריגה, ו-session over של finally מגיע אחרון.
  • גם close של video זרקה חריגה, אבל ה-catch קיבל את bandwidth dropped המקורית. החריגה של close לא אבדה: היא שמורה בתוך getSuppressed() כחריגה מדוכאת (suppressed).

ב-C# המקבילה היא הוראת using עם אובייקט שמממש IDisposable. גם שם Dispose נקרא אוטומטית, בסדר הפוך, לפני שה-catch החיצוני רץ:

C#
using System;

class Cursor : IDisposable
{
    private readonly string name;
    public Cursor(string name) { this.name = name; Console.WriteLine("open " + name); }
    public void Dispose() { Console.WriteLine("release " + name); }
}

class Program
{
    static void Main()
    {
        try
        {
            using (var rows = new Cursor("rows"))
            using (var index = new Cursor("index"))
            {
                Console.WriteLine("query");
                throw new TimeoutException("query took too long");
            }
        }
        catch (TimeoutException e) { Console.WriteLine("caught: " + e.Message); }
    }
}
פלט
open rows
open index
query
release index
release rows
caught: query took too long

ולמה לא להשאיר את זה ל-Garbage Collector? ה-GC מפנה זיכרון לפי שיקולים משלו, ואין לו לוח זמנים שאפשר לסמוך עליו. אובייקט של קובץ יכול לחכות דקות, או לא להיאסף עד סוף הריצה, ובכל הזמן הזה מערכת ההפעלה מחזיקה בשבילו handle פתוח.

חשוב גם לא לייחס ל-try-with-resources יותר ממה שיש בו. הוא לא שומר על קובץ מפני פתיחה נוספת בידי מתודה אחרת, והוא לא מחייב כשלעצמו להוסיף throws למתודות שמשתמשות במשאב. ההבטחה שלו מצומצמת וברורה: close ייקרא.

תרחיש 16: שרת שנגמרים לו הקבצים הפתוחים

מתודת ייצוא פותחת קובץ דוח, כותבת אליו שורות, ובשורה האחרונה של ה-try קוראת ל-close.

כשאחת הכתיבות נכשלת, נזרקת חריגה, הקריאה ל-close נשארת מאחור, והקובץ נשאר פתוח. השרת מריץ את הייצוא אלפי פעמים ביום, ואחרי מספיק כשלים מערכת ההפעלה מסרבת לפתוח קבצים נוספים. מאותו רגע נכשלים כל הייצואים, גם התקינים.

  • תיקון סביר: להעביר את ה-close ל-finally, כדי שירוץ גם כשהכתיבה נכשלת.
  • תיקון עדיף: לפתוח את הקובץ בסוגריים של try-with-resources, וכך הסגירה מובטחת בלי קוד ידני.
טעויות נפוצות
  • finally רץ רק כשמשהו השתבש. הוא רץ גם כשה-try עבר חלק, וזה בדיוק מה שהופך אותו למקום לניקוי.
  • return בתוך try מדלג על finally. finally רץ לפני שהשליטה חוזרת לקורא.
  • finally עוקף את catch ושולח את החריגה ישר לקורא, או רץ עוד לפני try. הסדר הוא תמיד try, אחריו catch מתאים, ובסוף finally.
  • finally סוגר בעצמו כל משאב שנפתח ב-try. finally מריץ רק את הקוד שכתבתם בו. בלי קריאה ל-close, שום דבר לא נסגר.
  • ב-try-with-resources, אם הגוף נכשל באמצע, המשאב נשאר פתוח, ולכן עדיין כותבים close ידני בסוף. הסגירה אוטומטית בכל יציאה מהבלוק, גם כשהיציאה היא חריגה.
  • כדי שמשאב ייסגר אוטומטית, המחלקה שלו צריכה לרשת מ-Exception. היא צריכה לממש את AutoCloseable (ב-C#: IDisposable).
  • try-with-resources מבקש מה-GC לקרוא ל-close, ומחייב throws בכל מתודה שמשתמשת במשאב. ה-JVM קורא ל-close בעצמו ברגע שהבלוק נגמר, ואין שום דרישה ל-throws.
בדקו את עצמכם
מה מודפס ומה מוחזר? try { System.out.println("1"); return "x"; } catch (Exception e) { return "y"; } finally { System.out.println("2"); }

מודפס 1 ואחריו 2, והמתודה מחזירה "x". אין חריגה, ולכן ה-catch לא רץ, ו-finally רץ אחרי חישוב ה-return ולפני החזרת השליטה.

ב-try-with-resources נפתחו שלושה משאבים בסדר log, db, cache. באיזה סדר הם ייסגרו, והאם זה יקרה לפני ה-catch?

cache, אחריו db ואחריו log, הפוך לפתיחה. הסגירה מתבצעת לפני שה-catch וה-finally של אותה הוראה רצים.

חזרה לתוכן העניינים

חריגה משלכם, עטיפה וזריקה מחדש

דמיינו שירות אחסון בענן. כשמשתמש מנסה להעלות קובץ שחורג מהמכסה שלו, אף מחלקה מובנית לא אומרת את זה בבירור: IllegalStateException כללית מדי, ו-IOException בכלל לא מתאימה. כאן כותבים מחלקת חריגה חדשה, כמו QuotaExceededException:

Java
public class Storage {
    static class QuotaExceededException extends Exception {     // checked: callers must deal with it
        private final long overByMb;

        QuotaExceededException(String user, long overByMb) {
            super(user + " is over quota by " + overByMb + " MB");   // the message
            this.overByMb = overByMb;                                // extra data for the handler
        }

        long getOverByMb() { return overByMb; }
    }

    static void upload(String user, long usedMb, long fileMb) throws QuotaExceededException {
        long limitMb = 1024;
        if (usedMb + fileMb > limitMb)
            throw new QuotaExceededException(user, usedMb + fileMb - limitMb);
        System.out.println(user + ": upload accepted");
    }

    public static void main(String[] argv) {
        String[] users = {"noa", "itai"};
        long[] used = {200, 1000};
        for (int i = 0; i < users.length; i++) {
            try { upload(users[i], used[i], 300); }
            catch (QuotaExceededException e) {
                System.out.println(e.getMessage() + ", offer " + e.getOverByMb() + " MB more");
            }
        }
    }
}
פלט
noa: upload accepted
itai is over quota by 276 MB, offer 276 MB more

QuotaExceededException בדוגמה יורשת מ-Exception, ולכן היא checked, ו-upload חייבת להכריז עליה ב-throws. אילו הייתה יורשת מ-RuntimeException היא הייתה unchecked, ושני הכיוונים מקובלים ב-Java. ב-C# יורשים תמיד מ-Exception, ושאלת ה-checked לא קיימת שם.

המחלקה מעבירה הודעה לבנאי של האב ומוסיפה שדה משלה, כך שה-catch יכול להציע ללקוח בדיוק כמה מקום חסר לו.

השאלההתשובה עבור QuotaExceededException
האם הלוג יגיד מה קרה?כן. השם עצמו מספר שמדובר בחריגה ממכסה, בלי לפענח הודעה
אפשר להגיב רק לה ולא לתקלות אחרות?כן. catch (QuotaExceededException e) לא ילכוד שום חריגה אחרת
אפשר להעביר נתונים ל-handler?כן. השדה overByMb הגיע ל-catch והפך להצעה ללקוח
האם התוכנית תרוץ מהר יותר?לא. בדיקת המכסה עדיין רצה, ונוספה עוד מחלקה
האם רק בזכותה יש stack trace?לא. גם Exception רגילה נושאת עקבות מחסנית מהרגע שנוצרה
האם זה כלי לשגיאות הידור או לשפה בלי חריגות?לא. זו חריגה רגילה שנזרקת בזמן ריצה
מה לא נחשב חריגה מותאמת? נניח ש-catch לוכד NumberFormatException ומדפיס הודעה בעברית: הפלט השתנה, אבל מה שנזרק היה ונשאר NumberFormatException. כך גם החלפת הטקסט של חריגה קיימת, ובוודאי משתנה null שמפיל את התוכנית, כי בלי מחלקה חדשה שיורשת מ-Exception אין חריגה מותאמת.

עטיפה (wrapping). כשמתרגמים חריגה טכנית לחריגה ברמה גבוהה יותר, מעבירים את המקורית כסיבה, כדי שהמידע עליה לא יאבד. ב-Java זה הארגומנט השני בבנאי, new X(message, cause), וב-C# המאפיין InnerException.

Java
public class PortReader {
    static int readPort(String text) {
        try {
            return Integer.parseInt(text);
        } catch (NumberFormatException e) {
            throw new IllegalStateException("bad port setting", e);   // wrap, keep the cause
        }
    }

    public static void main(String[] argv) {
        try { readPort("80a"); }
        catch (IllegalStateException e) {
            System.out.println(e.getMessage());
            System.out.println("cause: " + e.getCause().getClass().getSimpleName());
        }
    }
}
פלט
bad port setting
cause: NumberFormatException

זריקה מחדש ב-C#. לפעמים מתודה לוכדת חריגה רק כדי לתעד אותה, ואחר כך צריכה לשחרר אותה לקורא. התוכנית הבאה מנסה ארבע דרכים לעשות את זה, ובכולן Divide היא המקום שבו החילוק באפס קרה בפועל:

C#
using System;

class Program
{
    static int Divide(int a, int b) { return a / b; }

    static void Rethrow() { try { Divide(8, 0); } catch (Exception) { throw; } }
    static void Reset()   { try { Divide(8, 0); } catch (Exception ex) { throw ex; } }
    static void Wrap()    { try { Divide(8, 0); }
                            catch (Exception ex) { throw new ApplicationException("ratio failed", ex); } }
    static void Swallow() { try { Divide(8, 0); } catch (Exception) { return; } }

    static void Main()
    {
        try { Rethrow(); }
        catch (Exception e) { Console.WriteLine("throw;    Divide in trace: " + e.StackTrace.Contains("Divide")); }
        try { Reset(); }
        catch (Exception e) { Console.WriteLine("throw ex; Divide in trace: " + e.StackTrace.Contains("Divide")); }
        try { Wrap(); }
        catch (Exception e) { Console.WriteLine("wrapped:  " + e.Message + ", inner " + e.InnerException.GetType().Name); }
        Swallow();
        Console.WriteLine("return;   the caller never heard about it");
    }
}
פלט
throw;    Divide in trace: True
throw ex; Divide in trace: False
wrapped:  ratio failed, inner DivideByZeroException
return;   the caller never heard about it
  • throw; הדפיס True: הקורא קיבל את החריגה עם עקבות המחסנית המלאות, ו-Divide עדיין מופיעה בהן.
  • throw ex; הדפיס False. האובייקט הוא אותו אובייקט, אבל העקבות נכתבו מחדש מנקודת ה-throw שב-Reset, והשורה של Divide נעלמה.
  • ב-Wrap נבנתה חריגה חדשה, ApplicationException, והקודמת לא אבדה כי הועברה לבנאי, ולכן היא נגישה דרך InnerException. בלי הארגומנט הזה, throw new היה מתחיל חריגה בלי שום קשר למקור.
  • ב-Swallow, ה-return בתוך catch סיים את המתודה כאילו הכול תקין, ו-Main לא קיבל שום חריגה.

השורה של Reset גם מקבלת אזהרת build, CA2200, בדיוק בגלל מחיקת המידע הזה. לכן בתוך catch שרק מתעד, כותבים throw; בלי שם.

טעויות נפוצות
  • חריגה מותאמת חוסכת בדיקות תקינות, ולכן התוכנית רצה מהר יותר. היא לא מאיצה כלום. הערך שלה הוא בהירות: שם מדויק ו-catch מדויק.
  • כותבים חריגה מותאמת כדי לקבל stack trace. כל חריגה נושאת stack trace מרגע יצירתה.
  • ב-Java חריגה מותאמת חייבת לרשת מ-RuntimeException. מותר לבחור. ירושה מ-Exception נותנת checked, ומ-RuntimeException נותנת unchecked.
  • חריגות מותאמות נועדו לשגיאות שהמהדר מגלה, או לשפות שאין בהן חריגות. זו חריגה רגילה שנזרקת בזמן ריצה, בשפה שיש בה מנגנון חריגות.
  • הדפסת הודעה משלכם ב-catch, או החלפת ההודעה של חריגה קיימת, יוצרות שגיאה מותאמת. מותאמת פירושה מחלקה חדשה שיורשת מ-Exception. כל השאר משנה רק טקסט.
  • ב-C#, throw ex; משמר את המקום המקורי של התקלה. הוא מאפס את ה-stack trace. מי שמשמר אותו הוא throw; בלי שם.
  • throw new Exception() מקבלת אוטומטית את ה-stack trace של הקודמת, ו-return; ב-catch מעביר את החריגה לקורא. חריגה חדשה מתחילה נקייה אלא אם מעבירים InnerException, ו-return פשוט בולע את התקלה.
בדקו את עצמכם
צוות Java מגדיר SeatTakenException ורוצה שהמהדר יאלץ כל קוד שמזמין מושב להתייחס אליה. ממה לרשת?

מ-Exception ולא מ-RuntimeException, כך שהחריגה תהיה checked והמהדר ידרוש catch או throws.

ב-C# כתבתם catch (Exception err) { Audit(err); throw err; }. מה יחסר למי שיחקור את התקלה?

המיקום המקורי: ה-stack trace יתחיל בשורת ה-throw err ולא במתודה שבה התקלה קרתה. כותבים throw; כדי לשמור אותו.

חזרה לתוכן העניינים

חריגות אינן כלי לזרימה רגילה

שתי המתודות בתוכנית הבאה מחפשות את החשבונית הראשונה שבאיחור. הראשונה יוצאת מהלולאה בזריקת חריגה, והשנייה ב-return רגיל:

Java
public class Invoices {
    static int[] daysLate = {0, 0, 12, 0, 30};

    public static void main(String[] argv) {
        System.out.println(firstLateByThrow() + " " + firstLate());
    }

    // bad: an exception is the way out of the loop
    static int firstLateByThrow() {
        int found = -1;
        try {
            for (int i = 0; i < daysLate.length; i++)
                if (daysLate[i] >= 1) { found = i; throw new RuntimeException("stop"); }
        } catch (RuntimeException stop) {
            // searching is over
        }
        return found;
    }

    // good: an ordinary exit
    static int firstLate() {
        for (int i = 0; i < daysLate.length; i++)
            if (daysLate[i] >= 1) return i;
        return -1;
    }
}
פלט
2 2

התוצאה זהה, אז מה רע בגרסה הראשונה? השוו מה Java עושה בכל אחת מהן כשהחיפוש מצליח:

מה קורהfirstLate (return)firstLateByThrow (throw)
יציאה מהלולאהקפיצה ישירה החוצה, בתוך אותה מתודהפריקת המחסנית עד שנמצא catch מתאים
אובייקטים חדשיםאיןאובייקט RuntimeException חדש בכל חיפוש מוצלח
עקבות המחסניתלא נאספותנאספות בכל פעם, וזה הרכיב היקר ביותר
קריאת הקודרואים את היציאה בדיוק במקום שבו היא קוריתצריך לאתר את ה-catch כדי לדעת לאן הזרימה ממשיכה

המסקנה: throw שמור לאירוע שלא אמור לקרות. החלטות שגרתיות, כמו נמצא אז עוצרים או פגום אז מדלגים, נכתבות עם if, break, continue ו-return.

כמה שאלות שעולות סביב חריגות, והתשובות להן:

השאלההתשובה
האם השמה שבוצעה לפני הזריקה מתבטלת כשתופסים את החריגה?לא. משתנים ושדות שעודכנו נשארים מעודכנים
האם catch בתוך לולאה פועל רק בפעם הראשונה?לא. הוא תופס בכל סיבוב שבו נזרקת חריגה
האם ה-catch חייב לשבת במתודה אחרת מזו שזרקה?לא. אותה מתודה, ואפילו אותו try, זה תקין לגמרי
האם המהדר דורש לזרוק מחדש כל חריגה שנתפסה?לא. מותר לסיים את הטיפול בתוך ה-catch
האם חריגה שנתפסה תקועה בזיכרון עד סוף הריצה?לא. היא אובייקט רגיל, וה-GC אוסף אותה כשאין אליה הפניות, בלי דליפה
האם מערכת ההפעלה שומרת תיעוד של כל חריגה שנזרקה?לא. תיעוד קיים רק אם הקוד שלכם או ספרייה כותבים אותו ללוג
Java
public class Readings {
    public static void main(String[] argv) {
        String[] readings = {"12", "x", "40", "?", "8"};
        int sum = 0, rejected = 0;
        for (String r : readings) {
            try {
                sum += Integer.parseInt(r);
            } catch (NumberFormatException e) {   // runs again on every bad item
                rejected++;
            }
        }
        System.out.println("sum " + sum + ", rejected " + rejected);
    }
}
פלט
sum 60, rejected 2

ה-catch הופעל פעמיים, פעם לכל ערך פגום, והסכום שנצבר לפני כל כישלון נשמר. הקוד נכון, אבל כשרוב הקלט פגום הוא משלם על זריקה ועל איסוף stack trace כמעט בכל סיבוב.

catch ריק מחמיר את המצב: הוא מעלים את הבעיה, והתוכנית ממשיכה עם נתונים שגויים בלי שאיש יודע.
תרחיש 17: ייבוא לילי של חצי מיליון מזהים

תהליך לילי קורא חצי מיליון מזהים מקובץ, וממיר כל אחד ב-Integer.parseInt בתוך try שבתוך הלולאה. אחרי שינוי אצל הספק, רוב השורות מגיעות עם קידומת טקסט.

פתאום התהליך נמשך פי כמה: כמעט כל סיבוב זורק NumberFormatException ואוסף stack trace.

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

Java
public class ReadingsChecked {
    static boolean isDigits(String s) {
        if (s.isEmpty()) return false;
        for (char c : s.toCharArray())
            if (c < '0' || c > '9') return false;
        return true;
    }

    public static void main(String[] argv) {
        String[] readings = {"12", "x", "40", "?", "8"};
        int sum = 0, rejected = 0;
        for (String r : readings) {
            if (!isDigits(r)) { rejected++; continue; }   // an ordinary check, no exception
            sum += Integer.parseInt(r);
        }
        System.out.println("sum " + sum + ", rejected " + rejected);
    }
}
פלט
sum 60, rejected 2
טעויות נפוצות
  • catch בתוך לולאה עובד פעם אחת, ובסיבובים הבאים החריגות כבר לא נתפסות. כל סיבוב נכנס מחדש ל-try, וה-catch זמין בכל פעם.
  • javac דוחה catch שלא זורק את החריגה הלאה. אין דרישה כזו. catch שמטפל ומסיים הוא המקרה הרגיל.
  • חריגות שנתפסו מצטברות בזיכרון ויוצרות דליפה. אחרי הטיפול אין אליהן הפניות, וה-GC אוסף אותן.
  • ה-catch צריך להיות במתודה שונה מזו שזרקה, מערכת ההפעלה מתעדת אוטומטית כל חריגה, ותפיסה מבטלת את ההשמות שקדמו לה. שלוש הטענות שגויות, כפי שמראה הטבלה למעלה.
  • גם חריגה unchecked צריכה throws בכל מתודה שהיא עוברת בה. רק checked דורשות throws.
בדקו את עצמכם
תנו שתי סיבות לכך ש-break עדיף על throw כדרך לצאת מלולאת חיפוש.

throw יקר בהרבה, ורוב המחיר הוא רישום ה-stack trace. וחוץ מזה, קפיצה אל catch מרוחק מקשה לעקוב אחרי הזרימה, בזמן ש-break ממשיך בשורה שאחרי הלולאה.

לולאה רצה עם i מ-1 עד 10, ובכל סיבוב שבו i אי-זוגי נזרקת חריגה שנתפסת בתוך הלולאה. כמה פעמים ירוץ ה-catch?

5 פעמים, ב-i שווה 1, 3, 5, 7 ו-9. ה-catch זמין מחדש בכל סיבוב.

חזרה לתוכן העניינים

StackOverflowError: כשרקורסיה נגמרת בחריגה

הנה נקודת המפגש בין רקורסיה לחריגות. countDown בתוכנית הבאה מקבלת מינוס 1 ומחכה ל-0, אבל כל קריאה רק מרחיקה אותה ממנו, כך שמקרה הבסיס לא יגיע לעולם:

Java
public class CountDown {
    static int depth = 0;

    static long countDown(long n) {
        depth++;
        if (n == 0) return 0;             // never true when n starts below zero
        return 1 + countDown(n - 1);
    }

    public static void main(String[] argv) {
        try {
            try { countDown(-1); }
            catch (Exception e) { System.out.println("Exception handler"); }
        } catch (StackOverflowError e) {
            System.out.println("outer handler: " + e.getClass().getSimpleName());
            System.out.println("parent class: " + e.getClass().getSuperclass().getSimpleName());
            System.out.println("an Exception? " + (((Object) e) instanceof Exception));
            System.out.println("more than 1000 frames? " + (depth > 1000));
        }
    }
}
פלט
outer handler: StackOverflowError
parent class: VirtualMachineError
an Exception? false
more than 1000 frames? true

הריצה לא נתקעה לנצח כמו בלולאה אינסופית. כל קריאה הוסיפה מסגרת, ואחרי יותר מאלף מסגרות (השורה האחרונה בפלט) המחסנית, שגודלה מוגבל, התמלאה, וה-JVM זרק StackOverflowError.

ה-catch (Exception e) הפנימי לא הגיב בכלל, והשגיאה עברה דרכו אל ה-catch החיצוני. ההדפסות מסבירות למה: StackOverflowError יורשת מ-VirtualMachineError, שהיא Error, ולא Exception.

  • השורה parent class מראה VirtualMachineError, מהמשפחה של Error. לכן javac לא ביקש עבור countDown לא catch ולא throws: Error נחשבת unchecked.
  • השורה outer handler מוכיחה שהשגיאה הגיעה כאירוע גלוי. ה-JVM לא זיהה את הרקורסיה ועצר אותה בשקט, ומערכת ההפעלה לא סגרה את התהליך בלי מילה. בלי ה-catch החיצוני, ה-thread הראשי היה נגמר עם עקבות מחסנית ארוכות.
  • ה-catch החיצוני אמנם עבד, אבל הוא לא פתר כלום: countDown(-1) תיכשל שוב בכל ניסיון. לתפוס StackOverflowError ב-Java זה אפשרי, לא מועיל.
  • ו-Java לא הצילה את המצב בהמרה אוטומטית של הקריאות ללולאה, כי אין לה אופטימיזציה כזו.

ב-.NET המצב קשה יותר: StackOverflowException אי אפשר לתפוס בכלל, והיא מפילה את התהליך כולו. בתוכנית C# מקבילה, עם catch (Exception e) סביב הקריאה, מודפס Stack overflow ואחריו רשימת המסגרות החוזרות, והתהליך נגמר בלי שה-catch או השורה שאחריו רצו.

ב-Python את המגבלה אוכף הפרשן עצמו: מעבר לעומק המותר (ברירת המחדל היא 1000) נזרקת RecursionError.

Python
import sys

def climb(n):
    return climb(n + 1)    # no base case

print("limit:", sys.getrecursionlimit())
try:
    climb(0)
except RecursionError as e:
    print(type(e).__name__, "-", e)
פלט
limit: 1000
RecursionError - maximum recursion depth exceeded

מה כן עוזר? לתקן את הקוד עצמו. ב-countDown זה תנאי כמו n <= 0 במקום n == 0, כך שכל קלט מגיע לסיום, וכשהעומק הצפוי גדול מטבעו, למשל מיליון רמות, כותבים את האלגוריתם כלולאה.

תרחיש 18: עטיפה ב-catch שלא הצילה דבר

פונקציה רקורסיבית שסורקת עץ תיקיות עטופה ב-try { ... } catch (Exception e) { report(e); }. בתיקייה עמוקה במיוחד התוכנית נופלת בכל זאת, וב-stack trace מופיעה StackOverflowError.

ה-catch לא עזר, כי StackOverflowError נמצאת בענף של Error, שהוא אח של Exception תחת Throwable. catch (Exception e) פשוט לא מתאים לה.

מישהו מציע להחליף ל-catch (Throwable t). זה אכן יתפוס, אבל הסריקה עדיין לא תושלם: השגיאה רק תיבלע. התיקון הנכון הוא סריקה בלולאה, עם מחסנית מפורשת של תיקיות שממתינות לטיפול.

טעויות נפוצות
  • המחסנית מתרחבת לפי הצורך, ולכן בלי מקרה בסיס הפונקציה פשוט רצה לנצח. גודל המחסנית מוגבל, ובסופו של דבר נזרקת StackOverflowError.
  • ה-JVM מבחין ברקורסיה אינסופית וסוגר את התוכנית בלי לומר מילה, או שמערכת ההפעלה הורגת את התהליך בשקט. נזרקת שגיאה גלויה, ואם היא לא נתפסת מודפס stack trace.
  • זו Exception רגילה, אז catch (Exception e) יתפוס אותה ואפשר להמשיך. זו Error, ו-catch (Exception e) לא מתאים לה.
  • המהדר ידרוש להצהיר עליה ב-throws. Error היא unchecked. המהדר לא דורש דבר.
  • Java תמיר את הרקורסיה ללולאה ותמשיך בלי שגיאה. Java לא מבצעת המרה כזו, וכל קריאה תופסת מסגרת חדשה.
בדקו את עצמכם
ב-Java, האם catch (Error e) יתפוס StackOverflowError? ובקוד C# מקביל, האם catch (Exception e) יציל את התהליך מ-StackOverflowException?

ב-Java כן, כי StackOverflowError היא צאצאית של Error (אבל הבעיה עצמה לא נפתרה). ב-.NET לא: את החריגה הזו אי אפשר לתפוס, והתהליך נסגר.

חזרה לתוכן העניינים

סיכום

מה הקורא רואה אחרי שהמתודה סיימה?

  • שינוי בתוך אובייקט שהמתודה קיבלה, כמו שדה או תא במערך: נראה, כי הפרמטר הוא עותק של אותה הפניה. Java מעבירה רק By Value, ו-C# עושה כך כברירת מחדל.
  • הצבה חדשה לפרמטר, או שינוי של פרמטר פרימיטיבי: לא נראים. כדי להחזיר תוצאה ב-Java משתמשים בערך ההחזרה או בשדה של אובייקט עוטף.
  • s = s + "x" על String, או חישוב על Integer: לא נראה, כי הטיפוסים האלה אינם ניתנים לשינוי, והתוצאה היא אובייקט חדש.
  • ב-C#: שינוי בתוך struct לא נראה (ה-struct כולו הועתק), ושינוי בתוך אובייקט של class נראה. struct גדול מעבירים עם in (לקריאה בלבד) או עם ref, כדי לחסוך את ההעתקה.
  • עם ref או out הכול נראה, כי הפרמטר הוא כינוי למשתנה של הקורא. את שתי המילים כותבים גם בשורת הקריאה.

מה ייעצר עוד לפני הריצה?

  • ב-C#: משתנה בלי ערך שמועבר ב-ref (CS0165), מתודה עם out שלא מציבה ערך באחד הנתיבים (CS0177), וקריאה של פרמטר out לפני שהוצב בו ערך (CS0269).
  • ב-Java: חריגה checked שלא נלכדת ולא מוכרזת ב-throws. RuntimeException, Error וצאצאיהן פטורות; שתיהן, Error ו-Exception, הן אחיות תחת Throwable. ב-C# אין חריגות checked כלל.
  • בשתי השפות: catch רחב שמופיע לפני catch צר מאותה משפחה. הצר תמיד קודם, ו-multi-catch עם | מאחד טיפוסים שמקבלים תגובה זהה.
  • return בתוך finally ב-C# (CS0157). ב-Java זה עובר הידור, אבל דורס את ערך ההחזרה ומעלים חריגות.
  • שגיאות תחביר. טעויות לוגיות, לעומת זאת, לא ייעצרו לא בהידור ולא ב-catch.

מה קורה בזמן ריצה כשמשהו נכשל?

  • נוצרת חריגה, אובייקט שמתאר את התקלה. try תוחם את הקוד, catch מגיב, finally מנקה.
  • שלם חלקי אפס זורק ArithmeticException ב-Java ו-DivideByZeroException ב-C#, וב-double מקבלים Infinity או NaN בלי חריגה.
  • החריגה עולה ממתודה לקוראת שלה עד ה-catch הראשון שמתאים לה (הטיפוס או אב שלו). בלי catch כזה, ב-Java נגמר ה-thread עם עקבות המחסנית (ב-main קוד היציאה הוא 1), וב-.NET נגמר התהליך כולו.
  • finally רץ בכל יציאה מה-try, כולל return, ומדלג רק כשהתהליך עצמו מסתיים. try-with-resources (עם AutoCloseable) ו-using (עם IDisposable) סוגרים משאבים לבד, מהאחרון לראשון.
  • ב-C#, throw; מעביר חריגה הלאה עם המקור שלה, ו-throw ex; מוחק את המקור מעקבות המחסנית.
  • ברקורסיה כל קריאה מקבלת מסגרת משלה, והזיכרון גדל עם העומק. מקרה הבסיס נבדק בראש המתודה, לכל מקרה בסיס תנאי משלו, וכל צעד חייב להתקרב אליו.
  • רקורסיה שלא מגיעה למקרה בסיס ממלאת את המחסנית: StackOverflowError ב-Java (מסוג Error, וגודל המחסנית נקבע ב--Xss), RecursionError ב-Python מעל עומק 1000.
  • כשעוקבים אחרי פלט רקורסיבי, הדפסה שלפני הקריאה יוצאת בירידה פנימה, והדפסה שאחריה יוצאת בעלייה חזרה, בסדר הפוך.

מה עולה ביוקר, ומה מתקן?

  • פיבונאצ'י רקורסיבי נאיבי: 9 קריאות ל-fib(4), 15 ל-fib(5), כ-331 מיליון ל-fib(40). Memoization או לולאה מורידים אותו ל-O(n).
  • רקורסיית זנב, שבה הקריאה היא הפעולה האחרונה, לא תציל מעומק גדול: Java לא ממטבת אותה, C# לא מבטיחה, ו-CPython אף פעם לא.
  • רקורסיה עמוקה מאוד ממירים ללולאה, אם צריך עם מחסנית מפורשת על הערימה. -Xss, -Xmx, catch ו-Memoization לא פותרים את השורש.
  • חריגה ככלי לזרימה רגילה: איסוף עקבות המחסנית יקר, והקפיצה מקשה לקרוא את הקוד. if, break ו-return עדיפים.
  • חריגה מותאמת, שיורשת מ-Exception או מ-RuntimeException, לא חוסכת זמן ריצה. היא קונה בהירות: שם מדויק, catch מדויק ושדות משלה.