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

מהו עץ רקורסיה?

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

צורה מלאה

מבנה עץ

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

מקרה יסוד

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

שיחות רקורסיביות

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

זרימת ביצוע:

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

ניתוח מורכבות זמן

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

מבוא

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

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

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

סוגי רקורסיה

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

• רקורסיה לינארית
• רקורסיית עץ
• רקורסיה לינארית

רקורסיה לינארית

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

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• אם נסתכל על הפונקציה doSomething(n), היא מקבלת פרמטר בשם n ועושה כמה חישובים לפני שקוראים לאותו הליך פעם נוספת אבל עם ערכים נמוכים יותר.
• כאשר השיטה doSomething() נקראת עם ערך הארגומנט n, נניח ש-T(n) מייצג את משך הזמן הכולל הדרוש להשלמת החישוב. לשם כך, נוכל גם לנסח קשר חוזר, T(n) = T(n-1) + K. K משמש כאן כקבוע. קבוע K נכלל מכיוון שלוקח זמן לפונקציה להקצות או לבטל הקצאת זיכרון למשתנה או לבצע פעולה מתמטית. אנו משתמשים ב-K כדי להגדיר את הזמן מכיוון שהוא כל כך דקה וחסר משמעות.
• ניתן לחשב פשוט את מורכבות הזמן של תוכנית רקורסיבית זו מכיוון שבתרחיש הגרוע ביותר, השיטה doSomething() נקראת n פעמים. מבחינה פורמלית, המורכבות הזמנית של הפונקציה היא O(N).

רקורסיית עץ

• כאשר אתה מבצע קריאה רקורסיבית במקרה הרקורסי שלך יותר מפעם אחת, היא מכונה רקורסיית עץ. המחשה יעילה של רקורסיית העץ היא רצף הפיבונאצ'י. פונקציות רקורסיביות של עץ פועלות בזמן אקספוננציאלי; הם אינם ליניאריים במורכבות הזמנית שלהם.
• תסתכל על הפסאודו-קוד למטה,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• ההבדל היחיד בין הקוד הזה לקודם הוא שהקוד הזה מבצע קריאה אחת נוספת לאותה פונקציה עם ערך נמוך יותר של n.
• נניח T(n) = T(n-1) + T(n-2) + k כיחס החזרה לפונקציה זו. K משמש כקבוע פעם נוספת.
• כאשר מתבצעת יותר מקריאה אחת לאותה פונקציה עם ערכים קטנים יותר, רקורסיה מסוג זה מכונה רקורסיית עץ. ההיבט המסקרן הוא עכשיו: עד כמה הפונקציה הזו גוזלת זמן?
• קחו ניחוש המבוסס על עץ הרקורסיה למטה עבור אותה פונקציה.
  
• זה עלול לחשוב על כך שזה מאתגר להעריך את מורכבות הזמן על ידי הסתכלות ישירה על פונקציה רקורסיבית, במיוחד כאשר מדובר ברקורסיה של עץ. שיטת עץ הרקורסיה היא אחת מכמה טכניקות לחישוב המורכבות הזמנית של פונקציות כאלה. בואו נבחן את זה בפירוט רב יותר.

מהי שיטת עץ הרקורסיה?

• יחסי חזרות כמו T(N) = T(N/2) + N או השניים שכיסינו קודם בסעיף סוגי הרקורסיה נפתרים באמצעות גישת עץ הרקורסיה. יחסים חוזרים אלה משתמשים לעתים קרובות באסטרטגיית הפרד וכבש כדי לטפל בבעיות.
• לוקח זמן לשלב את התשובות לבעיות המשנה הקטנות יותר שנוצרות כאשר בעיה גדולה יותר מפורקת לבעיות משנה קטנות יותר.
• יחס החזרה, למשל, הוא T(N) = 2 * T(N/2) + O(N) עבור מיון המיזוג. הזמן הדרוש לשילוב התשובות לשתי בעיות משנה עם גודל משולב של T(N/2) הוא O(N), וזה נכון גם ברמת היישום.
• לדוגמה, מכיוון שיחס החזרה לחיפוש בינארי הוא T(N) = T(N/2) + 1, אנו יודעים שכל איטרציה של חיפוש בינארי מביאה למרחב חיפוש שנחתך לשניים. לאחר שנקבעה התוצאה, אנו יוצאים מהפונקציה. ליחס החזרה נוסף 1+ מכיוון שזו פעולת זמן קבועה.
• קשר החזרה T(n) = 2T(n/2) + Kn הוא אחד שיש לקחת בחשבון. Kn מציין את משך הזמן הנדרש לשילוב התשובות לבעיות משנה דו-ממדיות.
• הבה נתאר את עץ הרקורסיה עבור יחס החזרה הנ'ל.

