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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Kapag kayo ay nakakita
ang video sa recursion,

3
00:00:07,670 --> 00:00:10,170
maaaring mayroon ang buong proseso
tila isang maliit na bit nakapagtataka.

4
00:00:10,170 --> 00:00:10,930
Paano ito gumagana?

5
00:00:10,930 --> 00:00:15,010
Paano ko malalaman kung ang mga function na ang mga ito
kailangang maghintay at maghintay para sa isa pang halaga

6
00:00:15,010 --> 00:00:19,150
upang bumalik mula sa isang iba't ibang mga pag-andar
tumawag upang makuha ang mga resulta na gusto natin?

7
00:00:19,150 --> 00:00:22,550
>> Well, ang dahilan na ito ay gumagawa ay dahil
ng isang bagay na kilala bilang ang stack ng tawag.

8
00:00:22,550 --> 00:00:26,360
Kapag tumawag ka ng isang function, ang
nagtatakda ng sistema tabi espasyo sa memory

9
00:00:26,360 --> 00:00:28,120
para sa na function na gawin ang trabaho nito.

10
00:00:28,120 --> 00:00:31,720
At ang tawag namin sa mga tipak ng memorya na
ay ina-magtabi para sa bawat pag-andar

11
00:00:31,720 --> 00:00:35,670
tumawag sa isang stack frame o isang function frame.

12
00:00:35,670 --> 00:00:38,290
At bilang maaari mong asahan,
mga frames stack

13
00:00:38,290 --> 00:00:41,000
nakatira sa stack bahagi ng memorya.

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

15
00:00:43,960 --> 00:00:47,540
>> Higit sa isang function na stack frame
maaaring umiiral sa memory sa isang ibinigay na oras.

16
00:00:47,540 --> 00:00:51,240
Kung pangunahing tawag ng isang function ilipat,
at ilipat tawag direksyon,

17
00:00:51,240 --> 00:00:54,460
lahat ng tatlong mga pag-andar na may bukas na mga frame.

18
00:00:54,460 --> 00:00:57,350
Ngunit hindi lahat sila ay may aktibong frames.

19
00:00:57,350 --> 00:00:59,410
Ang mga frame ay nakaayos sa isang stack.

20
00:00:59,410 --> 00:01:01,820
At ang mga frame mula sa
pinakahuling tinawagan

21
00:01:01,820 --> 00:01:04,390
function na ay palaging sa tuktok ng stack.

22
00:01:04,390 --> 00:01:07,150
At iyon ay palaging ang aktibong frame.

23
00:01:07,150 --> 00:01:10,420
Mayroon lamang talagang kailanman isa
function na ay aktibo sa isang pagkakataon.

24
00:01:10,420 --> 00:01:12,420
Ito ang isa sa itaas ng stack.

25
00:01:12,420 --> 00:01:17,620
>> Kapag ang isang function ng mga tawag sa isa pang
function, ito uri ng mga pagpindot pause.

26
00:01:17,620 --> 00:01:20,590
Ito ang uri ng ay naka-hold, naghihintay.

27
00:01:20,590 --> 00:01:24,050
At isa pang stack frame ay itinutulak
papunta sa stack sa tuktok ng mga ito.

28
00:01:24,050 --> 00:01:26,150
At iyon ay magiging mga aktibong frame.

29
00:01:26,150 --> 00:01:28,600
At ang mga frame agad
sa ibaba na kinakailangan nito upang maghintay

30
00:01:28,600 --> 00:01:33,560
hanggang sa ito ay muli ang mga aktibong frame
bago ito ay maaaring ipagpatuloy ang kanyang trabaho.

31
00:01:33,560 --> 00:01:35,870
Kapag ang isang function ay
kumpleto at tapos na ito,

32
00:01:35,870 --> 00:01:37,720
frame nito ay pop-off ang stack.

33
00:01:37,720 --> 00:01:38,950
Iyan ay ang terminolohiya.

34
00:01:38,950 --> 00:01:41,110
At ang mga frame agad
sa ibaba nito, tulad ng sinabi ko lang,

