רקורסיה חלק ג’ – קופסא שחורה

הפוסט הקודם בסדרה – רקורסיה – חלק ב’ – כתיבת אלגוריתם רקורסיבי מהסוף להתחלה

היי לכולן!

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

שיטה שנייה – “הקופסא השחורה”

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

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

אז בואו נחזור לתרגיל שאנחנו רוצות לפתור – מימוש אלגוריתם contains שבודק האם מספר נמצא במערך בגודל n. לפי שיטת הקופסא השחורה אנחנו יכולות להניח שכבר קיימת פונקציה, נקרא לה contains_part שמקבלת מערך בגודל n-1 ומספר, ומחזירה true אם המספר נמצא במערך, ו-false אם הוא לא נמצא במערך.

איך נוכל להשתמש בפונקציה contains_part כדי לדעת אם המספר שאנחנו מחפשות נמצאות במערך בגודל n?

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

contains(arr, x):
	arr_head = arr[0]
	arr_tail = arr[1:]
	return check(arr_head, x) or contains_part(arr_tail, x)

מה בדיוק עשיתי פה?
הנחתי שהמערך שלי הוא בגודל n, וחתכתי אותו שלי לשתי חתיכות – הראש הוא מערך באורך 1 שמכיל רק את האיבר הראשון. הזנב הוא מערך בגודל n-1 שמכיל את שאר האיברים.
עכשיו, אני יכולה להגיד שאם האיבר נמצא ב-arr_head או ב-arr_tail אז הוא בוודאות נמצא במערך.

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

אני אעדכן את הפונקציה שלי בהתאם.

contains(arr, x):
	arr_head = arr[0]
	arr_tail = arr[1:]
	return arr_head == x or contains_part(arr_tail, x)

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

arr = [3,8,10]
contains([3,8,10], 8):
  arr_head = 3
  arr_tail = [8,10]
  return arr_head == 8 or contains_part([8,10], 8)
 
contains_part([8,10], 8) → True 
 
contains([3,8,10], 8):
  return arr_head == 8 or contains_part([8,10], 8) True = True

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

עכשיו, בואו נבדוק מקרה קיצון – מה יקרה אם נרוץ על מערך ריק?

arr = []
contains(arr, 8):
  arr_head = arr[0] ← ERROR

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

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

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

contains(arr, x):
	if len(arr) == 0:
		return False
	arr_head = arr[0]
	arr_tail = arr[1:]
	return arr_head == x or contains_part(arr_tail, x)

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

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

הנה הוא, האלגוריתם הסופי שלנו –

contains(arr, x):
	if len(arr) == 0:
		return False
arr_head = arr[0]
	arr_tail = arr[1:]
	return arr[0] == x or contains(arr_tail, x)

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

arr = [3,8,10]
contains([3,8,10], 8):
len([3,8,10]) == 0 → False
  arr_head = 3
  arr_tail = [8,10]
  return arr_head == 8 or contains([8,10], 8)
 
contains([8,10], 8):
len([8,10]) == 0 → False
  arr_head = 8
  arr_tail = [10]
  return arr_head == 8 or contains([10], 8) → True
 
contains([3,8,10], 8):
  return arr_head == 8 or contains([8,10], 8) True = True

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

arr = [3,8,10]
contains([3,8,10], 1):
len([3,8,10]) == 0 → False
  arr_head = 3
  arr_tail = [8,10]
  return arr_head == 1 or contains([8,10], 1)
 
contains([8,10], 1):
len([8,10]) == 0 → False
  arr_head = 8
  arr_tail = [10]
  return arr_head == 1 or contains([10], 1)
 
contains([10], 1):
len([10]) == 0 → False
  arr_head = 10
  arr_tail = []
  return arr_head == 1 or contains([], 1)
 
contains([], 1):
  len([]) == 0 → True
  return False
 
contains([10], 1):
  return arr_head == 1 or contains([], 1) False = False
 
contains([8,10], 1):
  return arr_head == 1 or contains([8,10], 1) False = False
 
contains([3,8,10], 1):
  return arr_head == 1 or contains([8,10], 1) False = False

מצוין, קיבלנו False כמו שרצינו.

לסיכום

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

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

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

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

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