Writing Recursion

בלי כתוביותעם כתוביות

Writing Recursion

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

נושאי הסיכום המוצגים בשיעור:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

סיכום:

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

בשיעור הבא נעסוק בנושא Recursion Diagram.

פרקי ההרצאה: Writing Recursion

תמלול ההרצאה: Writing Recursion

הטקסט המלא של הדקות הראשונות בהרצאה «Writing Recursion» בקורס הווידאו של PracticU – כתוביות בעברית עם זמן התחלה לכל פסקה. כך תוכלו לקרוא ולחפש את הנושאים לפני שמתחילים ללמוד.

00:02
אז בואו ניישם את ארבעת העקרונות האלה בכדי לכתוב פונקציות רקורסיביות. הפונקציה הראשונה שנכתוב זאת בעצם הפונקציה שדיברנו עליה שמציגה n כוכביות. אז בואו נראה מה בעצם השלבים לבנייה של הפונקציה.
00:20
אם אני רוצה להציג n כוכביות בפונקציה, אז אני אבנה אותה באותה החתימה כמו פונקציה רגילה, זה היה השלב הראשון. בואו ניקח static void, print stars זה השם שלה והיא תקבל n.
00:35
הנה כבר השלב הראשון. השלב הראשון, בואו נרשום את זה כאן, function, signature. השלב הבא זה תנאי יציאה, מתי אני לא רוצה להמשיך ולבצע את הקוד של הפונקציה, exit condition.
01:01
בואו נראה, יהיה לי פה if ואנחנו צריכים לחשוב מתי בעצם אנחנו לא רוצים לבצע כלום. אם שולחים לנו לדוגמה n שווה 8, ברור שאני רוצה לבצע משהו.
01:13
אם שולחים לי n שווה 120, אני רוצה לבצע משהו, אפילו אם שולחים לי n שווה 1. אבל אם שולחים לי n שווה 0 או n שלילי, אין לי מה לעשות כרגע בפונקציה.
01:25
אז בואו נניח אם n קטן או שווה ל-0, return, צא לגמרי מהפונקציה ואל תבצע שום דבר. הנה יש לנו פה את הכלל השני, exit condition.
01:38
הכלל השלישי היה do one part from the entire task. בואו נבצע רק שלב אחד. רצינו להציג n כוכביות, שלב אחד יהיה להציג כוכבית אחת אז בואו נציג רק כוכבית אחת והשלב האחרון זה שליחה לפונקציה עצמה את שאר המטלה send the rest of the task to that function אז בואו נקרא שוב פעם לפרינט סטארס ושימו לב שאנחנו עדיין
02:21
בבנייה של פרינט סטארס אבל אני כבר יודע שאם עשיתי את הכל כמו שצריך היא עובדת פרפקט גם אם הקריאה הזאת הייתה לדוגמה כאן יכול להיות שהקריאה לפעמים היא לפני, אז אנחנו צריכים להניח שהכל בסדר.
02:37
עכשיו, מה אנחנו בעצם רוצים לשלוח? אנחנו רוצים לשלוח לא את n אלא את n פחות 1. אנחנו לא נשלח n מינוס מינוס, זה ברור שלא, כי אז אנחנו נשלח את אותו ה-n, ואנחנו גם לא נשלח מינוס מינוס n, כי אין צורך להוריד את ה-n.
02:53
אנחנו נשלח n פחות 1, קצת יותר יעיל. פה סיימנו לבנות את הפונקציה הרקורסיבית, ואנחנו רוצים לקרוא לה ולבדוק שהיא עובדת כמו שצריך.
03:03
סטרינט סטארס ובואו נשלח 5 נריץ ונראה שיש לנו על המסך 5 כוכביות. בואו ננסה לשלוח 1 ונראה על המסך שיש לנו כוכבית 1. 10 ונראה על המסך שיש לנו 10 כוכביות.
03:21
הפונקציה עובדת בצורה רקורסיבית לא היינו צריכים פה שום לולאה זה לא אומר שבפונקציות רקורסיביות אין לולאות יכול להיות בהחלט שיש אבל לא תמיד צריך כרגע אני לא צריך שום לולאה.
03:35
בואו נבנה פונקציה רקורסיבית נוספת. פעם הפונקציה מחזירה ערך. שימו לב שהפונקציה הקודמת שבנינו רק הציגה דברים על המסך. הפונקציה הבאה מחזירה אינטג'ר ובואו נגיד שאנחנו רוצים את הסכום של כל המספרים עד n.
03:56
סכום המספרים יהיה 1 ועוד 2 ועוד 3 ועוד 4 וכולי עד n. 1 ועוד 2 ועוד 3 ועוד עד n. למעשה זה בדיוק אותו הדבר כמו n ועוד n פחות 1 ועוד n פחות 2 ועוד, עד שאנחנו מגיעים בחזרה ל-1, זה בדיוק אותו הסכום.
04:23
אז מה אנחנו עושים? אז זאת החתימה של הפונקציה, קודם כל. הדבר הבא זה תנאי עצירה. מה בעצם צריך לקרות כשאנחנו יודעים שאין לנו יותר מה להמשיך?
04:34
אז בוא נניח שאנחנו רוצים לתמוך בפונקציה עם n חיובי בלבד, ושוב פעם, התנאי העצירה דומה לתנאי העצירה הקודם. אם n קטן או שווה ל-0, תחזיר לי 0.
04:47
כלומר, אין לי פה סכום איברים שאני יכול להחזיר. אני לא יכול לבצע ריטרן בצורה כזאת, מפני שהפונקציה מוגדרת ככזו שהיא מחזירה אינטג'ר.
04:56
אז נחזיר 0. עכשיו, אנחנו רוצים להחזיר רק שלב 1. שלב 1 מכל החיבורים האלה יהיה רק להחזיר את n. ריטרן n, אבל אם אני מבצע ריטרן, זהו, סיימתי.
05:17
לא הגיוני שאני אחזיר את n, אני צריך לבצע פה גם קריאה רקורסיבית. אז אני רוצה להחזיר את n ולחבר אותו עם שאר המטלה לביצוע.
05:27
זה יהיה החלק הנוכחי. שאר המטלה זה החיבורים של כל אלה. את n כבר אנחנו סוכמים פה, נשאר לנו לסכום את כל היתר, n פחות 1 ועוד n פחות 2 וכדומה.
05:42
כאן אנחנו יכולים לקרוא קריאה רקורסיבית ל-get summary ולשלוח את n פחות 1. בואו נצמצם פה טיפה ונקרא לפונקציה הזאת.
05:55
בואו נציג את הסכום של כל המספרים מ-1 עד 10. הסכום אמור להיות 55. בואו נריץ, והנה אנחנו רואים שיש לנו 55. בואו נבצע פה איזה הצגה כזאת.
06:19
sum of 1 to 10, 55. הכל עובד פרפקט.