35
00:01:41,110 --> 00:01:42,880
nagiging bagong mga aktibong frame.

36
00:01:42,880 --> 00:01:45,960
>> At kung ito tawag ng isa pang function,
ito ay pagpunta sa i-pause muli.

37
00:01:45,960 --> 00:01:49,290
Ay stack frame na bagong pag-andar ng
hunhon papunta sa tuktok ng stack.

38
00:01:49,290 --> 00:01:50,650
Makikita ito gawin ang trabaho nito.

39
00:01:50,650 --> 00:01:52,100
Maaaring pop-back off.

40
00:01:52,100 --> 00:01:55,630
At ang iba pang mga function
ibaba maaari itong ipagpatuloy muli.

41
00:01:55,630 --> 00:02:00,080
>> Kaya sabihin pumunta sa pamamagitan na ito muli, naghahanap
sa ideya ng factorial na function

42
00:02:00,080 --> 00:02:03,070
na natukoy namin sa
recursion video upang makita

43
00:02:03,070 --> 00:02:07,770
eksakto kung paano ang mga magic sa likod na ito
recursive proseso ay nagaganap.

44
00:02:07,770 --> 00:02:09,870
Kaya ito ay ang aming buong file, i-right?

45
00:02:09,870 --> 00:02:14,000
Aming natukoy dalawang
functions-- pangunahing at katotohanan.

46
00:02:14,000 --> 00:02:15,980
At bilang maaari naming asahan,
anumang programa C ay pagpunta

47
00:02:15,980 --> 00:02:18,470
upang simulan sa unang linya ng main.

48
00:02:18,470 --> 00:02:21,660
>> Kaya gumawa kami ng isang bagong stack frame para sa main.

49
00:02:21,660 --> 00:02:23,320
At ito ay pagpunta upang magsimulang tumakbo.

50
00:02:23,320 --> 00:02:25,270
Main tawag printf.

51
00:02:25,270 --> 00:02:29,390
At printf ay pagpunta sa
i-print ang factorial 5.

52
00:02:29,390 --> 00:02:31,440
Well, ito ay hindi alam
kung ano ang factorial ng 5 ay,

53
00:02:31,440 --> 00:02:35,620
at iba ang tawag na ito ay ginagamit na
depende sa isa pang pag-andar ng tawag.

54
00:02:35,620 --> 00:02:37,270
Kaya pangunahing ay pagpunta sa i-pause ang may karapatan.

55
00:02:37,270 --> 00:02:39,103
Ako gonna iwanan nito
palaso doon, kulay

56
00:02:39,103 --> 00:02:41,360
ito ang parehong kulay bilang ang
stack frame sa kanan,

57
00:02:41,360 --> 00:02:47,720
upang ipahiwatig na pangunahing ay pagpunta upang i-freeze
dito habang factorial 5 ay tinatawag na.

58
00:02:47,720 --> 00:02:49,300
>> Kaya factorial 5 ay tinatawag na.

59
00:02:49,300 --> 00:02:53,160
At ito ay pagpunta sa simulan sa pinakadulo
simula ng factorial function.

60
00:02:53,160 --> 00:02:55,440
Ito nagtatanong ang tanong ay kasing-halaga ko sa 1?

61
00:02:55,440 --> 00:02:56,810
Ay 5 katumbas ng 1?

62
00:02:56,810 --> 00:02:57,410
Hindi.

63
00:02:57,410 --> 00:03:01,110
Kaya ito ay pagpunta upang lumusong sa
ang ibang tao ng bahagi, return n ulit

64
00:03:01,110 --> 00:03:02,990
factorial ng n minus 1.

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

66
00:03:03,490 --> 00:03:07,070
>> Kaya ngayon, factorial ng 5 ay
depende sa isa pang tawag

67
00:03:07,070 --> 00:03:09,740
sa factorial, pagpasa
sa 4 na bilang ng mga parameter.

68
00:03:09,740 --> 00:03:14,210
At upang ang mga factorial ng
5 frame, na red frame,

69
00:03:14,210 --> 00:03:17,160
ay pagpunta sa i-freeze ang may karapatan
sa na linya Isinaad ko

