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

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

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

{{הארה|1 = 
רעיון זה נקרא לפעמים ''divide and conquer'', או ''הפרד ומשול''.}} 

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

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

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

<source lang = "python">
# 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</source>

מהתבוננות בפונקציה, קל לראות שהיא מחזירה <math dir = "ltr">\displaystyle 1 \cdot 1 \cdot 2 \cdots n = n!</math>.

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

<source lang = "python">
# 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)</source>

בניגוד למימוש הקודם, מימוש זה הוא ''רקורסיבי'', וזאת משום שהפונקציה {{קוד בשורה|Factorial}} קוראת לפונקציה {{קוד בשורה|Factorial}}, כלומר לה עצמה.

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

מדוע עובדת הגרסה הרקורסיבית? להלן ההסבר הנפוץ בקורס תכנות. נניח שאנו קוראים ל{{קוד בשורה|Factorial(3)}}:
#בקריאה הראשונה {{קוד בשורה|1=n == 3}}.‏ 1 תכשל, ו2 לא תתבצע. 3 תחזיר כתשובה את 3 כפול הערך המוחזר מ{{קוד בשורה|Factorial(2)}}.
#בקריאה זו {{קוד בשורה|1=n == 2}}.‏ 1 תכשל,  ו2 לא תתבצע. 3 תחזיר כתשובה את 2 כפול הערך המוחזר מ{{קוד בשורה|Factorial(1)}}.
#בקריאה זו {{קוד בשורה|1=n==1}}.‏ 1 תכשל, ו2 לא תתבצע. 3 תחזיר כתשובה את 1 כפול הערך המוחזר מ{{קוד בשורה|Factorial(0)}}.
#בקריאה זו {{קוד בשורה|1=n == 0}}.‏ 1 תצליח, ו2 תחזיר כתשובה את 1. ערך זה יוכפל ב1, התוצאה תוכפל ב2, והתוצאה תוכפל ב3. 

הנקודה האחרונה מראה שמבחינת התוצאה המוחזרת, נקבל אותו הדבר כגרסת הלולאה. בשני המקרים נקבל <math dir = "ltr">\displaystyle 1 \cdot 1 \cdot 2 \cdot 3 \cdot = 3!</math>.


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

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

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

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

{{הוכחה|1 = 

(בסיס האינדוקציה) אם <math dir = "ltr">\displaystyle n = 0</math> אז הפונקציה מחזירה <math dir = "ltr">\displaystyle 1 = 0!</math>. זה ברור מ1-2.

(מעבר האינדוקציה) נניח שהפונקציה עובדת עד (כולל) <math dir = "ltr">\displaystyle n - 1 \ge 0</math>, ונראה שהיא עובדת גם
ל<math dir = "ltr">\displaystyle n \ge 1</math>. אם <math dir = "ltr">\displaystyle n \ge 1</math>, אז ברור ש1 תיכשל, ו2 לא תתבצע. עפ"י הנחת האינדוקציה, {{קוד בשורה|Factorial(n - 1)}} תחזיר <math dir = "ltr">\displaystyle (n - 1)! = 1 \cdot 1 \cdot 2 \cdots (n - 1)</math>. לכן, 3 תחזיר <math dir = "ltr">\displaystyle 1 \cdot 1 \cdot 2 \cdots
(n - 1) \cdot n = n!</math>.}} 

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

{{הארה|1=
חלק מהסטודנטים מתקשים בנקודה השניה, ומתעקשים לחקות את פעולת המהדר ולפרוש את הרקורסיה עד לסוף. עם זאת, כפי שציינו, זה ממילא מה שאנו עושים בהוכחת נכונות האינדוקציה, לכן מדוע לא לעשות זאת בשלב בו אנו כותבים את הרקורסיה?
}}

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

===חישוב עצרת===

כדי להתרגל לרעיון, נחזור שוב לדוגמה הראשונה שראינו - חישוב עצרת. (היות שכבר ראינו את הפתרון לעיל, לא נראה כאן שום דבר חדשני במיוחד.)
כאמור, בגוף הרקורסיה, נתחיל בכך שנטפל בבעיות הקטנות שאין יכולת או צורך לחלק אותן הלאה. כאן, באופן טבעי, הבעיה הקטנה ביותר היא כאשר <math dir = "ltr">\displaystyle n = 0</math>:

<source lang = "python">
# Calculates the factorial (atzeret).
# Takes a non-negative integer number (n).
Factorial(n)
1	if n == 0
2		return 1</source>

