[השמעת מוסיקה] 

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

אתה לקמפל את זה. אתה מפעיל את התכנית. אתה טוב ללכת. 

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

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

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

אז 5 עצרת היא 5 פעמים 4 פעמים 3 פעמים 2 פעמים 1. ו -4 עצרת היא 4 פעמים 3 פעמים 2 פעמים 1 וכן הלאה. אתה מבין את הרעיון. 

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

אז הנה כמה משחק מילים facts-- intended-- על factorial-- פונקצית עצרת. העצרת של 1, כפי שאמרתי, היא 1. העצרת של 2 היא 2 פעמים 1. העצרת של 3 היא 3 פעמים 2 פעמים 1, וכן הלאה. דברנו על 4 ו -5 כבר. 

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

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

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

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

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

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

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

איזו ממראה של אלה כמו במקרה הבסיס כאן? שאחד מאלה נראה כמו פתרון הפשוט לבעיה? יש לנו חבורה של עצרות, ואנחנו יכולים להמשיך הולך on-- 6, 7, 8, 9, 10, וכן הלאה. 

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

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

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

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

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

אם אנחנו לוקחים את העצרת של 3, זה 3 פעמים את העצרת של 3 מינוס 1, או 2. ולכן אם אנחנו לא מסתכל על 1, אחרת פעמים n התמורה עצרת של n מינוס 1. זה די פשוט. 

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

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

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

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

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

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

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

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

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

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

אולי אתה זוכר מ ימי בית ספר יסודיים שרצף פיבונאצ'י מוגדר כמו זה-- האלמנט הראשון הוא 0. האלמנט השני הוא 1. שני אלה הם רק על ידי הגדרה. 

אז כל אלמנט אחר מוגדר כסכום של n מינוס 1 ומינוס 2 n. אז האלמנט השלישי יהיה 0 בתוספת 1 הוא 1. ואז האלמנט הרביעי יהיה האלמנט השני, 1, בתוספת האלמנט השלישי, 1. וזה יהיה 2. וכן הלאה וכן הלאה. 

אז במקרה הזה, יש לנו שני מקרי בסיס. אם n הוא שווה ל 1, 0 לחזור. אם n הוא שווה ל 2, 1 חזור. אחרת, תחזור פיבונאצ'י של n מינוס 1 בתוספת פיבונאצ'י של n מינוס 2. 

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

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

אחרת, לעבור את זה תהליך שוב על n מתחלק ב -2. ולראות אם אתה יכול לחזור ל1. אחרת, אם n הוא מוזר, לעבור תהליך זה שוב על 3 יד בתוספת 1, או 3 פעמים n בתוספת 1. אז הנה יש לנו מקרה בסיס יחיד. אם n הוא שווה ל 1, לעצור. אנחנו לא עושים שום רקורסיה יותר. 

אבל יש לנו שני מקרים רקורסיבית. אם n הוא גם, שאנחנו עושים רקורסיבית אחת מקרה, קורא מחולק n על ידי 2. אם n הוא מוזר, אנחנו עושים שונים מקרה רקורסיבית על 3 פעמים n בתוספת 1. 

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

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

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

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

במשך 3, כפי שניתן לראות, יש לא מעט שלבים כרוכים. אתה הולך מ 3. ואז אתה הולך ל 10, 5, 16, 8, 4, 2, 1. זה לוקח שבעה צעדים כדי לחזור ל1. וכמו שאתה יכול לראות, יש כמה מקרי מבחן אחרים כאן כדי לבדוק את התכנית שלך. אז שוב, להשהות את הווידאו. ואני אלך עכשיו לקפוץ חזרה ל מה התהליך בפועל הוא כאן, מה היא השערה זו. 

תראה אם ​​אתה יכול להבין איך להגדיר Collatz של n כך שהיא מחשבת כמה צעדים שנדרש כדי להגיע ל1. אז אני מקווה, שעצרת את הווידאו ואתה לא רק מחכה לי כדי לתת לך את התשובה כאן. אבל אם אתה, גם, הנה התשובה בכל מקרה. 

אז הנה הגדרה אפשרית של פונקצית Collatz. הבסיס שלנו case-- אם n הוא שווה ל -1, אנו חוזרים 0. זה לא לוקח כל צעדים כדי לחזור ל1. 

אחרת, יש לנו שתי cases-- רקורסיבית אחד מספרים אפילו ואחד למוזר. דרכי לבדוק למספרים אפילו הוא לבדוק אם n mod 2 שווה 0. זהו בעצם, שוב, שואל את השאלה, אם אתה זוכר מה הוא-- mod אם אני n הפרד על ידי 2 שאין שארית? זה יהיה גם מספר. 

ולכן אם n mod 2 שווה 0 הוא בדיקה היא זה אפילו מספר. אם כך, אני רוצה לחזור 1, כי זה בהחלט לוקח צעד אחד בתוספת של Collatz מה מספר הוא חצי ממני. אחרת, אני רוצה לחזור 1 בתוספת 3 פעמים Collatz של n בתוספת 1. זה היה אחר צעד רקורסיבית ש יכול לקחת כדי לחשב את Collatz-- מספר הצעדים שנדרש כדי לחזור עד 1 ניתנה מספר. אז אני מקווה, דוגמא זו נתתי לך קצת של טעם של נהלים רקורסיבית. יש לקוות, אתה חושב קוד הוא קצת יותר יפה אם ייושם בדרך אלגנטית, רקורסיבית. אבל גם אם לא, רקורסיה היא כלי באמת חזק בכל זאת. ואז זה בהחלט משהו כדי לקבל את הראש שלך בסביבה, כי אתה יכול ליצור תוכניות די מגניבים באמצעות רקורסיה כי אחר עלולים להיות מורכב לכתוב אם אתה משתמש בלולאות ואיטרציה. אני דאג לויד. זה CS50.