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), ונעלם יחד איתה כשהמתודה חוזרת.
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 ולתת לקורא לבצע את ההשמה בעצמו:
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
170exchange החליפה רק בין 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) | לא, רק העותק של ההפניה הוסט |
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.
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 errorref ו-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 הוא אובייקט שחי בערימה, ולכן שני הכללים מהחלק הקודם חלים עליו כמו שהם. כתיבה לתא דרך הפרמטר מגיעה למערך של הקורא, והצבה של מערך אחר בפרמטר מסיטה רק את העותק של ההפניה.
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 כותב לתוכו.
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 יש לכך שני פתרונות שמקובל להשתמש בהם:
- להחזיר את הערך מהמתודה ולתת לקורא להציב אותו, כמו
points = withBonus(points). זו הדרך הפשוטה והקריאה ביותר כשמדובר בערך אחד. - לעטוף את הערך באובייקט שניתן לשנות: מחלקה קטנה עם שדה יחיד, או מערך בגודל 1, ולשנות בתוך המתודה את השדה או את התא.
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 | ההפניה בלבד | נוחת על האובייקט המשותף, והקורא רואה אותו |
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 200px.R נשאר 0, ערך ברירת המחדל של שדה int. המתודה כתבה 200 לתוך השכפול של המבנה, והשכפול נעלם בסוף הקריאה.
כמה שאלות על השכפול הזה חוזרות שוב ושוב. הנה התשובות, מרוכזות:
| שאלה | התשובה עבור struct בהעברה רגילה |
|---|---|
| מתי נוצר השכפול? | ברגע הקריאה, בכל קריאה, גם כשהמתודה רק קוראת מהמבנה ולא כותבת בו |
| האם ה-CLR (סביבת הריצה של .NET) מחליף אותו בהפניה כדי לחסוך? | לא, המבנה מועתק כפי שהקוד ביקש |
| כמה זה עולה? | כל השדות מועתקים, לעומת כתובת אחת בהעברה של class. במבנה גדול ההבדל מורגש |
| איך חוסכים? | מעבירים עם in (מ-C# 7.2, הפניה לקריאה בלבד) או עם ref |
| ומה אם המבנה מחזיק שדה מטיפוס class? | מועתקת ההפניה שבשדה, והאובייקט עצמו נשאר משותף (הדוגמה הבאה) |
| האם יש כאן boxing? | לא. boxing, אריזה של טיפוס ערך בתוך אובייקט בערימה, קורה רק כשממירים את המבנה ל-object או לממשק |
הדוגמה הבאה ממחישה את השורה של שדה ה-class: מבנה Order שמחזיק הפניה ללקוח עובר למתודה שמשנה גם את הכמות וגם את שם הלקוח.
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 שהקורא מחזיק, ולכן הוא נשאר: השכפול שטחי.
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 באותה חתימה:
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 90fee הוכפל בתוך המתודה, אבל רק בעותק, ולכן הקורא מדפיס 5. ההפחתה מ-balance נעשתה ישירות במשתנה של הקורא, ולכן נשארו 90.
גם החלפה בין שני משתנים, שב-Java לא הייתה אפשרית, עובדת עם ref:
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 northref הוא חלק מהחוזה של המתודה, ולכן צריך לכתוב אותו גם בצד הקורא. כשמשמיטים אותו, ההידור נכשל:
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' keywordref ומשתנה בלי ערך. מתודה שמקבלת ref רשאית לקרוא את מה שכבר נמצא במשתנה, ולכן חייב להיות שם ערך. ב-C# משתנה מקומי שהוצהר בלי השמה לא מחזיק אפילו 0, כך שהמהדר עוצר את הקריאה:
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" כאן:
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 לפני ההצבה הראשונה בו נחסמת:
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 מתאים לכל טיפוס, גם לטיפוס הפניה:
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
80in: לקרוא בלי להעתיק. מתודה שמקבלת פרמטר in מקבלת גישה ישירה למשתנה של הקורא, אבל המהדר מתייחס אליו כאל readonly. זה הכלי המתאים כשמבנה גדול צריך להגיע למתודה שרק קוראת ממנו, בלי לשכפל את כל השדות שלו:
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 הוא רשות. שתי הצורות מתקמפלות ונותנות אותה תוצאה:
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 10ref מול struct ומול class. כשהפרמטר הוא struct, ref הוא מה שמביא שינוי שדה אל המבנה של הקורא, כי בלעדיו המתודה עובדת על שכפול:
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 נחוץ רק כשהמתודה רוצה להשאיר בידי הקורא אובייקט אחר לגמרי:
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 guestref או 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 כפול העצרת של המספר שמתחתיו.
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, ומאותו רגע רק ממשיך לרדת.
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).
על כל פתק כתובים הערכים שהמתודה קיבלה, המשתנים שהגדירה, ולאן לחזור כשתסיים. זה נכון לכל מתודה שמופעלת, לא רק לרקורסיה. התוכנית הבאה מאפשרת לראות את הפתקים:
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() | איסוף הזבל מנקה אובייקטים בערימה. מסגרות של הפעלות פתוחות אינן זבל, והוא לא נוגע בהן |
לסמן את הפרמטר final | final רק אוסר להשים לפרמטר ערך חדש |
להגדיר את המתודה static | גם מתודה סטטית מקבלת מסגרת בכל הפעלה, בדיוק באותו אופן |
להחליף int ב-short או ב-long | מספר ההפעלות לא משתנה, ולכן גם העומק לא |
| לפצל לשתי מתודות שמפעילות זו את זו | המחסנית שייכת ל-thread ולא למתודה, ושתיהן נערמות על אותה מחסנית |
תרחיש 7: המחסנית של חזקה, מסגרת אחר מסגרת
המתודה pow(b, e) מחזירה 1 כש-e שווה 0, ואחרת מחזירה b * pow(b, e - 1). מה קורה במחסנית בקריאה pow(2, 3)?
- main מפעילה את
pow(2, 3). נוספת מסגרת עם e = 3, והיא נעצרת באמצע הביטוי, כי הכפל צריך את התשובה שלpow(2, 2). - באותה צורה נוספות מסגרות עם e = 2, e = 1 ולבסוף e = 0. ברגע השיא יש מעל main ארבע מסגרות של pow, וכל אחת מחזיקה e משלה.
- המסגרת של e = 0 פוגשת את מקרה הבסיס, מחזירה 1 ויורדת מהמחסנית.
- המסגרת של 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 את החריגה הזו אי אפשר לתפוס, והתהליך כולו מסתיים.
מעקב אחרי קוד רקורסיבי: מה יופיע בפלט
השאלה הנפוצה ביותר על רקורסיה מבקשת לכתוב את הפלט. המפתח לפתרון הוא לבדוק איפה עומדת ההדפסה ביחס להפעלה העצמית.
- הדפסה לפני הקריאה רצה בדרך פנימה, בזמן שהשרשרת מעמיקה. הסדר הוא מההפעלה החיצונית אל הפנימית.
- הדפסה אחרי הקריאה מחכה עד שההפעלה הפנימית מסיימת. היא רצה בדרך חזרה, ולכן הסדר מתהפך.
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) | 3 | 3 |
mirror(2) | 2 | 2 |
mirror(1) | 1 | 1, פותח את החצי השני |
mirror(0) | כלום, יוצאת מיד | אין |
כדי להפוך את הטבלה לפלט, יורדים פעם אחת בעמודה "מדפיסה בכניסה", משורת mirror(4) עד שורת mirror(1), ומקבלים 4 3 2 1. אחר כך מטפסים בעמודה "מדפיסה ביציאה" מ-mirror(1) חזרה אל mirror(4), ומקבלים 1 2 3 4. הטעות הנפוצה היא לקרוא גם את עמודת היציאה מלמעלה, כאילו mirror(4) מסיימת ראשונה, אף שבפועל היא ממתינה לכל השורות שמתחתיה.
במתודה שמחזירה ערך אין הדפסות לעקוב אחריהן, אבל אותו רעיון עובד באלגברה פשוטה: כותבים את הקריאה כשוויון, מחליפים כל קריאה פנימית בביטוי שהיא מחשבת, ומציבים מספרים רק כשמגיעים לקצה.
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: ביטוי שמפרק מספר ומרכיב אותו מחדש
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, ושולחת את שאר המספר פנימה:
dropZeros(4050): last = 0, ממתינה ל-dropZeros(405).dropZeros(405): last = 5, ממתינה ל-dropZeros(40).dropZeros(40): last = 0, ממתינה ל-dropZeros(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 מפעילה חזרה את A | isEven(n) שמפעילה את isOdd(n - 1), וההפך |
| רקורסיית זנב (tail recursion) | ההפעלה העצמית היא הצעד האחרון, ושום חישוב לא מחכה לתוצאה שלה | חזקה עם צובר, בתת-הפרק הבא |
ברקורסיה כפולה האויב הוא עבודה שחוזרת על עצמה: שני ענפים שונים בעץ מגיעים לאותה תת-בעיה, וכל אחד פותר אותה מאפס. כך זה נראה בפיבונאצ'י הנאיבי:
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), כשכל שורה היא הפעלה אחת:
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) מחושבת בו פעם אחת, אבל בעץ המלא היא מחושבת פעמיים, כי לכל ענף אין מושג מה הענף השני כבר מצא.
כמה מהר זה גדל? הוספנו מונה הפעלות והרצנו:
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, שראיתם בפלט למעלה, או לולאה שבונה את הסדרה מלמטה עם שני משתנים:
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 לפי אוקלידס.
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תלשו מעץ את השורש, ומה שנשאר הם שני עצים נפרדים, שמאלי וימני. השאלה "האם יש בעץ ערך שלילי" מתפרקת לכן לבדיקה של צומת אחד ולאותה שאלה בדיוק על שני העצים שנותרו, וזה בדיוק מה שמתודה רקורסיבית יודעת לעשות בכמה שורות.
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 בגרסה הנאיבית לוקח כמה שניות טובות, ומישהו בטוח שמשהו נשבר. בודקים את החשודים אחד אחד.
- גלישת int? לא. 102334155 נכנס בטווח, וגם אילו לא היה נכנס, Java לא הייתה זורקת בגלל זה חריגה.
- גלישת מחסנית? לא. העומק המרבי הוא 40 מסגרות, והתוכנית בכלל לא נופלת. היא רק איטית.
- חישוב חוזר? כן. אותם ערכים נפתרים שוב ושוב בענפים שונים, ומצטברים ליותר מ-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).
מיקום הקריאה בקוד לא מכריע. גם קריאה בשורה האחרונה של המתודה אינה בזנב אם כפל, חיבור או השוואה ממתינים לתוצאה שלה.
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:
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):
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 כבר לא מגביל את העומק |
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. תנאי העצירה תקין לגמרי. הבעיה היא ששלושה מיליון מסגרות פתוחות לא נכנסות במחסנית.
הצוות מחפש פתרון שלא תלוי בכמה מחסנית הוקצתה. התשובה היא לולאה שבה משתנה אחד צועד אחורה בהיסטוריה:
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, וזה מצליח רק אם הטקסט הוא באמת מספר:
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 מיותר | לא. אזהרה אינה מונעת הרצה ואינה חריגה |
שני הרגלים רעים שכדאי להימנע מהם:
- 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 במערך של שני תאים. עקבו אחרי הפלט:
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 (עקבות המחסנית): רשימת המתודות שהיו פתוחות, מהעמוקה ביותר החוצה.
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):
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, ושום דבר לא נזרק.
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? trueusing 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 החדשות מציגות את האינסוף כסימן ∞, אבל זה אותו ערך בדיוק. הטבלה מרכזת את הזוגות שכדאי להכיר בשתי השפות:
| מה קרה | Java | C# |
|---|---|---|
| שלם חולק בשלם שערכו 0 | ArithmeticException | DivideByZeroException |
| הפעלת מתודה או גישה לשדה דרך null | NullPointerException | NullReferenceException |
| אינדקס שחורג מגבולות המערך | ArrayIndexOutOfBoundsException | IndexOutOfRangeException |
| המרת אובייקט לטיפוס שאינו מתאים לו | ClassCastException | InvalidCastException |
| טקסט שאינו מספר הומר למספר | NumberFormatException (מ-Integer.parseInt) | FormatException (מ-int.Parse) |
| ערך פסול הועבר כארגומנט | IllegalArgumentException | ArgumentException, ומשפחתה כמו 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 או של מחלקה שיורשת ממנה. זה העץ שחשוב להכיר:
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
+-- StackOverflowErrorError ו-Exception. בעץ שלמעלה הן נמצאות באותה קומה: שתיהן ילדות של Throwable, ואף אחת לא יורשת מהשנייה.
ההבדל ביניהן הוא במי שאמור להגיב. Error מדווחת שהמכונה הווירטואלית עצמה בצרה, למשל כשאין עוד מקום בערימה או במחסנית, ובשלב הזה לקוד האפליקציה אין דרך סבירה לתקן את המצב. Exception מדווחת על בעיה שהקוד שלכם יכול לצפות, להגיב לה ב-catch, ולהמשיך לעבוד.
checked מול unchecked (חריגה בדוקה מול לא בדוקה). ההבחנה עונה על שאלה אחת: האם javac יסרב לקמפל קוד שמתעלם מהחריגה. במקום לשנן רשימות, אפשר לשאול על כל מחלקה שאלה פשוטה, וזה מה שהתוכנית הבאה עושה: האם יש לה אב קדמון RuntimeException או Error?
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:
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 של המתודה.
יש שתי דרכים לרצות את המהדר: לטפל במקום, או להצהיר ולהעביר את ההחלטה למי שקורא למתודה.
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, ולכל אחד תגובה משלו: לבקש מהמשתמש קובץ, לנסות שוב, או להתריע.
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#:
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 errorusing 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 אפשר לרכז כמה טיפוסים בבלוק אחד, מופרדים בקו אנכי |, כשהתגובה לכולם זהה:
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) נכנס לפעולה רק אם הטיפוס מתאים וגם התנאי מתקיים. אחרת החריגה ממשיכה הלאה, כאילו הבלוק לא קיים.
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 ... שוב ושוב, כלומר לכתוב ידנית את מה שבלוקים נפרדים נותנים מעצמם.
תרחיש 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.
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.
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 מנסה לשנות את מה שמוחזר:
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, וגרוע מזה, מעלים חריגה שהייתה בדרך החוצה:
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:
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 clausetry-with-resources. מאז Java 7 אפשר לפתוח משאב בתוך הסוגריים של ה-try עצמו. בסוף הבלוק, איך שלא יסתיים, Java מפעילה בשבילכם את close() של המשאב, ולכן אין צורך לכתוב finally רק בשביל הסגירה.
המחלקה Channel שבדוגמה לא יורשת מאף מחלקה מיוחדת. מה שמכשיר אותה לשבת בסוגריים הוא implements AutoCloseable, הממשק שמגדיר את close.
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 החיצוני רץ:
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:
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 moreQuotaExceededException בדוגמה יורשת מ-Exception, ולכן היא checked, ו-upload חייבת להכריז עליה ב-throws. אילו הייתה יורשת מ-RuntimeException היא הייתה unchecked, ושני הכיוונים מקובלים ב-Java. ב-C# יורשים תמיד מ-Exception, ושאלת ה-checked לא קיימת שם.
המחלקה מעבירה הודעה לבנאי של האב ומוסיפה שדה משלה, כך שה-catch יכול להציע ללקוח בדיוק כמה מקום חסר לו.
| השאלה | התשובה עבור QuotaExceededException |
|---|---|
| האם הלוג יגיד מה קרה? | כן. השם עצמו מספר שמדובר בחריגה ממכסה, בלי לפענח הודעה |
| אפשר להגיב רק לה ולא לתקלות אחרות? | כן. catch (QuotaExceededException e) לא ילכוד שום חריגה אחרת |
| אפשר להעביר נתונים ל-handler? | כן. השדה overByMb הגיע ל-catch והפך להצעה ללקוח |
| האם התוכנית תרוץ מהר יותר? | לא. בדיקת המכסה עדיין רצה, ונוספה עוד מחלקה |
| האם רק בזכותה יש stack trace? | לא. גם Exception רגילה נושאת עקבות מחסנית מהרגע שנוצרה |
| האם זה כלי לשגיאות הידור או לשפה בלי חריגות? | לא. זו חריגה רגילה שנזרקת בזמן ריצה |
עטיפה (wrapping). כשמתרגמים חריגה טכנית לחריגה ברמה גבוהה יותר, מעבירים את המקורית כסיבה, כדי שהמידע עליה לא יאבד. ב-Java זה הארגומנט השני בבנאי, new X(message, cause), וב-C# המאפיין InnerException.
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 היא המקום שבו החילוק באפס קרה בפועל:
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 itthrow;הדפיס 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 רגיל:
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 אוסף אותה כשאין אליה הפניות, בלי דליפה |
| האם מערכת ההפעלה שומרת תיעוד של כל חריגה שנזרקה? | לא. תיעוד קיים רק אם הקוד שלכם או ספרייה כותבים אותו ללוג |
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 כמעט בכל סיבוב.
תרחיש 17: ייבוא לילי של חצי מיליון מזהים
תהליך לילי קורא חצי מיליון מזהים מקובץ, וממיר כל אחד ב-Integer.parseInt בתוך try שבתוך הלולאה. אחרי שינוי אצל הספק, רוב השורות מגיעות עם קידומת טקסט.
פתאום התהליך נמשך פי כמה: כמעט כל סיבוב זורק NumberFormatException ואוסף stack trace.
התיקון: בדיקה רגילה לפני ההמרה, שהמחרוזת לא ריקה ומכילה ספרות בלבד, ו-continue כשהיא לא עוברת. החריגה נשמרת רק למה שבאמת לא צפוי.
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, אבל כל קריאה רק מרחיקה אותה ממנו, כך שמקרה הבסיס לא יגיע לעולם:
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.
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 מדויק ושדות משלה.