70
00:03:17,160 --> 00:03:21,914
at hintayin ang factorial ng 4 upang matapos
kung ano ang kinakailangan nito upang gawin ito na pagkatapos na ito

71
00:03:21,914 --> 00:03:23,330
ay maaaring maging muli ang mga aktibong frame.

72
00:03:23,330 --> 00:03:26,890
>> Kaya factorial ng 4 ay nagsisimula sa
simula ng factorial.

73
00:03:26,890 --> 00:03:28,556
Ay 4 na katumbas ng 1?

74
00:03:28,556 --> 00:03:30,180
Hindi, kaya ito ay pagpunta sa gawin ang parehong bagay.

75
00:03:30,180 --> 00:03:31,590
Ito ay pagpunta sa pumunta down ang ibang tao na branch.

76
00:03:31,590 --> 00:03:33,240
Ito ay pagpunta upang makakuha ng sa na linya ng code.

77
00:03:33,240 --> 00:03:35,710
OK, ako pagpunta upang bumalik sa apat na beses.

78
00:03:35,710 --> 00:03:41,270
Oh, factorial ng 3-- kaya factorial ng
4 ay depende sa factorial ng 3 pagtatapos.

79
00:03:41,270 --> 00:03:43,055
>> At kaya kailangan nito upang tumawag factorial ng 3.

80
00:03:43,055 --> 00:03:45,180
At na gonna pumunta sa pamamagitan ng
muli ang parehong proseso.

81
00:03:45,180 --> 00:03:48,200
Nagsisimula ito sa pamamagitan, ay makakakuha dito.

82
00:03:48,200 --> 00:03:50,980
Factorial ng 3 depende
on factorial ng 1.

83
00:03:50,980 --> 00:03:53,750
Kaya factorial ng 2 nagsisimula, nakakakuha dito.

84
00:03:53,750 --> 00:03:56,310
Ito ay depende sa factorial ng 1.

85
00:03:56,310 --> 00:03:57,430
Factorial ng 1 magsisimula.

86
00:03:57,430 --> 00:03:57,650
>> SIGE.

87
00:03:57,650 --> 00:03:59,775
Kaya ngayon, kami ay pagkuha
sa tabi-tabi na interesante, di ba?

88
00:03:59,775 --> 00:04:02,190
Kaya ngayon, 1 ay katumbas ng 1.

89
00:04:02,190 --> 00:04:05,130
At kaya bumalik kami 1.

90
00:04:05,130 --> 00:04:06,770
Sa puntong ito, kami ay bumabalik.

91
00:04:06,770 --> 00:04:07,880
Ang function na ay tapos na.

92
00:04:07,880 --> 00:04:11,140
Ito ay ang pag-uugali is-- mayroong
wala nang iba pa para sa mga ito upang gawin,

93
00:04:11,140 --> 00:04:17,006
at sa gayon ang stack frame para sa
factorial ng 1 nagpa-pop off.

94
00:04:17,006 --> 00:04:17,589
Ito ay tapos na.

95
00:04:17,589 --> 00:04:19,480
Ibinalik It 1.

96
00:04:19,480 --> 00:04:23,370
At ngayon, factorial ng 2, kung saan
ay agad-agad ang mga frame sa ibaba nito

97
00:04:23,370 --> 00:04:26,160
sa stack, nagiging aktibo frame.

98
00:04:26,160 --> 00:04:29,030
>> At ito ay maaaring kunin
nang eksakto kung saan ito huminto.

99
00:04:29,030 --> 00:04:32,240
Ito ay nai-naghihintay para sa isang factorial
ng 1 upang tapusin ang trabaho nito.

100
00:04:32,240 --> 00:04:33,610
Ito ay tapos na ngayon.

101
00:04:33,610 --> 00:04:35,510
At kaya dito tayo.

102
00:04:35,510 --> 00:04:38,080
>> Factorial ng 1 ibabalik ang halaga ng 1.

103
00:04:38,080 --> 00:04:42,430
Kaya factorial ng 2 lata
sabihin nating ibalik 2 beses 1.

