זאַמילאַ: אין סדר צו פֿאַרשטיין רעקורסיאָן, איר מוזן ערשטער פֿאַרשטיין רעקורסיאָן. ווייל רעקורסיאָן אין פּראָגראַם פּלאַן מיטל אַז איר האָבן זיך-רעפערענטיאַל זוך. רעקורסיווע דאַטן סטראַקטשערז, פֿאַר בייַשפּיל, זענען דאַטן סטראַקטשערז אַז אַרייַננעמען זיך אין זייער זוך. אבער הייַנט, מיר ניטאָ געגאנגען צו פאָקוס אויף רעקורסיווע פאַנגקשאַנז. 

צוריקרופן אַז פאַנגקשאַנז נעמען ינפּוץ, טענות, און קריק אַ ווערט ווי זייער רעזולטאַט רעפּריזענטיד דורך דעם דיאַגראַמע דאָ. מיר וועט טראַכטן פון די קאַסטן ווי די גוף פון די פֿונקציע, מיט די סכום פון ינסטראַקשאַנז אַז טייַטשן די אַרייַנשרייַב און צושטעלן אַ פּראָדוקציע. גענומען אַ נעענטער קוקן ין דער גוף פון די פֿונקציע קען אַנטדעקן רופט צו אנדערע פאַנגקשאַנז ווי געזונט. נעמען דעם פּשוט פֿונקציע, פו, אַז נעמט אַ איין שטריקל ווי אַרייַנשרייַב און פּרינץ ווי פילע אותיות אַז שטריקל האט. די פֿונקציע סטרלען, פֿאַר שטריקל לענג, איז גערופן, וועמענס פּראָדוקציע איז פארלאנגט פֿאַר די רופן צו פּרינטף. 

איצט, וואָס מאכט אַ רעקורסיווע פונקציאָנירן ספּעציעל איז אַז עס רופט זיך. מיר קענען פאָרשטעלן דעם רעקורסיווע רופן מיט דעם מאַראַנץ פייַל לופּינג צוריק צו זיך. אבער עקסאַקיוטינג זיך ווידער וועט בלויז מאַכן אנדערן רעקורסיווע רופן, און אנדערן און אנדערן. אבער רעקורסיווע פאַנגקשאַנז קענען ניט זיין ינפאַנאַט. זיי האָבן צו סוף עפעס, אָדער דיין פּראָגראַם וועט לויפן אויף אייביק. 

אַזוי מיר דאַרפֿן צו געפינען אַ וועג צו ברעכן אויס פון די רעקורסיווע רופט. מיר רופן דעם די באַזע פאַל. ווען די באַזע פאַל צושטאַנד איז באגעגנט, די פֿונקציע קערט אָן מאכן אן אנדער רעקורסיווע רופן. נעמען דעם פֿונקציע, הי, אַ פּאָסל פונקציאָנירן וואס נעמט אַ ינט N ווי אַרייַנשרייַב. די באַזע פאַל קומט ערשטער. אויב N איז ווייניקער ווי נול, דרוקן ביי און צוריקקומען פֿאַר אַלע אנדערע קאַסעס, די פונקציאָנירן וועט דרוקן הי און ויספירן די רעקורסיווע רופן. אן אנדער רופן צו די פֿונקציע הי מיט אַ דעקרעמענטעד אַרייַנשרייַב ווערט. 

איצט, אפילו כאָטש מיר דרוקן הי, די פונקציאָנירן וועט ניט פאַרענדיקן ביז מיר צוריקקומען זייַן צוריקקומען טיפּ, אין דעם פאַל פּאָסל. אַזוי פֿאַר יעדער N אנדערע ווי די באַזע פאַל, דעם פונקציאָנירן הי וועט צוריקקומען הי פון N מינוס 1. זינט דעם פֿונקציע איז פּאָסל כאָטש, מיר וועט ניט בפירוש טיפּ צוריקקומען דאָ. מיר וועט נאָר ויספירן די פֿונקציע. אַזוי פאַך הי (3) וועט דרוקן הי און ויספירן הי (2) וואָס עקסאַקיוץ הי (1) איינער וואָס עקסאַקיוץ הי (0), ווו די באַזע פאַל צושטאַנד איז באגעגנט. אַזוי הי (0) פּרינץ ביי און קערט. 

