1
00:00:00,000 --> 00:00:07,800

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Για να κατανοήσουμε
αναδρομή, θα πρέπει να

3
00:00:10,190 --> 00:00:13,820
πρώτα να κατανοήσουμε αναδρομή.

4
00:00:13,820 --> 00:00:17,280
Έχοντας αναδρομή στο πρόγραμμα design μέσα
ότι έχετε αυτοαναφορική

5
00:00:17,280 --> 00:00:18,570
ορισμούς.

6
00:00:18,570 --> 00:00:21,520
Αναδρομικές δομές δεδομένων, για παράδειγμα,
είναι δομές δεδομένων που

7
00:00:21,520 --> 00:00:23,990
περιλαμβάνουν τον εαυτό τους σε
τους ορισμούς τους.

8
00:00:23,990 --> 00:00:27,160
Αλλά σήμερα, θα πάμε να επικεντρωθεί
σχετικά με αναδρομικές συναρτήσεις.

9
00:00:27,160 --> 00:00:31,160
>> Υπενθυμίζουμε ότι οι λειτουργίες λαμβάνουν εισροές,
επιχειρήματα, και να επιστρέψει μια τιμή, όπως τους

10
00:00:31,160 --> 00:00:34,480
εξόδου που αντιπροσωπεύεται από
το διάγραμμα αυτό εδώ.

11
00:00:34,480 --> 00:00:38,060
Θα σκεφτούμε το κουτί όπως το σώμα του
η συνάρτηση, που περιέχει το σύνολο των

12
00:00:38,060 --> 00:00:42,340
οδηγίες που ερμηνεύουν το
εισόδου και παρέχουν μία έξοδο.

13
00:00:42,340 --> 00:00:45,660
Ρίχνοντας μια πιο προσεκτική ματιά στο εσωτερικό του σώματος της
η λειτουργία θα μπορούσε να αποκαλύψει τις κλήσεις προς

14
00:00:45,660 --> 00:00:47,430
άλλες λειτουργίες, καθώς και.

15
00:00:47,430 --> 00:00:51,300
Πάρτε αυτήν την απλή λειτουργία, foo, ότι
παίρνει μια χορδή ως είσοδο και

16
00:00:51,300 --> 00:00:54,630
εκτυπώσεις πόσα γράμματα
ότι η σειρά έχει.

17
00:00:54,630 --> 00:00:58,490
Η strlen λειτουργία, για το μήκος των χορδών,
λέγεται, η παραγωγή των οποίων είναι

18
00:00:58,490 --> 00:01:01,890
που απαιτούνται για την κλήση στην printf.

19
00:01:01,890 --> 00:01:05,770
>> Τώρα, αυτό που κάνει μια αναδρομική συνάρτηση
ξεχωριστό είναι ότι καλεί τον εαυτό της.

20
00:01:05,770 --> 00:01:09,610
Μπορούμε να αναπαραστήσουμε αυτό το αναδρομικό
καλέστε με αυτό το πορτοκαλί βέλος

21
00:01:09,610 --> 00:01:11,360
looping πίσω στον ίδιο.

22
00:01:11,360 --> 00:01:15,630
Αλλά η ίδια την εκτέλεση και πάλι θα είναι μόνο
κάνει μια άλλη αναδρομική κλήση, και

23
00:01:15,630 --> 00:01:17,150
άλλο και άλλο.

24
00:01:17,150 --> 00:01:19,100
Αλλά αναδρομικές συναρτήσεις
δεν μπορεί να είναι άπειρη.

25
00:01:19,100 --> 00:01:23,490
Θα πρέπει να καταλήγουν με κάποιο τρόπο, ή σας
πρόγραμμα θα τρέχει για πάντα.

26
00:01:23,490 --> 00:01:27,680
>> Γι 'αυτό πρέπει να βρούμε έναν τρόπο να σπάσει
από τις αναδρομικές κλήσεις.

27
00:01:27,680 --> 00:01:29,900
Καλούμε αυτό το βασικό σενάριο.

28
00:01:29,900 --> 00:01:33,570
Όταν πληρούται η προϋπόθεση βασική περίπτωση,
η συνάρτηση επιστρέφει χωρίς να

29
00:01:33,570 --> 00:01:34,950
μια άλλη αναδρομική κλήση.

