מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/חשיבה רקורסיבית

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס

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

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

מה היא רקורסיה?

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

# Calculates the factorial (atzeret).
# Takes a non-negative integer number (n).
Factorial(n)
1	ret = 1
	
2	for i in [1 … n]:
3		ret = ret * i
	
4	return ret

מהתבוננות בפונקציה, קל לראות שהיא מחזירה $1 \cdot 1 \cdot 2 \dots n = n!$ .

לחלופין, נוכל לכתוב את הפונקציה בצורה רקורסיבית, כך:

# Calculates the factorial (atzeret).
# Takes a non-negative integer number (n).
Factorial(n)
1	if n == 0
2		return 1
	
3	return n * Factorial(n - 1)

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

כיצד המהדר מתייחס לרקורסיה

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

בקריאה הראשונה תבנית:קוד בשורה.‏ 1 תכשל, ו2 לא תתבצע. 3 תחזיר כתשובה את 3 כפול הערך המוחזר מתבנית:קוד בשורה.
בקריאה זו תבנית:קוד בשורה.‏ 1 תכשל, ו2 לא תתבצע. 3 תחזיר כתשובה את 2 כפול הערך המוחזר מתבנית:קוד בשורה.
בקריאה זו תבנית:קוד בשורה.‏ 1 תכשל, ו2 לא תתבצע. 3 תחזיר כתשובה את 1 כפול הערך המוחזר מתבנית:קוד בשורה.
בקריאה זו תבנית:קוד בשורה.‏ 1 תצליח, ו2 תחזיר כתשובה את 1. ערך זה יוכפל ב1, התוצאה תוכפל ב2, והתוצאה תוכפל ב3.

הנקודה האחרונה מראה שמבחינת התוצאה המוחזרת, נקבל אותו הדבר כגרסת הלולאה. בשני המקרים נקבל $1 \cdot 1 \cdot 2 \cdot 3 \cdot = 3!$ .

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

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

כעת נראה דרך אחרת, אינדוקטיבית יותר.

גישה אינדוקטיבית

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

תבנית:הוכחה

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

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

תבנית:הארה

כעת נראה מספר דוגמאות לכך.

חישוב עצרת

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

# Calculates the factorial (atzeret).
# Takes a non-negative integer number (n).
Factorial(n)
1	if n == 0
2		return 1

נמשיך בכך שנניח שהפונקציה עובדת עבור בעיות קטנות יותר. כאן, בפרט, נניח שתבנית:קוד בשורה אכן מחזירה את $1 \cdot 1 \cdot 2 \dots (n - 1) = (n - 1)!$ . נותר רק להכפיל תוצאה זו ב $n$ :

# Calculates the factorial (atzeret).
# Takes a non-negative integer number (n).
Factorial(n)
1	if n == 0
2		return 1
	
3	return n * Factorial(n - 1)

חיפוש לינארי

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

# Linear search.   
# Takes an array (Values) and a value (v).
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search(Values, v)
1	return Linear-Search'(Values, v, Length(Values))


# Recursive linear search.
# Takes an array (Values), a value (v), and the length of the initial subsequence.
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search'(Values, v, i)

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

# Linear search.   
# Takes an array (Values) and a value (v).
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search(Values, v)
1	return Linear-Search'(Values, v, Length(Values))


# Recursive linear search.
# Takes an array (Values), a value (v), and the length of the initial subsequence.
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search'(Values, v, i)	
1	if i == 0
2		return False

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

# Linear search.   
# Takes an array (Values) and a value (v).
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search(Values, v)
1	return Linear-Search'(Values, v, Length(Values))


# Recursive linear search.
# Takes an array (Values), a value (v), and the length of the initial subsequence.
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search'(Values, v, i)	
1	if i == 0
2		return False
	
3	if Values[i] == v
4		return True
	
5	return Linear-Search'(Values, v, i - 1)

נותר פשוט להוכיח פורמאלית את מה שעשינו עד כה.

תבנית:הוכחה

מיון מיזוג

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

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/מיון מיזוג/פסוודו-קוד לMerge

כעת נכתוב פונקציה שממיינת בעזרת פונקציית עזר זו. נשים לב שהמסקנה היא שאפשר לבנות פונקציה רקורסיבית בעזרת פונקציה אחרת (רקורסיבית או לא) שהנה "קופסה שחורה".

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

