1
00:00:00,000 --> 00:00:05,587

2
00:00:05,587 --> 00:00:07,670
Дъг LLOYD: Ако сте виждали
видеото на рекурсия,

3
00:00:07,670 --> 00:00:10,170
целият процес може да има
Изглеждаше малко вълшебно.

4
00:00:10,170 --> 00:00:10,930
Как работи?

5
00:00:10,930 --> 00:00:15,010
Как функциите знаят, че те
Трябва да изчакаме и да изчакаме още една стойност

6
00:00:15,010 --> 00:00:19,150
да се върне от различна функция
обадя, за да се получи резултата, което искаме?

7
00:00:19,150 --> 00:00:22,550
>> Е, причината е, защото това работи
на нещо, известно като стека повикване.

8
00:00:22,550 --> 00:00:26,360
Когато позвъните на функция,
система заделя място в паметта

9
00:00:26,360 --> 00:00:28,120
за тази функция, за да си върши работата.

10
00:00:28,120 --> 00:00:31,720
И ние наричаме тези части от паметта, която
се заделят за всяка функция

11
00:00:31,720 --> 00:00:35,670
обадете комин рамка или функция конструкция.

12
00:00:35,670 --> 00:00:38,290
И както може да се очаква,
тези стека рамки

13
00:00:38,290 --> 00:00:41,000
живеят на стека част на паметта.

14
00:00:41,000 --> 00:00:43,960

15
00:00:43,960 --> 00:00:47,540
>> Повече от една функция стека конструкция
може да съществува в памет в даден момент.

16
00:00:47,540 --> 00:00:51,240
Ако основната призовава функция ход,
и ход призовава посока,

17
00:00:51,240 --> 00:00:54,460
и трите функции са отворени рамки.

18
00:00:54,460 --> 00:00:57,350
Но те не всичко нужно активни рамки.

19
00:00:57,350 --> 00:00:59,410
Тези рамки са подредени в стека.

20
00:00:59,410 --> 00:01:01,820
И рамката от
най-наскоро призова

21
00:01:01,820 --> 00:01:04,390
функция е винаги на върха на стека.

22
00:01:04,390 --> 00:01:07,150
И това е винаги активното рамката.

23
00:01:07,150 --> 00:01:10,420
Има само един наистина някога
функция, която е активна в даден момент.

24
00:01:10,420 --> 00:01:12,420
Той е този, на върха на стека.

25
00:01:12,420 --> 00:01:17,620
>> Когато дадена функция призовава друг
функция, тя някак преси пауза.

26
00:01:17,620 --> 00:01:20,590
Това нещо е задържана, чака.

27
00:01:20,590 --> 00:01:24,050
И още един стек конструкция е натиснат
върху комина на върха му.

28
00:01:24,050 --> 00:01:26,150
И това става активна рамка.

29
00:01:26,150 --> 00:01:28,600
И рамката веднага
под него трябва да се изчака

30
00:01:28,600 --> 00:01:33,560
докато е отново активното рамката
преди да може да поднови работата си.

31
00:01:33,560 --> 00:01:35,870
Когато е функция
пълна и това е направено,

32
00:01:35,870 --> 00:01:37,720
рамката му е извадена извън стека.

33
00:01:37,720 --> 00:01:38,950
Това е терминологията.

34
00:01:38,950 --> 00:01:41,110
И рамката веднага
под него, както току-що каза,

35
00:01:41,110 --> 00:01:42,880
става новият активната рамка.

36
00:01:42,880 --> 00:01:45,960
>> И ако го нарича друга функция,
то се случва да направите пауза отново.

37
00:01:45,960 --> 00:01:49,290
Стак конструкция Тази нова функция воля
се вкарва на върха на купчината.

38
00:01:49,290 --> 00:01:50,650
Тя ще си върши работата.

39
00:01:50,650 --> 00:01:52,100
Тя може да се появи обратно на разстояние.

40
00:01:52,100 --> 00:01:55,630
И друга функция
под него може да се възобнови отново.

41
00:01:55,630 --> 00:02:00,080
>> Така че нека да мине през това отново, гледайки
до идеята за факторен функция

42
00:02:00,080 --> 00:02:03,070
че определени в
рекурсия видео, за да видите

43
00:02:03,070 --> 00:02:07,770
точно как магията зад това
рекурсивни процес се провежда.

44
00:02:07,770 --> 00:02:09,870
Така че това е цялата ни файл, нали?

45
00:02:09,870 --> 00:02:14,000
Ние определено две
functions-- основна и факт.

46
00:02:14,000 --> 00:02:15,980
И както може да се очаква,
всяко C програма ще