גוט. אַזוי איצט אַז מיר פֿאַרשטיין די באַסיקס פון רעקורסיווע פאַנגקשאַנז, אַז זיי דאַרפֿן לפּחות איין באַזע פאַל ווי געזונט ווי אַ רעקורסיווע רופן, לאָזן ס מאַך אויף צו אַ מער מינינגפאַל בייַשפּיל. איינער וואס טוט ניט נאָר צוריקקומען פּאָסל קיין ענין וואָס. 

זאל ס נעמען אַ קוק בייַ די פאַקטאָריאַל אָפּעראַציע געניצט רובֿ קאַמאַנלי אין מאַשמאָעס חשבונות. פאַקטאָריאַל פון N איז דער פּראָדוקט פון יעדער בעפיירעש ינטאַדזשער ווייניקער ווי און גלייַך צו N. אַזוי פאַקטאָריאַל פינף איז 5 מאל 4 מאל 3 מאל 2 מאל 1 צו געבן 120. פיר פאַקטאָריאַל איז 4 מאל 3 מאל 2 מאל 1 צו געבן 24. און די זעלבע הערשן אַפּלייז צו קיין positive ינטאַדזשער. 

אַזוי ווי זאל מיר שרייַבן אַ רעקורסיווע פונקציאָנירן אַז קאַלקיאַלייץ די פאַקטאָריאַל פון אַ נומער? גוט, מיר וועט דאַרפֿן צו ידענטיפיצירן ביידע די באַזע פאַל און די רעקורסיווע רופן. די רעקורסיווע רופן וועט זיין דער זעלביקער פֿאַר אַלע קאַסעס אַחוץ פֿאַר די באַזע פאַל, וואָס מיטל אַז מיר וועט האָבן צו געפינען אַ מוסטער וואָס וועט געבן אונדז אונדזער געוואלט רעזולטאַט. 

פֿאַר דעם בייַשפּיל, זען ווי 5 פאַקטאָריאַל ינוואַלווז מאַלטאַפּלייינג 4 דורך 3 דורך 2 דורך 1 און אַז זייער זעלביקער קייפל איז געפונען דאָ, די דעפֿיניציע פון ​​4 פאַקטאָריאַל. אַזוי מיר זען אַז 5 פאַקטאָריאַל איז נאָר 5 מאל 4 פאַקטאָריאַל. איצט טוט דעם מוסטער צולייגן צו 4 פאַקטאָריאַל ווי געזונט? יאָ. מיר זען אַז 4 פאַקטאָריאַל כּולל די קייפל 3 מאל 2 מאל 1, די זייער זעלביקער דעפֿיניציע ווי 3 פאַקטאָריאַל. אַזוי 4 פאַקטאָריאַל איז גלייַך צו 4 מאל 3 פאַקטאָריאַל, און אַזוי אויף און אַזוי אַרויס אונדזער מוסטער סטיקס ביז 1 פאַקטאָריאַל, וואָס דורך דעפֿיניציע איז גלייַך צו 1. 

עס ס קיין אנדערע positive ינטאַדזשערז לינקס. אַזוי מיר האָבן די מוסטער פֿאַר אונדזער רעקורסיווע רופן. 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 און קערט די סאַכאַקל פון אַלע קאָנסעקוטיווע positive ינטאַדזשערז פון N צו 1. איך 'ווע געשריבן אויס די סאַמז פון עטלעכע וואַלועס צו העלפן איר אונדזער. ערשטער, רעכענען אויס די באַזע פאַל צושטאַנד. דעמאָלט, קוק אין סאַכאַקל (5). קענען איר אויסדריקן עס אין טערמינען פון אן אנדער סאַכאַקל? איצט, וואָס וועגן סאַכאַקל (4)? ווי קענען איר אויסדריקן סאַכאַקל (4) אין טערמינען פון אן אנדער סאַכאַקל? 

אַמאָל איר האָבן סאַכאַקל (5) און סאַכאַקל (4) אויסגעדריקט אין טערמינען פון אנדערע סאַמז, זען אויב איר קענען ידענטיפיצירן אַ מוסטער פֿאַר סאַכאַקל (N). אויב ניט, פּרובירן אַ ביסל אנדערע נומערן און אויסדריקן זייער סאַמז אין טערמינען פון אנדערן נומערן. דורך יידענטאַפייינג פּאַטערנז פֿאַר דיסקרעטע נומערן, איר ניטאָ געזונט אויף דיין וועג צו יידענטאַפייינג דעם מוסטער פֿאַר קיין N. 