# Merge sort. 
# Takes an array (Values).
# Returns an array of the same elements, sorted in increasing order.
Merge-Sort(Values)
1	if Length(Values) <= 1
2		return Values

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

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון מיזוג/פסוודו-קוד

כרגיל, נפרמל את צורת המחשבה הזו להוכחת נכונות.

תבנית:הוכחה

סכום תת-סידרה

נניח ש $A$ הוא מערך של מספרים שלמים חיוביים, ו $t$ מספר יעד שלם לא-שלילי כלשהו. רוצים לבדוק האם קיימת תת-קבוצה של הערכים ב $A$ שסכום איבריה הוא בדיוק $t$ .

תבנית:מבנה תבנית

מה חדש כאן יחסית למה שכבר ראינו?

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

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

# Calculates whether it is possible to sum up to a number (t) from a subset
#	of the first few (i)  elements of an array (A).
# Takes an array (A), a whole number (t), and the number of first
#	elements (i).
# Returns True or False depending on whether there is a subset of the first i of T
#	summing to t.
Subset-Sum(A, t, i)
1	if t == 0
2		return True

בנוסף, אם הסדרה באורך 0, אז ברור שאין אפשרות להגיע למספר היעד (אלא אם כן הוא 0 - אפשרות שכבר בדקנו):

# Calculates whether it is possible to sum up to a number (t) from a subset
#	of the first few (i)  elements of an array (A).
# Takes an array (A), a whole number (t), and the number of first
#	elements (i).
# Returns True or False depending on whether there is a subset of the first i of T
#	summing to t.
Subset-Sum(A, t, i)
1	if t == 0
2		return True
	
3	if i == 0
4		return False

כעת נניח שהפונקציה פותרת את הבעיות הקטנות יותר, ונפתור את הבעיה עבור $t$ ו $i$ . נגדיר את האיבר ה $i$ כ $a_{i}$ ; יש לגביו שתי אפשרויות: או שלא משתמשים בו, או שכן. אם לא משתמשים בו, אז האפשרות היחידה להגיע ל $t$ היא אם אפשר להגיע ל $t$ בעזרת $i - 1$ האיברים הראשונים (בעיה קטנה יותר במספר האיברים); אם כן משתמשים בו, אז האפשרות היחידה להגיע ל $t$ היא אם אפשר להגיע ל $t - a_{i}$ בעזרת $i - 1$ האיברים הראשונים (בעיה קטנה יותר הן במספר האיברים והן במספר היעד). נקודד זאת:

# Calculates whether it is possible to sum up to a number (t) from a subset
#	of the first few (i)  elements of an array (A).
# Takes an array (A), a whole number (t), and the number of first
#	elements (i).
# Returns True or False depending on whether there is a subset of the first i of T
#	summing to t.
Subset-Sum(A, t, i)
1	if t == 0
2		return True
	
3	if i == 0
4		return False
	
5	if Subset-Sum(A, t, i - 1)
6		return True
	
7	if t >= A[i] and Subset-Sum(A, t - A[i], i - 1)
8		return True
	
9	return False

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

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

תבנית:משפט

תבנית:הוכחה

דג הסלמון

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

תבנית:מבנה תבנית

דג הסלמון צריך לבחור באיזו ברכה לעצור ולנוח, כדי לצמצם את משך הזמן הכולל מהברכה הראשונה לאחרונה. מדוע שהדג יעצור לנוח בכלל בברכה כלשהי? נניח שאם הדג אינו עוצר בברכה, אז השחייה בתעלה הבאה אורכת $1.5$ יחידות זמן, השחייה בתעלה שלאחריה אורכת $1 . 5^{2}$ יחידות זמן, השחייה בתעלה שלאחריה אורכת $1 . 5^{3}$ יחידות זמן, וכן הלאה (עד שהדג עוצר לנוח בברכה). לשם הפשטות, נניח שהדג נח בברכה הראשונה והאחרונה.

מהו זמן המינימום למסלול הדג, ובאלו ברכות ינוח?

תבנית:מבנה תבנית

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