47
00:02:15,980 --> 00:02:18,470
да започва с първата линия на основната.

48
00:02:18,470 --> 00:02:21,660
>> Така че ние се създаде нов комин рамка за основното.

49
00:02:21,660 --> 00:02:23,320
И то се случва да се показват отново.

50
00:02:23,320 --> 00:02:25,270
Основни разговори ФОРМАТ.

51
00:02:25,270 --> 00:02:29,390
И ФОРМАТ ще
разпечатате факториел от 5.

52
00:02:29,390 --> 00:02:31,440
Е, той не знае
което факторен на 5,

53
00:02:31,440 --> 00:02:35,620
и така този разговор вече е
в зависимост от друга функция повикване.

54
00:02:35,620 --> 00:02:37,270
Така че основното ще пауза точно там.

55
00:02:37,270 --> 00:02:39,103
Аз ще остави своя
стрелка точно там, цветен

56
00:02:39,103 --> 00:02:41,360
тя със същия цвят като на
стека конструкция отдясно,

57
00:02:41,360 --> 00:02:47,720
да се посочи, че основното ще замрази
тук, докато факторен на 5 се нарича.

58
00:02:47,720 --> 00:02:49,300
>> Така факторен на 5 се нарича.

59
00:02:49,300 --> 00:02:53,160
И това ще започне в самото
започваща на факторен функция.

60
00:02:53,160 --> 00:02:55,440
Той задава въпроса съм равен на 1?

61
00:02:55,440 --> 00:02:56,810
5 е равно на 1?

62
00:02:56,810 --> 00:02:57,410
Ами не.

63
00:02:57,410 --> 00:03:01,110
Така, че ще ходи да слязат
на друго участие, връщането н времена

64
00:03:01,110 --> 00:03:02,990
факторен на N минус 1.

65
00:03:02,990 --> 00:03:03,490
Е, OK.

66
00:03:03,490 --> 00:03:07,070
>> Така че сега, факториел от 5 е
в зависимост от друг разговор

67
00:03:07,070 --> 00:03:09,740
да факторните, минаваща
в 4 като параметър.

68
00:03:09,740 --> 00:03:14,210
И така на факториела
5 конструкция, която червена рамка,

69
00:03:14,210 --> 00:03:17,160
ще замрази точно там
по тази линия съм посочено

70
00:03:17,160 --> 00:03:21,914
и да чакат за факторен на 4, за да продължи
какво трябва да направи така, че след това го

71
00:03:21,914 --> 00:03:23,330
може да се превърне отново в активната рамка.

72
00:03:23,330 --> 00:03:26,890
>> Така факториела 4 започва в
началото на факториален.

73
00:03:26,890 --> 00:03:28,556
4 е равно на 1?

74
00:03:28,556 --> 00:03:30,180
Не, така че ще направи същото нещо.

75
00:03:30,180 --> 00:03:31,590
Това ще слязат на друг клон.

76
00:03:31,590 --> 00:03:33,240
Това ще стигнем до този ред код.

77
00:03:33,240 --> 00:03:35,710
OK, аз отивам да се върне четири пъти.

78
00:03:35,710 --> 00:03:41,270
О, факторен на 3-- така факториела
4 зависи от факторен на 3 довършителни работи.

79
00:03:41,270 --> 00:03:43,055
>> И така, той трябва да се обадя на факторен 3.

80
00:03:43,055 --> 00:03:45,180
И това ще мине през
същия процес отново.

81
00:03:45,180 --> 00:03:48,200
Тя започва през, дойде тук.

82
00:03:48,200 --> 00:03:50,980
Факториел на 3 зависи
на факториел на 1.

83
00:03:50,980 --> 00:03:53,750
Така факторен на 2 започва, получава тук.

84
00:03:53,750 --> 00:03:56,310
Това зависи от факторен на 1.

85
00:03:56,310 --> 00:03:57,430
Факториел на 1 започва.

86
00:03:57,430 --> 00:03:57,650
>> ДОБРЕ.

87
00:03:57,650 --> 00:03:59,775
Така че сега, ние получаваме
някъде интересно, нали?

88
00:03:59,775 --> 00:04:02,190
Така че сега, едно е равно на 1.

89
00:04:02,190 --> 00:04:05,130
И така, ние се върне 1.

90
00:04:05,130 --> 00:04:06,770
В този момент, ние се връщаме.

91
00:04:06,770 --> 00:04:07,880
Функцията е направено.

92
00:04:07,880 --> 00:04:11,140
Това е поведение is-- има
нищо друго, за да се направи,

