>> ZAMYLA: על מנת להבין רקורסיה, עליך
הראשונה מבין רקורסיה.
לאחר רקורסיה באמצעי עיצוב תכנית שיש לך קשרים עצמיים
הגדרות.
מבני נתונים רקורסיבית, למשל, הם מבני נתונים ש
כולל את עצמם ב ההגדרות שלהם.
אבל היום, אנחנו הולכים להתמקד על פונקציות רקורסיבית.
>> נזכיר כי פונקציות לקחת תשומות, טיעונים, ולהחזיר ערך כמוהם
פלט המיוצג על ידי תרשים זה כאן.
אנחנו נחשוב על התיבה כגוף של הפונקציה, המכילה הסדרה של
הוראות שמפרשות קלט ולספק פלט.
במבט מעמיק יותר בתוך הגוף של הפונקציה יכולה לחשוף שיחות
פונקציות אחרות גם כן.
קח את התפקיד הזה פשוט, foo, כי לוקח מחרוזת אחת כקלט ו
הדפסים כמה אותיות יש מחרוזת ש.
Strlen הפונקציה, לאורך מחרוזת, הוא נקרא, שתפוקתם היא
הנדרש לקריאה לprintf.
>> עכשיו, מה עושה פונקציה רקורסיבית מיוחד הוא שזה קורא לעצמו.
אנחנו יכולים לייצג רקורסיבית זה להתקשר עם החץ הכתום הזה
לולאה חזרה לעצמו.
אבל ביצוע עצמו שוב רק יהיה לעשות עוד שיחה רקורסיבית, ו
עוד אחד ועוד.
אבל פונקציות רקורסיבית לא יכול להיות אינסופי.
הם צריכים בסופו איכשהו, או שלך תכנית תפעל לנצח.
>> אז אנחנו צריכים למצוא דרך לשבור מתוך השיחות רקורסיבית.
אנחנו קוראים לזה במקרה הבסיס.
כאשר מקרה בסיס התנאי מתקיים, הפונקציה מחזירה מבלי לבצע
אחר קריאה רקורסיבית.
קח את התפקיד הזה, היי, פונקציה מבוטלת שלוקח n int כקלט.
מקרה הבסיס מגיע ראשון.
אם n הוא פחות מאפס, ביי והדפסה תמורה לכל המקרים האחרים,
הפונקציה תדפיס היי ולבצע הקריאה רקורסיבית.
שיחה נוספת להיי הפונקציה עם ערך קלט מופחת.
>> עכשיו, למרות שאנחנו להדפיס היי, פונקציה לא תסתיים עד ש
לחזור סוג ההחזרה שלו, במקרה החלל הזה.
אז לכל n אחר מאשר מקרה הבסיס, היי בפונקציה זו תחזיר ההיי
של n מינוס 1.
מאז פונקציה זו אם כי הוא בטל, אנחנו לא באופן מפורש הקלד לחזור לכאן.
אנחנו פשוט להפעיל את הפונקציה.
אז קורא היי (3) יודפס היי ו ביצוע היי (2), אשר מבצע היי (1) אחד
אשר מבצע היי (0), שבו מקרה בסיס תנאי מתקיים.
אז היי (0) מדפיס שלום וחוזר.
>> על אישור.
אז עכשיו שאנחנו מבינים את היסודות של פונקציות רקורסיבית, שהם צריכים
מקרה בסיס אחד לפחות, כמו גם קריאה רקורסיבית, בואו נעבור ל
דוגמא משמעותית יותר.
אחד שלא רק יחזור ביטול לא משנה מה.
>> בואו נסתכל על העצרת פעולה הנפוצה ביותר ב
חישובי הסתברות.
עצרת של n היא התוצר של כל מספר חיובי פחות מ
ושווה ל-n.
חמישה אז עצרת הוא 5 פעמים 4 פעמים 3 פעמים 2 פעמים 1 לתת 120.
ארבע עצרת היא 4 פעמים 3 פעמים 2 פעמים 1 לתת 24.
ואת אותו כלל חל לכל מספר שלם חיובי.
>> אז איך אנחנו יכולים לכתוב רקורסיבית פונקציה שמחשבת את העצרת
של מספר?
ובכן, אנחנו נצטרך לזהות שתי מקרה בסיס והקריאה רקורסיבית.
הקריאה רקורסיבית לא תהיה אותו הדבר בכל המקרים, פרט לבסיס
מקרה, מה שאומר שנצטרך למצוא דפוס שייתן לנו שלנו
תוצאה רצויה.
>> בדוגמה זו, לראות איך עצרת 5 כרוך הכפלת 4 ב -3 על ידי 2 ב -1
וממש באותו כפל נמצא כאן,
הגדרה של 4 עצרת.
כך אנו רואים כי 5 עצרת היא רק 5 פעמים עצרת 4.
עכשיו אין דפוס זה חלים ל4 עצרת גם כן?
כן.
אנו רואים כי 4 עצרת מכילה את כפל 3 פעמים 2 פעמים 1,
מאוד הגדרה כ3 עצרת.
אז 4 עצרת שווה ל 4 פעמים 3 עצרת, וכן הלאה וכן הלאה
דפוס מקלות עד עצרת 1, אשר מעצם הגדרתו הוא שווה ל 1.
>> אין חיובי אחרים מספרים שלמים עזבו.
אז יש לנו את הדפוס עבור הקריאה רקורסיבית שלנו.
n העצרת שווה לפעמי n העצרת של n מינוס 1.
ומקרה הבסיס שלנו?
שרק אהיה ההגדרה שלנו של עצרת 1.
>> אז עכשיו אנחנו יכולים לעבור לכתיבה קוד לפונקציה.
למקרה הבסיס, תהיה לנו n המצב שווה שווה 1, שבו
נחזור 1.
לאחר מכן לנוע על הקריאה רקורסיבית, נחזור פעמים n
עצרת של n מינוס 1.
>> עכשיו בואו לבודקנו זה.
בואו ננסה עצרת 4.
לפונקציה שלנו זה שווה עד 4 פעמים עצרת (3).
העצרת (3) שווה ל 3 פעמים עצרת (2).
העצרת (2) שווה ל 2 פעמים עצרת (1), שמחזיר 1.
עצרת (2) החברה מחזירה 2 פעמים 1, 2.
עצרת (3) יכולה עכשיו לחזור 3 פעמים 2, 6.
ולבסוף, עצרת (4) מחזיר 4 פעמים 6, 24.
>> אם אתה נתקלת בכל קושי עם הקריאה רקורסיבית, להעמיד פנים ש
הפונקציה עובדת כבר.
מה שאני מתכוון זה שאתה צריך סומך על השיחות רקורסיבית לחזור
הערכים תקין.
למשל, אם אני יודע ש עצרת (5) שווה פי 5
עצרת (4), אני הולך לתת אמון כי עצרת (4) תיתן לי 24.
תחשבו על זה כעל משתנה, אם אתה יהיה, כאילו אתה כבר הוגדר
עצרת (4).
אז לכל עצרת (n), זה המוצר של n ו
העצרת הקודמת.
ועצרת קודמת זה מתקבל על ידי קורא
עצרת של n מינוס 1.
>> עכשיו, לראות אם אתה יכול ליישם רקורסיבית לתפקד בעצמך.
טען עד המסוף שלך, או run.cs50.net, ולכתוב סכום פונקציה
שלוקח n מספר שלם ומחזיר את סכום של כל ברציפות החיובית
מספרים שלמים מ n עד 1.
שכתבתי את הסכומים של כמה ערכים שיעזרו לך שלנו.
ראשית, להבין את מקרה בסיס מצב.
ואז, מסתכל על הסכום (5).
האם אתה יכול להביע את זה במונחים מסכום אחר?
עכשיו, מה עם סכום (4)?
איך אתה יכול להביע את הסכום (4) במונחים של סכום אחר?
>> ברגע שיש לך סכום (5) וסכום (4) באו לידי ביטוי במונחים של סכומים אחרים, ראה
אם אתה יכול לזהות דפוס לסכום (n).
אם לא, נסה כמה מספרים אחרים ולבטא אותם בסכומים
מבחינת מספרים אחר.
על ידי זיהוי דפוסים לבדידים מספרים, אתה גם על הדרך שלך
זיהוי הדפוס לכל n.
>> רקורסיה היא כלי חזק באמת, אז כמובן שזה לא מוגבל ל
פונקציות מתמטיות.
ניתן להשתמש ברקורסיה בצורה יעילה מאוד כאשר מדוברים בעצים למשל.
עזיבה הקצרה על עצים עבור ביקורת מעמיקה יותר, אך לעת עתה
זוכר שעצי החיפוש בינארי, ב בפרט, בנויים מצומת, כל אחד
עם ערך ושני מצביעי צומת.
בדרך כלל, זה מיוצג על ידי צומת הורה שיש הצבעה שורה אחת
לצומת הילד השמאלית ואחד לצומת הילד הנכונה.
המבנה של חיפוש בינארי עץ משאיל את עצמו היטב
לחיפוש רקורסיבית.
הקריאה רקורסיבית עוברת גם ב שמאל או את הצומת הנכונה, אבל יותר
מזה בטווח הקצר העץ.
>> תגיד אתה רוצה לבצע פעולה על כל צומת בעץ בינארי.
איך שאתה יכול ללכת על זה?
ובכן, אתה יכול לכתוב רקורסיבית פונקציה שמבצעת את הפעולה
בצומת ההורה וגורם רקורסיבית להתקשר לאותו התפקיד,
עובר בצד השמאל ו בלוטות לילד נכון.
לדוגמא, בפונקציה זו, foo, כי משנה את הערך של צומת נתון ו
כל הילדים שלה עד 1.
מקרה הבסיס של גורמי צומת null הפונקציה לחזור, המציין
שאין כל צמתים עזב שבתת עץ.
>> בואו לעבור את זה.
ההורה הראשון הוא 13.
אנחנו משנים את הערך ל 1, ואז להתקשר הפונקציה שלנו בצד השמאל, כמו גם
כנכון.
הפונקציה, foo, נקראת משמאל תת עץ ראשון, ולכן את הצומת השמאלית
יוקצה מחדש לfoo 1 ויהיה להיקרא על הילדים של הצומת ש,
ראשון משמאל ולאחר מכן ימינה, וכן הלאה וכן הלאה.
ולומר להם שאין להם סניפים כל עוד ילדים כל כך את אותו התהליך
ימשיך לילדים תקין עד צמתים השלם של העץ הם
מחדש ל1.
>> כפי שאתה יכול לראות, אתה לא מוגבל רק אחד קריאה רקורסיבית.
בדיוק רבים ככל יקבל את העבודה.
מה אם היה לך עץ שבו כל הייתה לי צומת שלושה ילדים,
שמאל, באמצע, ונכון?
איך היית לערוך foo?
ובכן, פשוט.
רק להוסיף עוד קריאה רקורסיבית ו תעבור במצביע צומת אמצע.
>> רקורסיה היא חזקה מאוד ולא להזכיר אלגנטי, אבל זה יכול להיות
מושג קשה בהתחלה, כדי להיות סבלני ולקחת את הזמן שלך.
התחל עם מקרה הבסיס.
זה בדרך כלל הקל לזהות, ואז אתה יכול לעבוד
לאחור משם.
אתה יודע שאתה צריך להגיע אליך מקרה בסיס, ולכן כוח ש
אתן לך כמה רמזים.
נסה לבטא מקרה אחד ספציפי ב מבחינת מקרים אחרים, או בתת קבוצות.
>> תודה על צפייה את זה קצר.
לכל הפחות, עכשיו אתה יכול מבין בדיחות כמו זה.
השם שלי הוא Zamyla, וזה cs50.
>> קח את התפקיד הזה, היי, פונקצית חלל שלוקחת
int, n, כקלט.
מקרה הבסיס מגיע ראשון.
אם n הוא פחות מ 0, הדפסה "שלום" ולחזור.