Java/רקורסיה

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

רקורסיה פשוטה

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

public class Recursion {
	public static void printMe()
	{
		System.out.println("Printing...");
		printMe();
	}
	
	public static void main(String[] args) {
		printMe();
	}
}

חכו עד שהתוכנית תיעצר מעצמה. מה קרה?

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

public class Recursion {
	public static void printMe(String s)
	{
		System.out.println(s);
		printMe(s.substring(1));
	}
	
	public static void main(String[] args) {
		printMe("This is my string");
	}
}

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

public class Recursion {
	public static void printMe(String s)
	{
		if(s.length()>0)
		{
			System.out.println(s);
			printMe(s.substring(1));
		}
	}

	public static void main(String[] args) {
		printMe("This is my string");
	}
}

הסבר

התוכנית הראשונה היא פשוטה מאוד, פרט לחריגה אחת: השיטה printMe קראה לעצמה. בכל קריאה כזו התחילה השיטה מהתחלה, כאילו קראנו לה משיטה אחרת. כל פעם בוצעה פקודת ההדפסה שבשיטה, ואז קריאה נוספת. עם זאת, בניגוד לצפוי, התוכנית נעצרה עם הפלט Exception in thread "main" java.lang.StackOverflowError מדוע זה נגמר, ולא נמשך עד אין סוף, כמו לולאת while אינסופית?

הדמייה של פעולת המחסנית

כדי להבין את הסיבה לכך, צריך להכיר את התהליך שנמצא מאחורי הקלעים. בכל פעם שאנו קוראים לשיטה, המחשב שומר בזכרונו את המצב האחרון בו היינו. אם, למשל, קראנו פעם אחת לשיטה "printMe" מה-main, המחשב שומר בזכרונו את המצב האחרון בו הייתה ה-main - באיזו שורה היינו, מה מצב המשתנים המקומיים שלה, וכן הלאה. אם השיטה לה קראנו קראה לשיטה נוספת - גם מצבה של זו נשמר, וכן הלאה. כל המידע הזה נשמר במבנה מיוחד הנקרא "מחסנית" (באנגלית - Stack), בו הנתון האחרון שנכנס - הוא הנתון הראשון שיוצא. כשמסתיימת פעולתה של שיטה - היא נמחקת מהמחסנית. בתוכנית שלנו, התבצעה קריאה חוזרת לאותה השיטה, ללא הפסקה. כל קריאה כזו התווספה למחסנית, עד שזו כרעה תחת הנטל, וקרסה יחד עם התוכנית.

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

מבנה הרקורסיה

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

שיטה רקורסיבית שמחזירה ערך

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

public class Recursion {
	public static int sum(int n)
	{
		if(n<1)
			return 0;
		else
		{
			return n+sum(n-1);
		}
	}

	public static void main(String[] args) {
		System.out.println(sum(3));
	}
}

נעקוב במפורט אחרי הפעולות שהתבצעו:

1. ה-main קראה לשיטה sum עם הארגומנט 3.
2. בתחילת פעולת השיטה התבצעה הבדיקה: האם הארגומנט שקיבלנו - n - קטן מ-1? מאחר והתשובה שלילית, המשיכה התוכנית הלאה.
3. התוכנית מגיעה לפקודת return, אך צריכה להחזיר ערך שלא ידוע עדיין: הסכום של n - אותו אנחנו כבר יודעים, עם התוצאה של השיטה sum על הערך 2. ערך ההחזרה כרגע הוא 3 ועוד sum(2).
4. מתבצעת קריאה רקורסיבית לשיטה sum, והפעם ערכו של n הוא 2. גם כאן לא ענינו על התנאי n<1, לכן ממשיכים הלאה - אל הפקודה return. במחסנית שמורה הקריאה הקודמת, בה n=3.
5. ערך נוסף להחזיר: 2 ועוד sum(1). מתבצעת קריאה רקורסיבית נוספת, ואל המחסנית נוספת הקריאה בה n=2.
6. הפעם ערכו של n הוא 1, ובאופן דומה למה שכבר ראינו, מתבצעת קריאה רקורסיבית נוספת, עם הערך 0. גם הקריאה הזו מצטרפת למחסנית.
7. התוכנית נעצרת הפעם בתנאי: n הוא קטן מ-1, לכן התוכנית מחזירה 0, וחוזרת שלב אחד אחורה: הקריאה בה n=1 נשלפת מהמחסנית.
8. החישוב ממשיך: 1 ועוד sum(0) שווה ל-1, וזה הערך של sum(1). ממשיכים לטפס: הערך עבור הקריאה בה n=1 הוא 1 (1+0), הערך עבור הקריאה בה n=2 הוא, לכן, 3 (2+1), והערך עבור הקריאה n=3 הוא 6 (3+3).
9. סיימנו - כל הקריאות שהיו במחסנית נמחקו, ואפשר לחזור אל ה-main, שם מודפס הפלט - 6.

כיוון אחר

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

public class Recursion {

	public static void backwards(int arr[] , int n) {
		if(n>arr.length-1)
			return;
		backwards(arr, n+1);
		System.out.println(arr[n]);
	}

	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4};
		backwards(arr, 0);
	}
}

התהליך כאן הוא קצת שונה. השיטה קראה לעצמה לפני ההדפסה. השיטות שנקראו החלו להיצבר על המחסנית, עד שהתוכנית הגיעה לתנאי העצירה. בשלב זה, לא התבצעה קריאה חוזרת אלא הסתיימה מיד פעולת השיטה, בעזרת הפקודה return, והקריאה הזו נמחקה מהמחסנית. התוכנית, אם כך, חזרה שיטה אחת לאחור (במחסנית), בדיוק אל המקום בו הייתה קודם: פקודת ההדפסה. פקודת ההדפסה הזו התרחשה לגבי n=3, לכן האיבר הראשון שמודפס הוא האיבר הרביעי. בשלב זה הסתיימה פעולת הקריאה הזו, ושוב נשלפה שיטה מהמחסנית - הפעם זו בה n=2, והאיבר השלישי הודפס. כך המשיכה התוכנית עד שהתרוקנו כל הקריאות מהמחסנית.

קריאה כפולה

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

public class Recursion {
	public static int fibo(int n)
	{
		if(n==1 || n==2)
			return 1;
		int num1 = fibo(n-1);
		int num2 = fibo(n-2);
		return num1 + num2;
	}

	public static void main(String[] args) {
		int n = 7;
		System.out.println("Element number "+n+" is "+fibo(n));
	}
}

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

חסרונות ויתרונות

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

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

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

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

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

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

עוד על רקורסיה

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

הפרק הקודם: שיטות

רקורסיה תרגילים

הפרק הבא: בדיקת שגיאות