רעקורסיאָן ס אַ טאַקע שטאַרק געצייַג, אַזוי פון קורס עס ס ניט באגרענעצט צו מאַטאַמאַטיקאַל פאַנגקשאַנז. רעקורסיאָן קענען ווערן געניצט זייער יפעקטיוולי ווען דילינג מיט ביימער פֿאַר בייַשפּיל. טשעק אויס די קורץ אויף ביימער פֿאַר אַ מער גרונטיק באריכטן, אָבער פֿאַר איצט צוריקרופן אַז ביינערי זוכן ביימער, אין באַזונדער, זענען געמאכט אַרויף פון נאָודז, יעדער מיט אַ ווערט און צוויי נאָדע פּוינטערז. וסואַללי, דעם איז רעפּריזענטיד דורך די פאָטער נאָדע בעת איין שורה פּוינטינג צו די לינק קינד נאָדע און איינער צו די רעכט קינד נאָדע. די ביניען פון אַ ביינערי זוכן בוים לענדס זיך געזונט צו אַ רעקורסיווע זוכן. די רעקורסיווע רופן אָדער פּאַסיז אין די לינקס אָדער די רעכט נאָדע, אָבער מער פון אַז אין די בוים קורץ. 

זאָגן איר ווילן צו דורכפירן אַן אָפּעראַציע אויף יעדער איין נאָדע אין אַ ביינערי בוים. ווי זאל איר גיין וועגן אַז? נו, איר געקענט שרייַבן אַ רעקורסיווע פונקציאָנירן אַז פּערפאָרמז די אָפּעראַציע אויף די פאָטער נאָדע און מאכט אַ רעקורסיווע רופן צו דער זעלביקער פֿונקציע, גייט פארביי אין די לינק און רעכט קינד נאָודז. פֿאַר בייַשפּיל, דעם פֿונקציע, פו, אַז ענדערונגען די ווערט פון אַ געגעבן נאָדע און אַלע פון ​​זייַן קינדער צו 1. די באַזע פאַל פון אַ נאַל נאָדע ז די פֿונקציע צו צוריקקומען, ינדאַקייטינג אַז עס זענען ניט קיין נאָודז לינקס אין אַז סאַב-בוים. 

זאל ס גיין דורך עס. דער ערשטער פאָטער איז 13. מיר טוישן די ווערט צו 1, און דעמאָלט רופן אונדזער פונקציאָנירן אויף די לינק ווי געזונט ווי די רעכט. די פֿונקציע, פו, איז גערופן אויף די לינק סאַב-בוים ערשטער, אַזוי די לינק נאָדע וועט זיין ריאַסיינד צו 1 און פו וועט ווערן גערופן אויף אַז נאָדע ס קינדער, ערשטער די לינק און דעמאָלט די רעכט, און אַזוי אויף און אַזוי אַרויס. און דערציילן זיי אַז צווייגן טאָן ניט האָבן קיין מער קינדער אַזוי דער זעלביקער פּראָצעס וועט פאָרזעצן פֿאַר די רעכט קינדער ביז די גאנצע בוים ס נאָודז זענען ריאַסיינד צו 1. 

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

רעקורסיאָן איז זייער שטאַרק און ניט צו דערמאָנען עלעגאַנט, אָבער עס קענען זיין אַ שווער באַגריף בייַ ערשטער, אַזוי זיין פּאַציענט און נעמען אייער צייַט. אָנהייבן מיט די באַזע פאַל. עס ס יוזשאַוואַלי די יזיאַסט צו ידענטיפיצירן, און דעמאָלט איר קענען אַרבעט קאַפּויער פון עס. איר וויסן איר דאַרפֿן צו דערגרייכן דיין באַזע פאַל, אַזוי אַז זאל געבן איר אַ ביסל הינץ. פּרובירן צו אויסדריקן איינער ספּעציפיש פאַל אין תּנאָים פון אנדערע קאַסעס, אָדער אין סאַב-שטעלט. 

דאַנק פֿאַר וואַטשינג דעם קורץ. בייַ די זייער קלענסטער, איצט איר קענען פֿאַרשטיין דזשאָוקס ווי דעם. מיין נאָמען איז זאַמילאַ, און דעם איז קס50. 

נעמען דעם פֿונקציע, הי, אַ פּאָסל פונקציאָנירן אַז נעמט אַ ינט, ן, ווי אַרייַנשרייַב. די באַזע פאַל קומט ערשטער. אויב N איז ווייניקער ווי 0, דרוקן "ביי" און קריק.