נמשיך בכך ש'''נניח''' שהפונקציה עובדת עבור בעיות קטנות יותר. כאן, בפרט, נניח ש{{קוד בשורה|Factorial(n - 1)}} אכן מחזירה את <math dir = "ltr">\displaystyle 1 \cdot 1 \cdot 2 \cdots (n - 1) = (n -
1)!</math>. נותר רק להכפיל תוצאה זו ב<math dir = "ltr">\displaystyle n</math>:

<source lang = "python">
# 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)</source>

===חיפוש לינארי===

נמשיך בעוד דוגמה פשוטה. ניקח [[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/חיפוש לינארי ובינרי#חיפוש לינארי|חיפוש לינארי]], ונכתוב אותו בצורה רקורסיבית. נכתוב את הפונקציה כך שהיא תחפש את האיבר בתת-מערך המכיל את <math dir =  ltr">\displaystyle i</math> האיברים הראשונים:

<source lang = "python">
# 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)</source>

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

<source lang = "python">
# 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</source>

נמשיך בכך ש'''נניח''' שהפונקציה עובדת עבור בעיות קטנות יותר. כאן, בפרט, נניח ש {{קוד בשורה|Linear-Search'(Values, v, i)}} אכן בודקת נכונה האם <math dir = "ltr">\displaystyle v</math> מופיע ב<math dir = "ltr">\displaystyle i - 1</math> המקומות הראשונים. נותר רק לבדוק האם האיבר ה<math dir = "ltr">\displaystyle i</math> הוא האיבר המבוקש:

<source lang = "python">
# 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)</source>

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

{{הוכחה|1 = 
ההוכחה היא באינדוקציה על אורך המערך, <math dir = "ltr">\displaystyle i</math>. 

(בסיס האינדוקציה) אם המערך בעל אורך 0, אז אף איבר אינו חבר בו, ועל התשובה להיות {{קוד בשורה|Nil}}. אכן, 1-2 יחזירו {{קוד בשורה|Nil}}. 

(מעבר האינדוקציה) נניח שהפונקציה מחזירה את הערך הנכון עבור כל תת-מערך בעל אורך עד (כולל) <math dir = "ltr">\displaystyle i
- 1</math>, ונתבונן במערך בעל אורך <math dir = "ltr">\displaystyle i</math>. אם האיבר במקום ה<math dir = "ltr">\displaystyle i</math> הוא האיבר המבוקש, אז (מן הסתם) הוא נמצא במערך. אכן 3-4 יחזירו את התוצאה המבוקשת. אם האיבר במקום ה<math dir = "ltr">\displaystyle i</math> איננו האיבר המבוקש, אז או שהוא נמצא ב<math dir = "ltr">\displaystyle i - 1</math> המקומות הראשונים, או שאיננו כלל ב<math dir = "ltr">\displaystyle i</math> המקומות הראשונים. בכל מקרה, עפ"י הנחת האינדוקציה, 5 תחזיר את התוצאה המבוקשת.
}}

===מיון מיזוג===

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

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

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

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

<source lang = "python">
# 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</source>

שוב, נניח שהאלגוריתם יודע למיין כל מערך שארכו לכל היותר <math dir = "ltr">\displaystyle n - 1</math> (כולל), ונראה כיצד
להשתמש בזאת ובפונקציה {{קוד בשורה|Merge}} כדי למיין מערך שארכו <math dir = "ltr">\displaystyle n</math>. ראשית נחצה את המערך לשניים. כל אחד מחציו השמאלי והימני קטן ממש מ<math dir = "ltr">\displaystyle n</math>. על פי הנחתנו, הפונקציה אכן ממיינת מערכים בגדלים אלה. אנו גם יודעים ש{{קוד בשורה|Merge}} ממזגת מערכים ממויינים. נשתמש בזאת כך:

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

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

{{הוכחה|1 = 
נקבע כ<math dir = "ltr">\displaystyle n</math> את {{קוד בשורה|Length(Values)}}. ההוכחה היא באינדוקציה על
<math dir = "ltr">\displaystyle n</math>.

(בסיס האינדוקציה) עבור <math dir = "ltr">\displaystyle n = 0</math> או<math dir = "ltr">\displaystyle n = 1</math>,‏ 1-2 מחזירות פשוט את {{קוד בשורה|Values}}, שבמקרה זה ממוין עפ"י הגדרה.

(מעבר האינדוקציה) נניח ש{{קוד בשורה|Merge-Sort}} עובדת לכל <math dir = "ltr">\displaystyle n' < n</math>. אז 4-5 ממיינות את החצי השמאלי והימני לפי בסיס האינדוקציה (כי הפונקציה פועלת על מערכים קטנים יותר). 6 פועלת לכן על שני מערכים ממוינים,
ולכן מחזירה את המערך ממוין.}}

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

נניח ש<math dir = "ltr">\displaystyle	A</math> הוא מערך של מספרים שלמים חיוביים, ו<math dir = "ltr">\displaystyle	t</math> מספר יעד שלם לא-שלילי כלשהו. רוצים לבדוק האם קיימת תת-קבוצה של הערכים ב<math dir = "ltr">\displaystyle	A</math> שסכום איבריה הוא בדיוק <math dir = "ltr">\displaystyle	t</math>.

{{דוגמה|תוכן = 
נניח שהמערך מייצג את הערכים <math dir = "ltr">\displaystyle A = [2, 1, 10, 40, 20]</math> 
#אם <math dir = "ltr">\displaystyle t = 52</math>, אז התשובה היא {{קוד בשורה|True}}, מפני ש<math dir = "ltr">\displaystyle 2 + 10 +40 = 52</math>.
#אם <math dir = "ltr">\displaystyle t = 4</math> אז התשובה היא {{קוד בשורה|False}}, מפני שכפי שבדיקה פשוטה תראה, אין ערכים שסכומם 4.}} 

מה חדש כאן יחסית למה שכבר ראינו?
#מדובר כאן ב''בעיית הכרעה'' (כלומר, משהו שמחליט {{קוד בשורה|True}} או {{קוד בשורה|False}}), ולא בחישוב, כמקודם. (זו נקודה שולית למדי.)
#כאן יש שתי דרגות חופש לגבי הקביעה מה בעיה "קטנה" יותר: מספר יעד קטן יותר, או סדרה קצרה יותר. 

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


<source lang = "python">
# 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</source>

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

<source lang = "python">
# 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</source>

כעת '''נניח''' שהפונקציה פותרת את הבעיות הקטנות יותר, ונפתור את הבעיה עבור <math dir = "ltr">\displaystyle t</math> ו<math dir = "ltr">\displaystyle i</math>. נגדיר את האיבר ה<math dir = "ltr">\displaystyle i</math> כ<math dir = "ltr">\displaystyle a_i</math>; יש לגביו שתי אפשרויות: או שלא משתמשים בו, או שכן. אם לא משתמשים בו, אז האפשרות היחידה להגיע ל<math dir = "ltr">\displaystyle t</math> היא אם אפשר להגיע ל<math dir = "ltr">\displaystyle t</math> בעזרת <math dir = "ltr">\displaystyle i - 1</math> האיברים הראשונים (בעיה קטנה יותר במספר האיברים); אם כן משתמשים בו, אז האפשרות היחידה להגיע ל<math dir = "ltr">\displaystyle t</math> היא אם אפשר להגיע ל<math dir = "ltr">\displaystyle t - a_i</math> בעזרת <math dir = "ltr">\displaystyle i - 1</math> האיברים הראשונים (בעיה קטנה יותר הן במספר האיברים והן במספר היעד). נקודד זאת:

<source lang = "python">
# 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</source>

כדי לפתור את הבעיה המקורית, יש צורך לקרוא ל {{קוד בשורה|Subset-Sum(A, t, n)}}.

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

{{משפט|תוכן = 
נגדיר כ <math dir = "ltr">\displaystyle s(t, i)</math> את הערך המוחזר ע"י {{קוד בשורה|Subset-Sum(A, t, i)}}. אז <math dir = "ltr">\displaystyle s(t, i)</math> נתון על ידי הנוסחה:
<math dir = "ltr">\displaystyle	s(t, i) = </math>
#True, אם <math dir = "ltr">\displaystyle	t = 0</math>.
#False, אם <math dir = "ltr">\displaystyle t \ne 0,	i = 0</math>.
#True, אם <math dir = "ltr">\displaystyle	i > 0</math> 	וכן
##או ש<math dir = "ltr">\displaystyle	s(t, i - 1)</math> הוא True
##או ש<math dir = "ltr">\displaystyle	s(t - a_i, i - 1)</math> הוא True

בנוסף, ל<math dir = "ltr">\displaystyle s(t, i)</math> יש ערך אמת אמ"ם אפשר להגיע ל<math dir = "ltr">\displaystyle t</math> בעזרת סכום תת-סדרה של <math dir = "ltr">\displaystyle i</math> המספרים הראשונים מ{{קוד בשורה|A}}.}} 


{{הוכחה|1 = 
הטענה ש<math dir = "ltr">\displaystyle s(t, i)</math> נתון על ידי נוסחת הנסיגה הנ"ל ברורה מהתבוננות בקוד. נותר לכן רק להוכיח את החלק השני של המשפט, הטוען שלפונקציה הנתונה על ידי נוסחת הנסיגה הנ"ל יש ערך אמת אמ"ם אפשר להגיע ל<math dir = "ltr">\displaystyle t</math> בעזרת סכום תת-סדרה של <math dir = "ltr">\displaystyle i</math> המספרים הראשונים מ{{קוד בשורה|A}}.

ההוכחה היא באינדוקציה כפולה על <math dir = "ltr">\displaystyle	i</math> ו<math dir = "ltr">\displaystyle	t</math>.

(בסיס האינדוקציה) כאשר <math dir = "ltr">\displaystyle	t = 0</math> ברור שאפשר להגיע לסכום המתאים, מפני שאפשר לא לבחור אף איבר. כאשר <math dir = "ltr">\displaystyle	t \ne 0</math> אך <math dir = "ltr">\displaystyle	i = 0</math>, ברור שאי אפשר להגיע לסכום המתאים, כי אין אף איבר שאפשר לבחור.

(מעבר האינדוקציה) נניח שהטענה נכונה עד (לא כולל) זוג <math dir = "ltr">\displaystyle	(t, i)</math> כלשהו. יש בדיוק שתי אפשרויות עבור האיבר ה<math dir = "ltr">\displaystyle	i</math>: או שלא משתמשים בו, או שכן. אם לא משתמשים בו, אז חייבים להגיע ל<math dir = "ltr">\displaystyle	t</math> בעזרת <math dir = "ltr">\displaystyle	i - 1</math> המספרים הראשונים; מהנחת האינדוקציה, זהו בדיוק <math dir = "ltr">\displaystyle	s(t, i -1)</math>. אם כן משתמשים בו, אז חייבים להגיע ל<math dir = "ltr">\displaystyle	t - a_i</math> בעזרת <math dir = "ltr">\displaystyle	i - 1</math> המספרים הראשונים; מהנחת האינדוקציה, זהו בדיוק <math dir = "ltr">\displaystyle	s(t - a_i, i -1)</math>.

}}

===דג הסלמון===

{{:מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/חשיבה רקורסיבית/דג הסלמון/הבעיה}}

{{:מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/חשיבה רקורסיבית/דג הסלמון/הרקורסיה הפשוטה}}

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

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


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

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

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


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

נניח ש<math dir = "ltr">\displaystyle	A</math> הוא מערך של מספרים שלמים חיוביים, ו<math dir = "ltr">\displaystyle	t</math> מספר יעד שלם לא-שלילי כלשהו. נזכר שבבעיית סכום תת-סדרה, רוצים לבדוק האם קיימת תת-קבוצה של הערכים ב<math dir = "ltr">\displaystyle	A</math> שסכום איבריה הוא בדיוק <math dir = "ltr">\displaystyle	t</math>. כעת רוצים להדפיס גם את האיברים המרכיבים את הסכום (אם יש איברים כאלה).

נשים לב שכאן סוג ההחלטה שאנו מבצעים בכל קריאה רקורסיבית היא השאלה האם אנו משתמשים באיבר או לא. לכן, פשוט נוסיף עוד מטריצה <math dir = "ltr">\displaystyle	S</math>, המתארת עבור כל <math dir = "ltr">\displaystyle	t</math> ו<math dir = "ltr">\displaystyle	i</math> האם אנו משתמשים באיבר ה<math dir = "ltr">\displaystyle	i</math> כדי לקבל סכום <math dir = "ltr">\displaystyle	t</math>.

<source lang = "python">
# 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</source>
נשים לב לשורות 6, ,9. אם הגענו לשורה 6, משמע שמצאנו פתרון שאינו משתמש באיבר ה<math dir = "ltr">\displaystyle	i</math>; שורה 6 רושמת זאת במטריצה. שני המקרים האחרים דומים.


והנה הפונקציה {{קוד בשורה|Print-Elements}} שתדפיס את האיברים:     
<source lang = "python">
# 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] )
</source>

לסיכום, כך נדפיס הכל:      
<source lang = "python">
	# 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))</source>

{{הארה|אפשר לשים לב ששורה 11 ב{{קוד בשורה|Subset-Sum}} מיותרת. עם זאת, היא אינה מקלקלת דבר.}}

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

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

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

<source lang = "python">
# 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</source>

והנה הפונקציה {{קוד בשורה|Print-Stops}} שתדפיס את העצירות:     
<source lang = "python">
# 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)</source>

לסיכום, כך נדפיס הכל:      
<source lang = "python">
	# 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) )</source>


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

[[קטגוריה:מבני נתונים ואלגוריתמים]]