30
00:01:34,950 --> 00:01:39,610
Πάρτε αυτή τη λειτουργία, γεια, μια συνάρτηση void
που παίρνει έναν int n ως είσοδο.

31
00:01:39,610 --> 00:01:41,260
Η βασική περίπτωση έρχεται πρώτη.

32
00:01:41,260 --> 00:01:46,220
Εάν n είναι μικρότερη του μηδενός, αντίο εκτύπωσης και
Για να επιστρέψει όλες τις άλλες περιπτώσεις, η

33
00:01:46,220 --> 00:01:49,400
λειτουργία θα εκτυπώσει ένα γεια και να εκτελέσει
η αναδρομική κλήση.

34
00:01:49,400 --> 00:01:53,600
Μια άλλη κλήση στην hi συνάρτηση με
α μειώνεται τιμή εισόδου.

35
00:01:53,600 --> 00:01:56,790
>> Τώρα, ακόμα κι αν εκτυπώσετε γεια, η
λειτουργία δεν θα τερματίσει μέχρι να

36
00:01:56,790 --> 00:02:00,370
επιστρέψει τύπος επιστροφής της,
στην περίπτωση αυτή άκυρη.

37
00:02:00,370 --> 00:02:04,830
Έτσι, για κάθε n, εκτός από τη βασική περίπτωση,
αυτό το hi συνάρτηση θα επιστρέψει hi

38
00:02:04,830 --> 00:02:06,890
κ μείον 1.

39
00:02:06,890 --> 00:02:10,050
Δεδομένου ότι αυτή η λειτουργία είναι άκυρη όμως,
Δεν θα πληκτρολογήσετε ρητά την επιστροφή εδώ.

40
00:02:10,050 --> 00:02:12,000
Θα εκτελέσει μόνο τη λειτουργία.

41
00:02:12,000 --> 00:02:16,960
Έτσι, καλώντας hi (3), θα εκτυπώσει και hi
εκτελέσει hi (2), η οποία εκτελεί hi (1) μία

42
00:02:16,960 --> 00:02:20,560
το οποίο εκτελεί hi (0), όπου η
κατάσταση βασική υπόθεση ικανοποιείται.

43
00:02:20,560 --> 00:02:24,100
Έτσι hi (0) τυπώνει αντίο και επιστρέφει.

44
00:02:24,100 --> 00:02:24,990
>> OK.

45
00:02:24,990 --> 00:02:28,690
Έτσι, τώρα που καταλαβαίνουμε τα βασικά του
αναδρομικές συναρτήσεις, που χρειάζονται

46
00:02:28,690 --> 00:02:32,730
τουλάχιστον μία περίπτωση βάσεως, καθώς και ένα
αναδρομική κλήση, ας προχωρήσουμε σε μια

47
00:02:32,730 --> 00:02:34,120
πιο ουσιαστική παράδειγμα.

48
00:02:34,120 --> 00:02:37,830
Κάποιος που δεν είναι μόνο να επιστρέψει
ακυρώσει δεν έχει σημασία τι.

49
00:02:37,830 --> 00:02:41,340
>> Ας ρίξουμε μια ματιά στο παραγοντικό
λειτουργίας που χρησιμοποιείται πιο συχνά σε

50
00:02:41,340 --> 00:02:43,660
Υπολογισμοί πιθανοτήτων.

51
00:02:43,660 --> 00:02:48,120
Παραγοντικό n είναι το προϊόν της κάθε
θετικός ακέραιος μικρότερος

52
00:02:48,120 --> 00:02:49,400
και ίση με n.

53
00:02:49,400 --> 00:02:56,731
Έτσι παραγοντικό πέντε είναι 5 φορές 4 φορές
3 φορές 2 φορές για να δώσει 1 120.

54
00:02:56,731 --> 00:03:01,400
Τέσσερις παραγοντικό είναι 4 φορές 3 φορές
2 φορές για να δώσει 1 24.

55
00:03:01,400 --> 00:03:04,910
Και ισχύει ο ίδιος κανόνας
για κάθε θετικό ακέραιο.

56
00:03:04,910 --> 00:03:08,670
>> Λοιπόν, πώς θα μπορούσε να γράφουμε μια αναδρομική
συνάρτηση που υπολογίζει το παραγοντικό

