איך עובד רקורסיה - מוסבר בעזרת תרשימי זרימה וסרטון

"כדי להבין רקורסיה, צריך קודם להבין רקורסיה."

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

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

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

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

איזו גישה נראית לך קלה יותר?

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

function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } }}

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

function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }

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

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

תיק בסיס ותיק רקורסיבי

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

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

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1)} countdown(5); // This is the initial call to the function.

פונקציה זו תמשיך לספור למטה לנצח. אם אתה מפעיל בטעות קוד עם לולאה אינסופית, אתה יכול ללחוץ על "Ctrl-C" כדי להרוג את הסקריפט שלך. (לחלופין, אם לפעמים אתה משתמש ב- CodePen כמוני, עליך להוסיף "? Turn_off_js = true" בסוף כתובת האתר.)

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

הנה פונקציית הספירה לאחור, עם מקרה בסיס:

function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1); } } countdown(5); // This is the initial call to the function.

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

אנו מתחילים בהדפסת המספר 5 באמצעות console.log. מאז חמש הוא לא פחות מ או שווה לאפס, אנחנו הולכים לדוח אחר. שם אנו מכנים שוב את פונקציית הספירה לאחור עם המספר ארבע (5-1 = 4?).

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

ערמת השיחות

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

אני אראה לך את ערימת השיחות בפעולה עם factorialהפונקציה. factorial(5)כתוב כ 5! וזה מוגדר כך: 5! = 5 * 4 * 3 * 2 * 1. להלן פונקציה רקורסיבית לחישוב פקטורי המספר:

function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }

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

שימו לב כיצד לכל שיחה factיש עותק משלה x. זה מאוד חשוב ליצירת עבודות רקורסיות. אינך יכול לגשת לעותק של פונקציה אחרת x.

האם מצאת את המפתח עדיין?

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

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

ובזכות רקורסיה, סוף סוף תוכלו למצוא את המפתח ולקבל את החולצה!

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

סיכום

אני מקווה שמאמר זה הביא לך בהירות רבה יותר לגבי רקורסיות בתכנות. מאמר זה מבוסס על שיעור בקורס הווידיאו החדש שלי מ- Manning Publications בשם Algorithms in Motion. הקורס (וגם מאמר זה) מבוסס על הספר המדהים אלגוריתמים Grokking מאת Adit Bhargava. הוא זה שצייר את כל האיורים המהנים במאמר זה.

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

קבל 39% הנחה על הקורס שלי באמצעות קוד ' 39carnes '!

ולבסוף, כדי להבין באמת רקורסיה, עליכם לקרוא מאמר זה שוב. ?