נגדיר כ $m (k)$ את הזמן המינימלי הנדרש לנוח בברכה $1$ , לשחות מברכה $1$ לברכה $k$ , ולנוח בברכה $k$ .

תבנית:משימה

תבנית:משפט

תבנית:הוכחה

הבעיה היחידה היא שאיננו יודעים את $i$ , אבל קל לבדוק מהו ה $i$ המשתלם ביותר בעזרת לולאה:

# Calculates the minimum time for the fish to swim up to (including) some pool (k).
# Takes the up-to pool number (k).
Min-Time(k)
1	if k == 1
2		return Resting-Times[k]
		
3	min-time = ∞
	
4	for i in [1, ..., k - 1]
5		guess = Min-Time(i) + 2 * (1.5^(k - i) - 1) + Resting-Times[k]
					
6		if guess < min-time
7			min-time = guess
			
8	return min-time

תבנית:הארה

הדפסת פרטי הפתרון - "שביל פירורים"

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

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

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

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

נראה כעת שתי דוגמות לשיטה זו.

הדפסת פרטי סכום תת-סדרה

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

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

# Calculates whether it is possible to sum up to a number (t) from a subset
#	of the first few (i)  elements of an array (A).
# Takes an array (A), a whole number (t), and the number of first
#	elements (i).
# Returns True or False depending on whether there is a subset of the first i of T
#	summing to t.
Subset-Sum(A, t, i)
1	if t == 0
2		return True
	
3	if i == 0
4		return False
	
5	if Subset-Sum(A, t, i - 1)
6		S[t][i] = False
7		return True
	
8	if t >= A[i] and Subset-Sum(A, t - A[i], i - 1)
9		S[t][i] = True
10		return True

11	S[t][i] = False
	
12	return False

נשים לב לשורות 6, ,9. אם הגענו לשורה 6, משמע שמצאנו פתרון שאינו משתמש באיבר ה $i$ ; שורה 6 רושמת זאת במטריצה. שני המקרים האחרים דומים.

והנה הפונקציה תבנית:קוד בשורה שתדפיס את האיברים:

# Prints the elements summing up to a given target.
Print-Elements(A, t, i)
1	if t == 0 or i == 0
2		return
		
3	if S[t][i] == False
4		Print-Elements(A, t, i - 1)
5		return

6	Print-Elements(A, t - A[i], i - 1)
7	Print( A[i] )

לסיכום, כך נדפיס הכל:

	# Run the algorithm, get whether it's possible to sum up.
1	can = Subset-Sum(A, t, Length(A))

	# If can sum up, print also the elements.
2	if can 
3		Print-Elements(A, t, Length(A))

תבנית:הארה

הדפסת פרטי דג הסלמון

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

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

# Calculates the minimum time for the fish to swim up to (including) some pool (k).
# Takes the up-to pool number (k).
Min-Time(k)
1	if k == 1
2		S[k] = k
3		return Resting-Times[k]
		
4	min-time = ∞
	
5	for i in [1, ..., k - 1]
6		guess = Min-Time(i) + 2 * (1.5^(k - i) - 1) + Resting-Times[k]
					
7		if guess < min-time
8			S[k] = i
			
9	return min-time

והנה הפונקציה תבנית:קוד בשורה שתדפיס את העצירות:

# Prints the stops on the fastest route up to
#	(and including) some pool number (i).
Print-Stops(i)
1	if i > 1
2		Print-Stops(S[i])
	
3	Print(i)

לסיכום, כך נדפיס הכל:

	# Run the algorithm, get the shortest time. 
1	m = Min-Time( Length(Resting-Times) )

	# Print the shortest time.
2	Print(m)
	
	# Print the stops.
3	Print-Stops( Length(Resting-Times) )

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס ֵ

מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/חשיבה רקורסיבית

תוכן עניינים

מה היא רקורסיה?

כיצד המהדר מתייחס לרקורסיה

גישה אינדוקטיבית

חישוב עצרת

חיפוש לינארי

מיון מיזוג

סכום תת-סידרה

דג הסלמון

הדפסת פרטי הפתרון - "שביל פירורים"

הדפסת פרטי סכום תת-סדרה

הדפסת פרטי דג הסלמון

תפריט ניווט