57
00:03:08,670 --> 00:03:09,960
ενός αριθμού;

58
00:03:09,960 --> 00:03:14,700
Λοιπόν, θα πρέπει να προσδιορίσει τόσο το
βασική περίπτωση και η αναδρομική κλήση.

59
00:03:14,700 --> 00:03:18,250
Η αναδρομική κλήση θα είναι η ίδια
για όλες τις περιπτώσεις, εκτός από τη βάση

60
00:03:18,250 --> 00:03:21,420
περίπτωση, πράγμα που σημαίνει ότι θα πρέπει να
βρείτε ένα σχέδιο που θα μας δώσει μας

61
00:03:21,420 --> 00:03:23,350
επιθυμητό αποτέλεσμα.

62
00:03:23,350 --> 00:03:30,270
>> Για αυτό το παράδειγμα, δείτε πώς 5 παραγοντικό
περιλαμβάνει τον πολλαπλασιασμό 4 από 3 με 2 από 1

63
00:03:30,270 --> 00:03:33,010
Και η ίδια αυτή πολλαπλασιασμό
βρίσκεται εδώ, η

64
00:03:33,010 --> 00:03:35,430
ορισμό του παραγοντικού 4.

65
00:03:35,430 --> 00:03:39,810
Έτσι βλέπουμε ότι 5 παραγοντικό είναι
μόλις 5 φορές 4 παραγοντικό.

66
00:03:39,810 --> 00:03:43,360
Τώρα δεν ισχύει αυτό το μοτίβο
4 παραγοντικό, καθώς;

67
00:03:43,360 --> 00:03:44,280
Ναι.

68
00:03:44,280 --> 00:03:49,120
Βλέπουμε ότι 4 παραγοντικό περιέχει το
πολλαπλασιασμός 3 φορές 2 φορές 1, ο

69
00:03:49,120 --> 00:03:51,590
ίδια ορισμός ως 3 παραγοντικό.

70
00:03:51,590 --> 00:03:56,950
Έτσι, 4 παραγοντικό είναι ίση με 4 φορές 3
παραγοντικό, και ούτω καθεξής και ούτω καθεξής μας

71
00:03:56,950 --> 00:04:02,170
πρότυπο μπαστούνια μέχρι 1 παραγοντικό, η οποία
εξ ορισμού είναι ίσο με 1.

72
00:04:02,170 --> 00:04:04,950
>> Δεν υπάρχει καμία άλλη θετική
ακέραιοι αριστερά.

73
00:04:04,950 --> 00:04:07,870
Έτσι, έχουμε το σχέδιο για
αναδρομική κλήση μας.

74
00:04:07,870 --> 00:04:13,260
n παραγοντικό είναι ίσο με n φορές
το παραγοντικό του n μείον 1.

75
00:04:13,260 --> 00:04:14,370
Και τη βασική μας υπόθεση;

76
00:04:14,370 --> 00:04:17,370
Αυτό θα πρέπει ακριβώς να τον ορισμό μας
1 παραγοντικό.

77
00:04:17,370 --> 00:04:19,995
>> Έτσι, τώρα μπορούμε να προχωρήσουμε στο γράψιμο
κώδικα για τη συνάρτηση.

78
00:04:19,995 --> 00:04:24,110
Για το βασικό σενάριο, θα έχουμε την
κατάσταση n ισούται με ίσους 1, όπου

79
00:04:24,110 --> 00:04:25,780
θα επιστρέψουμε 1.

80
00:04:25,780 --> 00:04:29,280
Στη συνέχεια κινείται πάνω στην αναδρομική κλήση,
θα επιστρέψουμε ν φορές την

81
00:04:29,280 --> 00:04:32,180
παραγοντικό του n μείον 1.

82
00:04:32,180 --> 00:04:33,590
>> Τώρα ας δοκιμάσουν αυτή μας.

83
00:04:33,590 --> 00:04:35,900
Ας προσπαθήσουμε παραγοντικό 4.

84
00:04:35,900 --> 00:04:39,420
Ανά λειτουργία μας είναι ίση
έως 4 φορές παραγοντικού (3).

85
00:04:39,420 --> 00:04:43,040
Παραγοντικού (3) είναι ίσο με
3 φορές παραγοντικό (2).