93
00:04:11,140 --> 00:04:17,006
и така на стека рамката за
факторен на 1 изскача.

94
00:04:17,006 --> 00:04:17,589
Свършено е.

95
00:04:17,589 --> 00:04:19,480
Той се върна 1.

96
00:04:19,480 --> 00:04:23,370
И сега, факторен на 2, което
е рамката непосредствено под него

97
00:04:23,370 --> 00:04:26,160
в стека, става активна рамка.

98
00:04:26,160 --> 00:04:29,030
>> И това може да вдигне
точно там, където е спряло.

99
00:04:29,030 --> 00:04:32,240
Той е бил в очакване на факториел
1, за да продължи работата си.

100
00:04:32,240 --> 00:04:33,610
Сега е приключил.

101
00:04:33,610 --> 00:04:35,510
И така, ние сме тук.

102
00:04:35,510 --> 00:04:38,080
>> Факториел на 1 завърна на стойност 1.

103
00:04:38,080 --> 00:04:42,430
Така факторен на 2 консерва
да речем върне 2 пъти 1.

104
00:04:42,430 --> 00:04:43,680
Нейната работа е вече свършена.

105
00:04:43,680 --> 00:04:49,110
Той е върнал от 2 до факторните
на 3, която го очакваше.

106
00:04:49,110 --> 00:04:53,370
Факториел на 3 сега е най-горната част на рамката,
активното кадър в стека.

107
00:04:53,370 --> 00:04:58,617
И така се казва, OK, добре, аз ще съм
да се върнат 3 пъти 2, което е 6.

108
00:04:58,617 --> 00:05:00,700
И аз ще дам, че
ценим обратно към факторен

109
00:05:00,700 --> 00:05:03,430
4, който е бил да ме чака.

110
00:05:03,430 --> 00:05:04,500
Приключих.

111
00:05:04,500 --> 00:05:09,410
Факториел на 3 изскача стека, и
факторен на 4 сега е най-активната рамка.

112
00:05:09,410 --> 00:05:13,510
>> 4 казва, OK, аз отивам да се върне 4 пъти
факториела на 3, което е шест.

113
00:05:13,510 --> 00:05:15,980
Това беше на стойност, която
факторен на 3 върнати.

114
00:05:15,980 --> 00:05:19,010
И така 4 пъти 6 е 24.

115
00:05:19,010 --> 00:05:20,990
И аз отивам да мине
че обратно на факторните

116
00:05:20,990 --> 00:05:23,160
5, който е бил да ме чака.

117
00:05:23,160 --> 00:05:25,270
Факториел на 5 вече е активна рамка.

118
00:05:25,270 --> 00:05:30,700
Това ще върне 5 пъти
факторен на блок 4 5 пъти 24 или 120--

119
00:05:30,700 --> 00:05:32,722
и да даде тази стойност
обратно към основното, което има

120
00:05:32,722 --> 00:05:35,680
чакал търпеливо за
дълго време в долната част на купчината.

121
00:05:35,680 --> 00:05:36,640
>> Това е мястото, където е започнало.

122
00:05:36,640 --> 00:05:37,670
Той направи този призив.

123
00:05:37,670 --> 00:05:39,400
Няколко кадъра превзеха в горната част.

124
00:05:39,400 --> 00:05:41,890
Сега е отново на върха на стека.

125
00:05:41,890 --> 00:05:43,450
Това е най-активната рамка.

126
00:05:43,450 --> 00:05:47,810
Така че основната получава стойност от 120
обратно от факториел от 5.

127
00:05:47,810 --> 00:05:50,750
Той е бил в очакване да
разпечатате тази стойност.

128
00:05:50,750 --> 00:05:51,657
И тогава това е направено.

129
00:05:51,657 --> 00:05:53,240
Няма вече реда код в основната.

130
00:05:53,240 --> 00:05:56,800
Така че основната му конструкция изскача
стека, и сме готови.

131
00:05:56,800 --> 00:05:58,992
>> И това е, как работи рекурсия.

132
00:05:58,992 --> 00:06:00,200
Ето как стека рамки работят.

133
00:06:00,200 --> 00:06:03,120
Тези извиквания
, което се случи по-рано

134
00:06:03,120 --> 00:06:06,620
са само за пауза, очаквайки
за следващи покани

135
00:06:06,620 --> 00:06:12,050
да завърши така, те могат да станат активната
рамката и да завърши това, което трябва да направите.

136
00:06:12,050 --> 00:06:13,060
>> Аз съм Дъг Лойд.

137
00:06:13,060 --> 00:06:14,880
Това е CS50.

138
00:06:14,880 --> 00:06:16,580