רקורסיה - Recursion
void PrintStars(int n).if (n == 0) return;.n - 1. בזמן הכתיבה מניחים שהפונקציה כבר עובדת.Directory.GetFiles ו-Directory.GetDirectories.n++ או n-- בתוך הקריאה לא מתאימה, כי הערך משתנה לפני או אחרי השליחה. שולחים את n - 1, כך שהמשתנה המקורי לא משתנה.פרקי ההרצאה: רקורסיה - Recursion
תמלול ההרצאה: רקורסיה - Recursion
הטקסט המלא של הדקות הראשונות בהרצאה «רקורסיה - Recursion» בקורס הווידאו של PracticU – כתוביות בעברית עם זמן התחלה לכל פסקה. כך תוכלו לקרוא ולחפש את הנושאים לפני שמתחילים ללמוד.
אנחנו מגיעים לאחד הנושאים המורכבים ביותר מבחינת הבנה עבור מתכנתים מתחילים. הנושא הזה נקרא רקורסיה, באנגלית רקורשן. רקורסיה זאת הפעולה שבה פונקציה קורית לעצמה ויש המון שימושים עם הקונספט הזה שאנחנו בונים פונקציה שבמהלך הפונקציה הפונקציה בעצם קורית לעצמה ואז מתחילה להתבצע מההתחלה כאילו במופע חדש לגמרי
שמנותק מהמופע הקודם של הפונקציה הנוכחית. אם אתם פותחים את המילון במילה רקורסיה, אתם רואים ראה רקורסיה. זאת כמובן איזושהי בדיחה של מתכנתים, אבל גם לגוגל יש חוש הומור.
אם אתם נכנסים לגוגל ורושמים רקורשן, כמובן אין לי פה שום טעות, גוגל תגיד לכם בדיומין רקורשן. אתם לוחצים על זה ואתם מגיעים ל"בדיומים רקורשן" גם כן בדיחה של גוגל.
אז בעצם בואו נראה פעילות מסוימת של רקורסיה ובהמשך אנחנו נראה מתי באמת משתמשים עם זה. נניח שאנחנו רוצים לבנות פונקציה פשוטה שמקבלת מספר ומציגה כוכביות כאורך המספר אם אנחנו נבנה אותה אז אנחנו נבנה אותה בצורה מאוד פשוטה print stars מקבלת int n יש לנו פה איזושהי הילולה שרצה מ-1 עד n נתחיל ב-1 ונסתיים ב-n ומה שנעשה זה פשוט נציג כוכבית על המסך
וכך בעצם הצגנו n כוכביות. נקראים stars 10 ויש לנו 10 כוכביות. בואו נדפיס אותם בשורה אחת ויש לנו 10 כוכביות בשורה אחת.
זאת לא רקורסיה מפני שהפונקציה לא קורית לעצמה, פשוט יש בו לולאה. זה לא אומר שברקורסיה אין לולאה אבל ספציפית בואו נבנה אותה רקורסיה ונראה האם באמת אנחנו צריכים לולאה במקרה הזה.
אז אם אנחנו רוצים לקחת את הפעילות הזאת ובמקום לעשות את הפעילות הזאת בצורה של לולאה בצורה איטרטיבית מה שנקרא אנחנו רוצים לעשות אותה בצורה רקורסיבית כלומר הפונקציה מבצעת פעולה וקוראת לעצמה עוד פעם בשביל להמשיך לבצע את
שאר המטלות אבל אנחנו צריכים להבין איך בדיוק אפשר לבנות רקורסיה מה הנוהל הנכון לבנייה של רקורסיה. אז בעצם בנייה של רקורסיה מורכבת מארבעה צעדים.
נתחיל לראות בדיוק את ארבעת הצעדים לבנייה של פונקציה רקורסיבית. הצעד הראשון זה צעד שמדבר על החתימה של הפונקציה, כלומר הכותרת שלה, מה הפונקציה מחזירה, מה השם שלה ומה היא מקבלת.
והנוהל אומר כזה דבר, ברוב רוב המקרים, הנוהל הזה הוא לא באמת מוחלט ב-100% אבל ברוב הגדול של המקרים החתימה של פונקציה רקורסיבית תהיה זהה לחתימה של פונקציה שהיא אינה רקורסיבית.
זאת אומרת, אם אנחנו רוצים פונקציה שמקבלת מספר ומציגה n כוכביות תתלות במספר שהיא קיבלה, מספר n ומציגה n כוכביות, זה אומר שהחתימה של הפונקציה הזאת צריכה להיות כזאת שמקבלת int n מחזירה void וזה לא משנה אם אנחנו כותבים אותה בצורה איטרטיבית כמו שעשינו כרגע או בצורה רקורסיבית.
אז זה הנוהל הראשון. הנוהל השני אומר, או יותר נכון הצד השני אומר, שאנחנו צריכים לארגן בתוך הפונקציה משהו שנקרא תנאי עצירה.
בדרך כלל אנחנו נבדוק את התנאי הזה כדבר הראשון בתוך הפונקציה. עכשיו, מה זה אומר תנאי עצירה? תנאי עצירה אומר שאנחנו צריכים לבדוק האם להפסיק בעצם לבצע את הקריאות החוזרות והנשנות האלה, או לא להפסיק ואז כמובן אנחנו נקרא לעצמנו עוד פעם ועוד פעם. תנאי עצירה תמיד מורכב
מאיף, או לרוב מורכב מאיף. עכשיו, בואו נחשוב מה התנאי עצירה שיש לנו. מהו הפרמטר שאם אנחנו שולחים לנו את הערך שלו אנחנו לא רוצים להמשיך ולבצע דבר אז הפרמטר כמובן הוא 0 אם מישהו מביא לי 0 לפונקציה ואומר לי תדפיס לי בבקשה 0 כוכביות אז אני לא רוצה להדפיס לו שום כוכבית ואני מיד רוצה לצאת זאת אומרת תנאי העצירה
במקרה הזה אנחנו צריכים לבדוק האם n שווה 0 אם כן אני לא מבצע שום דבר ויוצא זה צעד מספר 2 בנוהל צעד ראשון היה חתימה, צעד שני תנאי עצירה.
צעד השלישי בנוהל אומר שעל הפונקציה להסתכל על כל המטלה שדרושה לביצוע. מהי כל המטלה שדרושה לביצוע? בואו נחשוב. כל המטלה שדרושה לביצוע זה להציג n כוכביות.
צעד השלישי בנוהל אומר מכל המטלה הזאת תעשה פעולה אחת ויחידה. זאת אומרת אם כל המטלה זה להדפיס n כוכביות, פעולה אחת ויחידה תהיה להדפיס כוכבית אחת. ולכן אנחנו בלי שום לולאה מציגים כוכבית אחת. את זה אפשר למחוק.
בואו נמספר פה את השלבים בינתיים שיש לנו. שלב ראשון וחתימה. צעד שני, תנאי יציאה. צעד שלישי בנוהל, ביצוע של מטלה אחת מכל הפעולה שאנחנו צריכים לבצוע.
או שלב אחד. שלב אחד מתוך כל המטלה לביצוע. עכשיו, השלב האחרון הכי חשוב, כאן זה בעצם הקריאה הרקורסיבית לפונקציה עצמה ואנחנו צריכים לשלוח לה את שאר המטלה לביצוע.
זאת אומרת print stars ואנחנו צריכים לשלוח לה את מה שנשאר כי אנחנו הרי כבר ביצענו שלב אחד. אז אם אנחנו רוצים להדפיס n כוכביות ואנחנו כבר הדפסנו כוכבית כמובן שנשארנו להדפיס n ממסכת שלב מספר 4 recursive call with task - the stage performed זאת אומרת אנחנו צריכים לשלוח את שאר המטלה פחות השלב שכבר ביצענו עכשיו הערה
לגבי הקריאה הרקורסיבית למרות שאנחנו כרגע נמצאים במצב שבו אנחנו בונים את הפונקציה print stars או כל פונקציה רקורסיבית אחרת אנחנו צריכים להניח שהיא עובדת כמו שצריך וכבר מוכנה אפילו שאנחנו עדיין בבנייה של הפונקציה ולכן אם אנחנו מניחים שהיא עובדת בצורה טובה
אנחנו יכולים לקרוא לה ולשלוח לה את הערכים הדרושים. הערה נוספת, האם זה בסדר לשלוח לה n++? תשובה, לא. מפני ש-n++ מבצע את הקידום אחרי השליחה.
זאת אומרת שאם מישהו מביא לי 3 כאן, הייתי רוצה לשלוח 2, אבל למעשה אני אשלח 3, כי הקידום יתבצע אחרי השליחה. אז בעצם זה יהיה מצב של קריאה אינסופית ל-recursor.
האם זה הגיוני לבצע n++? גם לא. מפני שגם כאן אני שולח עדיין 3 אם שלחו לי 3 ובואו ניקח את המקרה הזה שלחו לי 10 אני רוצה לשלוח 9 אני אשלח 10 ורק אחר כך אנחנו נוריד 1 זאת אומרת שגם כאן תהיה קביעה אינסופית האם זה בסדר לשלוח מינוס מינוס אז למעשה זה יעבוד מפני שקודם כל אנחנו מורידים את ה-10 שקיבלנו ל-9 ואז שולחים 9 אבל הפעולה הזאת
היא מיותרת מפני שאין לנו צורך לשנות את n ולכן הפעולה הכי נכונה פשוט לשלוח n ממסכה בואו נריץ את זה ונראה ששוב פעם קיבלנו 10 כוכביות על המסך פעם ביצענו את הפונקציה הזאת בצורה רקורסיבית חשוב לנו להבין מה קרה פה בזיכרון בואו נסתכל רגע על איזושהי פרזנטציה שתעזור לנו להבין מה בעצם קורה כאן בפרינט
סטארס בואו נריץ שלב שלב את הפרזנטציה הזאת ונראה מה קרה כאשר קראנו לפונקציה בהתחלה היה לנו את המיין קראנו לפרינט סטארב, בואו נניח ששלחנו שלוש ואנחנו רוצים להדפיס שלוש כוכביות.
מכאן התחילה הפונקציה, ושימו לב ש-n שווה שלוש. אז כאן התבצעה בדיקה האם n שווה 0, תשובה פולס, פסנו כוכבית אחת, זאת הכוכבית הראשונה שפסנו.
ואז קראנו שוב פעם לפונקציה ושלחנו n פחות 1, אם n שלוש שלחנו 2. אבל הנקודה הכי חשובה להבין כרגע היא שכאשר קראנו עוד פעם לפונקציה בעצם נפתח כאילו מופע חדש של הפונקציה.
כל המשתנים הפנימיים של הפונקציה הוטחלו מחדש, אלו משתנים אחרים, זה לא שהפונקציה כאילו מתחילה מההתחלה ומשנה את המשתנים הנוכחיים, או שהם אותו הדבר וממשיכים מאותו שלב.
כל מתחיל מההתחלה. ולכן, אנחנו עכשיו התחלנו מופע חדש של הפונקציה ו-n הוא 2, כאשר המופע הקודם תלוי ונשאר בזיכרון וממתין עד שהמופע הזה שקראנו כרגע יסתיים.
אוקיי, n שווה 2, אז הוא לא שווה 0. אנחנו מדפיסים כוכבית שנייה. פה זה היה הדפסה ראשונה, פה זה הדפסה שנייה. שוב פעם מבצעים קריאה רקורסיבית, הפעם שולחים 1.
2 פחות 1 זה 1. עוד פעם נפתח מופע, n מקבל 1, 1 לא שווה 0, אנחנו לא נכנסים ל-return, מדפיסים כוכבית מספר 3.
שוב פעם מתבצעת קריאה רקורסיבית, כל הפעם שולחים 0. מכאן יש פה קריאה אגרוסיבית נוספת, הפעם n שווה 0. יש פה את הריטרן.
מיד אנחנו חוזרים ומסיימים את המופע הזה, מופע מספר 4. מגיעים למופע מספר 3 בגלל שזאת הפקודה האחרונה שיש כאן, מסיימים את מופע מספר 3. חוזרים בחזרה מסיימים