86
00:04:43,040 --> 00:04:48,700
Παραγοντικό (2) είναι ίση με 2 φορές
παραγοντικού (1), η οποία επιστρέφει 1.

87
00:04:48,700 --> 00:04:52,490
Παραγοντικό (2) επιστρέφει τώρα 2 φορές 1, 2.

88
00:04:52,490 --> 00:04:55,960
Παραγοντικού (3) μπορεί τώρα να επιστρέψει
3 φορές 2, 6.

89
00:04:55,960 --> 00:05:02,490
Και τέλος, παραγοντικό (4)
επιστρέφει 4 φορές 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Εάν αντιμετωπίζετε οποιαδήποτε δυσκολία
με την αναδρομική κλήση, να υποκρινόμαστε ότι

91
00:05:06,780 --> 00:05:09,660
η λειτουργία λειτουργεί ήδη.

92
00:05:09,660 --> 00:05:13,450
Τι εννοώ με αυτό είναι ότι θα πρέπει να
εμπιστεύονται αναδρομικές κλήσεις σας για να επιστρέψετε

93
00:05:13,450 --> 00:05:15,100
οι σωστές αξίες.

94
00:05:15,100 --> 00:05:18,960
Για παράδειγμα, αν ξέρω ότι
παραγοντικό (5) ισούται με 5 φορές

95
00:05:18,960 --> 00:05:24,870
παραγοντικό (4), Πάω να εμπιστεύονται ότι
παραγοντικό (4) θα μου δώσει 24.

96
00:05:24,870 --> 00:05:28,510
Σκεφτείτε το σαν μια μεταβλητή, αν
θα προσφέρει, αν έχετε ήδη οριστεί

97
00:05:28,510 --> 00:05:30,070
παραγοντικό (4).

98
00:05:30,070 --> 00:05:33,850
Έτσι, για κάθε παραγοντικό (n), είναι
το προϊόν των η και

99
00:05:33,850 --> 00:05:35,360
το προηγούμενο παραγοντικό.

100
00:05:35,360 --> 00:05:38,130
Και αυτό το προηγούμενο παραγοντικό
λαμβάνεται με την κλήση

101
00:05:38,130 --> 00:05:41,330
παραγοντικό του n μείον 1.

102
00:05:41,330 --> 00:05:45,130
>> Τώρα, δείτε αν μπορείτε να εφαρμόσετε ένα
αναδρομική λειτουργήσει τον εαυτό σας.

103
00:05:45,130 --> 00:05:50,490
Τοποθετήστε το τερματικό σας, ή run.cs50.net,
και να γράψει ένα ποσό λειτουργία

104
00:05:50,490 --> 00:05:54,770
που παίρνει έναν ακέραιο n και επιστρέφει το
άθροισμα όλων των διαδοχικών θετικών

105
00:05:54,770 --> 00:05:57,490
ακέραιοι από 1 έως n.

106
00:05:57,490 --> 00:06:01,000
Έχω γράψει τα ποσά μερικών
τιμές για να σας βοηθήσει μας.

107
00:06:01,000 --> 00:06:04,030
Πρώτον, να καταλάβω το
κατάσταση βασική υπόθεση.

108
00:06:04,030 --> 00:06:06,170
Στη συνέχεια, κοιτάξτε ποσό (5).

109
00:06:06,170 --> 00:06:09,270
Μπορείς να την εκφράσουν με όρους
άλλο ποσό;

110
00:06:09,270 --> 00:06:11,290
Τώρα, τι γίνεται με άθροισμα (4);

111
00:06:11,290 --> 00:06:15,630
Πώς μπορείτε να εκφράζουν άθροισμα (4)
από την άποψη της άλλης ποσό;

112
00:06:15,630 --> 00:06:19,655
>> Μόλις έχετε άθροισμα (5) και το άθροισμα (4)
εκφράζονται σε άλλα ποσά, βλέπε

113
00:06:19,655 --> 00:06:22,970
αν μπορείτε να αναγνωρίσετε ένα
πρότυπο για άθροισμα (n).

114
00:06:22,970 --> 00:06:26,190
Αν όχι, δοκιμάστε μερικά άλλα νούμερα
και να εκφράσουν τα ποσά τους σε