אנו עשויים להסיק כמה מסקנות מלימוד עץ הרקורסיה לעיל, כולל

1. גודל הבעיה בכל רמה הוא כל מה שחשוב לקביעת הערך של צומת. גודל הבעיה הוא n ברמה 0, n/2 ברמה 1, n/2 ברמה 2 וכן הלאה.

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

• קחו למשל את הערך של N = 16. אם מותר לנו לחלק את N ב-2 בכל שלב, כמה צעדים נדרשים כדי לקבל N = 1? בהתחשב בכך שאנו מחלקים בשניים בכל שלב, התשובה הנכונה היא 4, שהוא הערך של log(16) base 2.

log(16) base 2

המרת מספר שלם למחרוזת

log(2^4) base 2

4 * log(2) base 2, שכן log(a) base a = 1

אז, 4 * log(2) base 2 = 4

3. בכל רמה, המונח השני בהישנות נחשב לשורש.

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

תו java ל-int

כיצד להשתמש בעץ רקורסיה כדי לפתור קשרי הישנות?

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

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

דוגמא

קחו בחשבון את הקשר הישנות,

T(n) = 2T(n/2) + K

פִּתָרוֹן

יחס החזרה הנתון מציג את המאפיינים הבאים,

בעיה בגודל n מחולקת לשתי תת-בעיות כל אחת בגודל n/2. עלות שילוב הפתרונות לבעיות משנה אלו היא ק.

כל גודל בעיה של n/2 מתחלק לשתי תת-בעיות כל אחת בגודל n/4 וכן הלאה.

ברמה האחרונה, גודל התת-בעיה יקטן ל-1. במילים אחרות, סוף סוף הגענו למקרה הבסיס.

בטל 0

בואו נבצע את השלבים כדי לפתור את הקשר הישנות הזה,

שלב 1: צייר את עץ הרקורסיה

שלב 2: חשב את גובה העץ

מכיוון שאנו יודעים שכאשר אנו מחלקים מספר ברציפות ב-2, מגיע הזמן שבו מספר זה מצטמצם ל-1. כמו עם גודל הבעיה N, נניח שלאחר K חלוקות ב-2, N הופך שווה ל-1, מה שמרמז, ( n / 2^k) = 1

כאן n / 2^k הוא גודל הבעיה ברמה האחרונה והוא תמיד שווה ל-1.

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

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) base 2

אז גובה העץ הוא בסיס לוג (n) 2.

שלב 3: חשב את העלות בכל רמה

סוג משתנים java

• עלות ברמה-0 = K, שתי בעיות משנה מתמזגות.
• עלות ברמה-1 = K + K = 2*K, שתי בעיות משנה מתמזגות פעמיים.
• עלות ברמה-2 = K + K + K + K = 4*K, שתי בעיות משנה מתמזגות ארבע פעמים. וכולי....

שלב 4: חשב את מספר הצמתים בכל רמה

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

• לרמה-0 יש צומת אחד (2^0).
• לרמה-1 יש 2 (2^1) צמתים
• לרמה-2 יש 4 (2^2) צמתים
• לרמה-3 יש 8 (2^3) צמתים

אז לרמה log(n) צריך להיות 2^(log(n)) צמתים כלומר n צמתים.

שלב 5: סכמו את העלות של כל הרמות

• ניתן לכתוב את העלות הכוללת כ,
• עלות כוללת = עלות כל הרמות מלבד הרמה האחרונה + עלות הרמה האחרונה
• עלות כוללת = עלות לרמה-0 + עלות לרמה-1 + עלות לרמה-2 +.... + עלות לרמה-לוג(n) + עלות לרמה האחרונה

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

בואו נכניס את הערכים לנוסחאות,

• T(n) = K + 2*K + 4*K + .... + log(n)` פעמים + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) פעמים)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) פעמים + O(n)

אם תסתכל מקרוב על הביטוי שלמעלה, הוא יוצר התקדמות גיאומטרית (a, ar, ar^2, ar^3 ...... זמן אינסופי). הסכום של GP ניתן על ידי S(N) = a / (r - 1). הנה האיבר הראשון ו-r הוא היחס המשותף.