רקורסיה אינה קשה: הדרכה שלב אחר שלב של טכניקת תכנות שימושית זו

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

הפעלת פונקציה

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

ראשית, מהי ערימה?

ערימה היא מבנה נתונים הפועל על בסיס "Last In, First Out". פריט "נדחף" לערימה כדי להוסיף אליו, ופריט "מוקפץ" מעל הערימה כדי להסיר אותו.

שימוש בערימה הוא שיטה להזמנת פעולות מסוימות לביצוע.

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

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

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

למה אני אומר בדרך כלל ?

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

רקורסיה

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

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

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

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

בואו נסתכל על דוגמה קלאסית.

פקטוריאל

const factorial = function(num) { debugger; if (num === 0 || num === 1) { return 1 } else { return num * factorial(num - 1) }}

factorial(5)

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

התנאי הראשון קובע: "אם הפרמטר שעבר שווה 0 או 1, נצא ונחזיר 1".

בהמשך, המקרה הרקורסיבי קובע:

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

אז אם אנו מתקשרים factorial(0), הפונקציה מחזירה 1 ולעולם לא פוגעת במקרה הרקורסיבי.

אותו הדבר תקף factorial(1).

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

1. ערימת הביצוע ממוקמת factorial()עם 5 ככל שהוויכוח עבר. המקרה הבסיסי הוא שקרי, אז הכנסו למצב הרקורסיבי.
2. ערימת הביצוע ממוקמת factorial()בפעם השנייה עם num-1= 4 כארגומנט. מקרה הבסיס שגוי, הזן מצב רקורסיבי.
3. ערימת הביצוע מציבה factorial()בפעם השלישית כ num-1(4–1) = 3 כארגומנט. מקרה הבסיס שגוי, הזן מצב רקורסיבי.
4. ערימת הביצוע מציבה factorial()פעם רביעית עם num-1(3–1) = 2 כארגומנט. מקרה הבסיס שגוי, הזן מצב רקורסיבי.
5. ערימת הביצוע מציבה factorial()פעם חמישית עם num-1(2–1) = 1 כארגומנט. עכשיו המקרה הבסיסי נכון, אז חזור 1.

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

6. מכאן ההקשר האחרון לביצוע הושלם,, num === 1כך שהפונקציה מחזירה 1.

7. לאחר מכן num === 2, אז ערך ההחזר הוא 2. (1 × 2).

8. לאחר מכן num === 3, ערך השיבה הוא 6, (2 × 3).

עד כה יש לנו 1 × 2 × 3.

9. לאחר מכן,, num === 4(4 × 6). 24 הוא ערך ההחזרה להקשר הבא.

10. לבסוף,, num === 5(5 × 24) ויש לנו 120 כערך הסופי.

רקורסיה די מסודרת, נכון?

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

זו הסיבה שאנו משתמשים בפתרונות רקורסיביים.

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

• קל יותר לפתור בעיות משנה מאשר הבעיה המקורית
• פתרונות לבעיות משנה משולבים בכדי לפתור את הבעיה המקורית

"חלוק-וכבוש" משמש לרוב למעבר או חיפוש במבני נתונים כגון עצי חיפוש בינאריים, גרפים וערמות. זה עובד גם עבור אלגוריתמי מיון רבים, כמו quicksort ו- heapsort.

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

פיבונאצ'י

const fibonacci = function(num) { if (num <= 1) { return num } else { return fibonacci(num - 1) + fibonacci(num - 2) }}fibonacci(5);

מערכים רקורסיביים

function flatten(arr) { var result = [] arr.forEach(function(element) { if (!Array.isArray(element)) { result.push(element) } else { result = result.concat(flatten(element)) } }) return result}

flatten([1, [2], [3, [[4]]]]);

היפוך מחרוזת

function reverse(str) { if (str.length === 0) return '' return str[str.length - 1] + reverse(str.substr(0, str.length - 1))}

reverse('abcdefg');

מהיר

function quickSort(arr, lo, hi) { if (lo === undefined) lo = 0 if (hi === undefined) hi = arr.length - 1

 if (lo 
    
      partition: ' + p) // sort subarrays quickSort(arr, lo, p - 1) quickSort(arr, p + 1, hi) } // for initial call, return a sorted array if (hi - lo === arr.length - 1) return arr}
    

function partition(arr, lo, hi) { // choose last element as pivot var pivot = arr[hi] // keep track of index to put pivot at var pivotLocation = lo // loop through subarray and if element <= pivot, place element before pivot for (var i = lo; i < hi; i++) { if (arr[i] <= pivot) { swap(arr, pivotLocation, i) pivotLocation++ } } swap(arr, pivotLocation, hi) return pivotLocation}

function swap(arr, index1, index2) { if (index1 === index2) return var temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp console.log('swapped' + arr[index1], arr[index2], +' in ', arr) return arr}

quickSort([1, 4, 3, 56, 9, 8, 7, 5])

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

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

משאבים נוספים

ויקיפדיה

Software Engineering

Another good article

M.I.T. open courseware