115
00:06:26,190 --> 00:06:28,410
όρους άλλο αριθμό.

116
00:06:28,410 --> 00:06:31,930
Με τον προσδιορισμό πρότυπα για διακριτά
αριθμοί, είστε καλά στο δρόμο σας για να

117
00:06:31,930 --> 00:06:34,320
τον προσδιορισμό του προτύπου για κάθε n.

118
00:06:34,320 --> 00:06:38,040
>> Η αναδρομή είναι ένα πραγματικά ισχυρό εργαλείο,
οπότε φυσικά δεν είναι περιορίζεται σε

119
00:06:38,040 --> 00:06:39,820
μαθηματικές συναρτήσεις.

120
00:06:39,820 --> 00:06:44,040
Αναδρομή μπορεί να χρησιμοποιηθεί πολύ αποτελεσματικά
όταν ασχολείται με τα δέντρα για παράδειγμα.

121
00:06:44,040 --> 00:06:47,210
Ελέγξτε τη σύντομη στα δέντρα για μια
διεξοδικότερη εξέταση, αλλά προς το παρόν

122
00:06:47,210 --> 00:06:51,140
Υπενθυμίζουμε ότι δυαδικά δέντρα αναζήτησης, σε
Ειδικότερα, αποτελούνται από κόμβους, το καθένα

123
00:06:51,140 --> 00:06:53,820
με αξία και δίποντα κόμβο.

124
00:06:53,820 --> 00:06:57,270
Συνήθως, αυτό αντιπροσωπεύεται από την
κόμβο γονέα που έχει μία γραμμή που δείχνει

125
00:06:57,270 --> 00:07:01,870
στο αριστερό θυγατρικό κόμβο και ένα
προς τα δεξιά θυγατρικό κόμβο.

126
00:07:01,870 --> 00:07:04,510
Η δομή ενός δυαδική αναζήτηση
δέντρο αποτελεί πρόσφορο μέσο

127
00:07:04,510 --> 00:07:05,940
σε μια αναδρομική αναζήτηση.

128
00:07:05,940 --> 00:07:09,730
Η αναδρομική κλήση περνά είτε στην
αριστερό ή το δεξί κόμβο, αλλά περισσότερο

129
00:07:09,730 --> 00:07:10,950
του ότι σε σύντομο δέντρου.

130
00:07:10,950 --> 00:07:15,690
>> Ας πούμε ότι θέλετε να εκτελέσετε μια λειτουργία σε
κάθε κόμβου σε ένα δυαδικό δένδρο.

131
00:07:15,690 --> 00:07:17,410
Πώς θα πάτε γι 'αυτό;

132
00:07:17,410 --> 00:07:20,600
Λοιπόν, θα μπορούσατε να γράψετε ένα αναδρομικό
λειτουργία που εκτελεί τη λειτουργία

133
00:07:20,600 --> 00:07:24,450
στον πατρικό κόμβο και κάνει μια αναδρομική
καλέστε την ίδια λειτουργία,

134
00:07:24,450 --> 00:07:27,630
περνώντας στην αριστερή
δεξιά κόμβους παιδί.

135
00:07:27,630 --> 00:07:31,650
Για παράδειγμα, η λειτουργία αυτή, foo, ότι
αλλάζει την τιμή του ένα δεδομένο κόμβο και

136
00:07:31,650 --> 00:07:33,830
όλα τα παιδιά της σε 1.

137
00:07:33,830 --> 00:07:37,400
Η βασική περίπτωση ενός null αιτίες κόμβο
η λειτουργία για να επιστρέψει, δείχνοντας

138
00:07:37,400 --> 00:07:41,290
ότι δεν υπάρχουν κόμβοι
αριστερά σε αυτή την υπο-δέντρο.

139
00:07:41,290 --> 00:07:42,620
>> Ας δούμε μέσα από αυτό.

140
00:07:42,620 --> 00:07:44,340
Ο πρώτος γονέας είναι 13.

141
00:07:44,340 --> 00:07:47,930
Αλλάζουμε την τιμή σε 1, και στη συνέχεια να καλέσετε
λειτουργία μας στα αριστερά, καθώς και

142
00:07:47,930 --> 00:07:49,600
όπως το δικαίωμα.