104
00:04:42,430 --> 00:04:43,680
Ang trabaho ay tapos na ngayon.

105
00:04:43,680 --> 00:04:49,110
Ito ay bumalik sa 2 hanggang factorial
ng 3, na kung saan ay naghihintay para sa mga ito.

106
00:04:49,110 --> 00:04:53,370
Factorial ng 3 ay ang frame tuktok ngayon,
ang aktibong frame sa stack.

107
00:04:53,370 --> 00:04:58,617
At kaya ang sinasabi nito, OK, well, ako pagpunta
upang bumalik sa 3 beses sa 2, na kung saan ay 6.

108
00:04:58,617 --> 00:05:00,700
At ako pagpunta upang bigyan na
Pinahahalagahan pabalik sa factorial

109
00:05:00,700 --> 00:05:03,430
ng 4, na kung saan ay naghihintay para sa akin.

110
00:05:03,430 --> 00:05:04,500
Tapos na ako.

111
00:05:04,500 --> 00:05:09,410
Factorial ng 3 nagpa-pop-off ang stack, at
factorial ng 4 ay ang aktibong frame ngayon.

112
00:05:09,410 --> 00:05:13,510
>> 4 sabi, OK, ako pagpunta upang bumalik sa 4 na beses
ang factorial ng 3, na kung saan ay anim na.

113
00:05:13,510 --> 00:05:15,980
Iyon ay may halaga na
factorial ng 3 ibabalik.

114
00:05:15,980 --> 00:05:19,010
At kaya 4 na beses 6 ay 24.

115
00:05:19,010 --> 00:05:20,990
At ako pagpunta sa pumasa
na bumalik sa factorial

116
00:05:20,990 --> 00:05:23,160
5, na kung saan ay naghihintay para sa akin.

117
00:05:23,160 --> 00:05:25,270
Factorial 5 ay ang aktibong frame ngayon.

118
00:05:25,270 --> 00:05:30,700
Ito ay pagpunta upang bumalik 5 beses
factorial ng 4-- 5 beses 24, o 120--

119
00:05:30,700 --> 00:05:32,722
at bigyan ng halaga na
bumalik sa pangunahing, na may

120
00:05:32,722 --> 00:05:35,680
naghihintay napaka matiyagang para sa isang
mahabang panahon sa ilalim ng stack.

121
00:05:35,680 --> 00:05:36,640
>> Ito ay kung saan ito nagsimula.

122
00:05:36,640 --> 00:05:37,670
Ito ay ginawa ang tawag na ito.

123
00:05:37,670 --> 00:05:39,400
Ilang frames kinuha higit sa itaas.

124
00:05:39,400 --> 00:05:41,890
Ito ngayon ay bumalik sa tuktok ng stack.

125
00:05:41,890 --> 00:05:43,450
Ito ay ang aktibong frame.

126
00:05:43,450 --> 00:05:47,810
Kaya pangunahing nakuha ang halaga ng 120
pabalik mula factorial 5.

127
00:05:47,810 --> 00:05:50,750
Ito ay nai-naghihintay na
i-print out ang halaga.

128
00:05:50,750 --> 00:05:51,657
At pagkatapos ay tapos na ito.

129
00:05:51,657 --> 00:05:53,240
Walang higit pang mga linya ng code sa main.

130
00:05:53,240 --> 00:05:56,800
Kaya nagpa-pop frame main ni off
stack, at tapos na kami.

131
00:05:56,800 --> 00:05:58,992
>> At na kung paano gumagana recursion.

132
00:05:58,992 --> 00:06:00,200
Iyon ay kung paano gumagana stack frame.

133
00:06:00,200 --> 00:06:03,120
Ang mga tawag sa function na
na nangyari dati

134
00:06:03,120 --> 00:06:06,620
ay lamang sa i-pause, naghihintay
para sa kasunod na mga tawag

135
00:06:06,620 --> 00:06:12,050
upang matapos upang sila ay maaaring maging ang mga aktibong
frame at tapusin ang kung ano ang kailangan nilang gawin.

136
00:06:12,050 --> 00:06:13,060
>> Ako Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
Ito ay CS50.

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