רקורסיה חלק ד’ – איך להפוך לולאה לרקורסיה

הפוסט הקודם בסדרה – רקורסיה חלק ג’ – קופסא שחורה

היי לכולן!

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

שיטה שלישית – “תרגום מלולאה לרקורסיה”

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

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

יש כמובן שתי בעיות עם הגישה הזו –

1. אם ניתן לפתור את הבעיה בעזרת לולאה, אז אין באמת סיבה לתרגם לרקורסיה, זה יוצר עבודה כפולה.
2. אם לא ניתן לפתור את הבעיה בעזרת לולאה – האם נצליח לייצר את הרקורסיה לבד?

התשובה לשאלה הראשונה היא – כן, זו עבודה כפולה, וזה מיותר, אבל כיוון שאנחנו בשלב הלימודי, כל מה שעובד הוא טוב. 

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

אז בואו נחזור לתרגיל שאנחנו רוצות לפתור – מימוש אלגוריתם contains שבודק האם מספר x נמצא במערך בגודל n.

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

contains(arr, x):
	for i in range(0,len(arr)):
		if arr[i] == x:
			return True
	return False

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

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

הפונקציה הרקורסיבית שלי תיראה בערך ככה –

contains_rec(arr, i, x):
 
	if arr[i] == x:
		return True
	return contains_rec(arr, i+1, x)

שימו לב ששורות 3-4, שהן שורות הלוגיקה של הלולאה נשארו זהות בשתי הפונקציות.

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

עכשיו כל מה שנשאר הוא להוסיף את הקריאה הראשונה לפונקציה. הפונקציה contains_rec צריכה שיקראו לה מבחוץ עם האינדקס הראשון – 0, כי היא לא מאתחלת את האינדקס בעצמה.

contains_rec(arr, i, x):
	if arr[i] == x:
		return True
	return contains_rec(arr, i+1, x)
 
contains(arr, x):
	return contains_rec(arr, 0, x)

בואו נבדוק אם האלגוריתם שלנו עובד!

arr = [3,10]
contains([3,10], 8):
 return contains_rec([3,10], 0, 8)
 
contains_rec([3,10], 0, 8):
 arr[0] == 8 → False
 return contains_rec([3,10], 1, 8)
 
contains_rec([3,10], 1, 8):
 arr[1] == 8 → False
 return contains_rec([3,10], 2, 8)
 
contains_rec([3,10], 1, 8):
 arr[2] == 8 ← ERROR

אופס, קיבלנו שגיאה.
למה? כי לא הוספנו לאלגוריתם הרקורסיבי את הסוף של הלולאה.
נכון בלולאת for אנחנו רצות על כל האיברים מ-0 ועד len(arr)? אז אותו תנאי צריך להתקיים גם פה, אנחנו צריכות לעצור כשהאינדקס שלנו יגיע לגודל המערך.

נוסיף את הבדיקה הזו (שהיא בעצם תנאי העצירה של הפונקציה) לאלגוריתם שלנו –

contains_rec(arr, i, x):
	if i == len(arr):
		return False
	if arr[i] == x:
		return True
	return contains_rec(arr, i+1, x)
 
contains(arr, x):
	return contains_rec(arr, 0, x)

נפלא!
בואו נריץ את הבדיקה שלנו שוב – 

arr = [3,10]
contains([3,10], 8):
 return contains_rec([3,10], 0, 8)
 
contains_rec([3,10], 0, 8):
 0 == 2 → False
 arr[0] == 8 → False
 return contains_rec([3,10], 1, 8)
 
contains_rec([3,10], 1, 8):
 1 == 2 → False
 arr[1] == 8 → False
 return contains_rec([3,10], 2, 8)
 
contains_rec([3,10], 2, 8):
 2 == 2 → True
 return False
 
contains_rec([3,10], 1, 8):
return contains_rec([3,10], 2, 8) False
 
contains_rec([3,10], 0, 8):
 return contains_rec([3,10], 1, 8) False
 
contains([3,10], 8):
return contains_rec([3,10], 0, 8) False

הידד!
יש לנו אלגוריתם רקורסיבי מבוסס לולאה להתגאות בו.

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

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

פוסטים נוספים בסדרת הרקורסיות