143
00:07:49,600 --> 00:07:53,910
Η λειτουργία, foo, καλείται με το αριστερό
υπο-δένδρο πρώτα, έτσι ώστε το αριστερό κόμβο

144
00:07:53,910 --> 00:07:57,730
θα μπορούν να τοποθετηθούν σε 1 και foo θα
να κληθούν τα παιδιά αυτού του κόμβου,

145
00:07:57,730 --> 00:08:01,900
Πρώτα η αριστερά και στη συνέχεια το δικαίωμα,
και ούτω καθεξής και ούτω καθεξής.

146
00:08:01,900 --> 00:08:05,630
Και να τους πούμε ότι τα υποκαταστήματα δεν έχουν
πια τα παιδιά έτσι ώστε η ίδια διαδικασία

147
00:08:05,630 --> 00:08:09,700
θα συνεχιστεί για το δικαίωμα των παιδιών
μέχρι να είναι οι κόμβοι του δέντρου ολόκληρη

148
00:08:09,700 --> 00:08:11,430
εκ νέου σε 1.

149
00:08:11,430 --> 00:08:15,390
>> Όπως μπορείτε να δείτε, δεν είστε περιορισμένοι
σε ένα μόνο αναδρομική κλήση.

150
00:08:15,390 --> 00:08:17,930
Ακριβώς όπως πολλοί όπως θα γίνει η δουλειά.

151
00:08:17,930 --> 00:08:21,200
Τι εάν είχατε ένα δέντρο όπου κάθε
κόμβος είχε τρία παιδιά,

152
00:08:21,200 --> 00:08:23,100
Αριστερό, μεσαίο και δεξί;

153
00:08:23,100 --> 00:08:24,886
Πώς θα επεξεργαστείτε foo;

154
00:08:24,886 --> 00:08:25,860
Λοιπόν, απλά.

155
00:08:25,860 --> 00:08:30,250
Απλά προσθέστε μια άλλη αναδρομική κλήση και
περάσει στο δείκτη μεσαίας κόμβο.

156
00:08:30,250 --> 00:08:34,549
>> Η αναδρομή είναι πολύ ισχυρό και να μην
αναφέρουμε κομψό, αλλά μπορεί να είναι ένα

157
00:08:34,549 --> 00:08:38,010
δύσκολη έννοια στην αρχή, έτσι ώστε να είναι
ασθενή και πάρτε το χρόνο σας.

158
00:08:38,010 --> 00:08:39,370
Ξεκινήστε με τη βασική περίπτωση.

159
00:08:39,370 --> 00:08:42,650
Είναι συνήθως το πιο εύκολο να εντοπιστούν,
και, στη συνέχεια, μπορείτε να εργαστείτε

160
00:08:42,650 --> 00:08:43,830
προς τα πίσω από εκεί.

161
00:08:43,830 --> 00:08:46,190
Ξέρετε ότι πρέπει να φτάσει το
βασική περίπτωση, έτσι ώστε θα μπορούσε

162
00:08:46,190 --> 00:08:47,760
να σας δώσω μερικές συμβουλές.

163
00:08:47,760 --> 00:08:53,120
Προσπαθήστε να εκφράσω για μία συγκεκριμένη περίπτωση
αφορά άλλες περιπτώσεις, ή σε υπο-ομάδες.

164
00:08:53,120 --> 00:08:54,700
>> Ευχαριστώ για την προσοχή αυτό το σύντομο.

165
00:08:54,700 --> 00:08:58,920
Τουλάχιστον, τώρα μπορείτε
καταλαβαίνουν ανέκδοτα σαν αυτό.

166
00:08:58,920 --> 00:09:01,250
Το όνομά μου είναι Zamyla, και αυτό είναι CS50.

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> Πάρτε αυτή τη λειτουργία, γεια, μια
void συνάρτηση που παίρνει

169
00:09:07,170 --> 00:09:09,212
int, n, ως εισροές.

170
00:09:09,212 --> 00:09:11,020
Η βασική περίπτωση έρχεται πρώτη.

171
00:09:11,020 --> 00:09:14,240
Εάν το η είναι μικρότερο από 0, εκτύπωση
"Αντίο" και την επιστροφή.

172
00:09:14,240 --> 00:09:15,490