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

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

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

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

דוגמאות – 

arr = [3, 8, 10]
contains(arr, 3) = True
contains(arr, 4) = False

שיטה ראשונה – “מהסוף להתחלה”

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

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

איך בוחרות תנאי עצירה?
תנאי עצירה טוב הוא כזה ש-

1. את יודעת בוודאות מה הוא אמור להחזיר.
2. הוא מכסה את כל מקרי הקצה שלך.

במקרה של פונקציית ה- sum תנאי העצירה שלי היה מערך באורך אפס, כי אני יודעת ש-

1. מערך באורך אפס הוא מערך ריק, וסכום האיברים במערך ריק הוא אפס.
2. הוא מכסה את כל מקרי הקצה שלי, כי לא יכול להיות לי מערך באורך קטן מאפס.

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

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

contains(arr, x):
  if len(arr) == 0:
    return False 

יאי, התחלה מצוינת. מה עכשיו?

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

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

אז איך אנחנו בודקות אם מספר נמצא במערך באורך 1? מאוד בקלות, אנחנו בודקות אם האיבר היחיד במערך שווה למספר שאנחנו מחפשות, ומחזירות True או False בהתאם.

כלומר – 

if arr[0] == x:
  return True
else:
  return False

כמובן שבצורה המקוצרת והנוחה אנחנו יכולות לכתוב – 

return arr[0] == x

אחלה. בואו נוסיף את השלב הזה לאלגוריתם שלנו – 

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

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

if len(arr) == 2:
  return arr[0] == x or arr[1] == x

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

אז איך האלגוריתם שלי נראה עכשיו?

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

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

if len(arr) == 3:
  return arr[0] == x or arr[1] == x or arr[2] == x

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

contains(arr, x):
  if len(arr) == 0:
    return False
  elif len(arr) == 1:
    return arr[0] == x
  elif len(arr) == 2:
    return contains(arr[0:1],x) or arr[1] == x
  elif len(arr) == 3:
    return contains(arr[0:2],x) or arr[2] == x

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

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

אם אתן לא מכירות את צורת הכתיבה שהשתמשתי בה כדי “לחתוך” את המערכים אתן יכולות לקרוא עליה פהhttps://towardsdatascience.com/the-basics-of-indexing-and-slicing-python-lists-2d12c90a94cf.

עכשיו, כדי לשכנע את עצמנו שהאלגוריתם אכן פועל, נריץ עליו דוגמא –

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

contains([3,8], 8|):
  len([3, 8]) == 0 → False
  return contains([3], 8) or 8 == 8

contains([3], 8):
  len([3]) == 0 → False
  return contains([], 8) or 3 == 8

contains([], 8):
  len([]) == 0 → True
  return False

contains([3], 8):
  len([3]) == 0 → False
  return contains([], 8) False or 3 == 8 = False

contains([3,8], 8|):
  len([3, 8]) == 0 → False
  return contains([3], 8) False or 8 == 8 = True

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

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

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

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

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

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

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

בשאלות של מערכים – תנאי העצירה בדרך כלל יהיה מערך ריק.
בשאלות של מספרים – תנאי העצירה בדרך כלל יהיה כשנגיע ל-0 (או לפעמים 1).
בשאלות של עצים – תנאי העצירה יהיה כשנגיע לעלה.

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

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

if len(arr) == 1:
	if arr[0] == x:
		return True
	else:
		return False

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

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

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