1
00:00:00,000 --> 00:00:05,860
 [SKAN MŪZIKA]

2
00:00:05,860 --> 00:00:07,695
DAGS LOIDS: Jūs droši vien domājat,
ka kods tiek izmantots tikai 

3
00:00:07,695 --> 00:00:09,530
uzdevuma veikšanai. 

4
00:00:09,530 --> 00:00:10,450
Jūs to izrakstāt.

5
00:00:10,450 --> 00:00:11,664
Tas kaut ko dara.

6
00:00:11,664 --> 00:00:12,580
Tas ir gandrīz viss.

7
00:00:12,580 --> 00:00:13,160
 Jūs to kompilējat.

8
00:00:13,160 --> 00:00:13,993
Jūs palaižat programmu.

9
00:00:13,993 --> 00:00:15,370
Jūs esat gatavi.

10
00:00:15,370 --> 00:00:17,960
Bet ticiet vai ne, ja kodējat ilgu
laiku, jūs praktiski varētu 

11
00:00:17,960 --> 00:00:20,550
uztvert kodu kā kaut ko skaistu. 

12
00:00:20,550 --> 00:00:23,530
Tas atrisina problēmu ļoti
interesantā veidā, vai arī tās izskatā ir 

13
00:00:23,530 --> 00:00:26,510
kaut kas patiešām glīts. 

14
00:00:26,510 --> 00:00:28,750
Jūs varat smieties par mani, bet tā
ir taisnība.

15
00:00:28,750 --> 00:00:31,420
Un rekursija ir viens no veidiem,
kā saprast ideju par skaistu, 

16
00:00:31,420 --> 00:00:34,090
elegantu kodu. 

17
00:00:34,090 --> 00:00:36,950
Tā atrisina problēmas interesantā,
viegli vizualizējamā un 

18
00:00:36,950 --> 00:00:39,810
pārsteidzoši īsā veidā. 

19
00:00:39,810 --> 00:00:44,550
Rekursijas darbības veids ir tāds,
ka rekursīvā funkcija tiek 

20
00:00:44,550 --> 00:00:49,291
definēta kā funkcija, kas sevi
izsauc kā daļu no tās izpildes. 

21
00:00:49,291 --> 00:00:51,520
Tas varētu šķist nedaudz dīvaini,
bet pēc brīža mēs redzēsim, kā tas 

22
00:00:51,520 --> 00:00:53,750
darbojas. 

23
00:00:53,750 --> 00:00:56,736
Bet atkal šīs rekursīvās procedūras
būs tik elegantas, jo tās 

24
00:00:56,736 --> 00:00:59,723
atrisinās šo problēmu, neizmantojot
pārējās funkcijas vai šīs garas 

25
00:00:59,723 --> 00:01:02,710
cilpas. 

26
00:01:02,710 --> 00:01:06,310
Jūs redzēsiet, ka šīs rekursīvās
procedūras izskatīsies tik īsas.

27
00:01:06,310 --> 00:01:10,610
Un tās patiešām padarīs jūsu kodu
daudz skaistāku.

28
00:01:10,610 --> 00:01:12,745
Es parādīšu jums piemēru, lai
redzētu, kā var definēt rekursīvo 

29
00:01:12,745 --> 00:01:14,880
procedūru. 

30
00:01:14,880 --> 00:01:17,495
Tātad, no matemātikas stundām pirms
daudziem gadiem jūs zināt, ka ir 

31
00:01:17,495 --> 00:01:20,110
kaut kas tāds, ko sauc par
faktoriālu funkciju, ko parasti apzīmē kā 

32
00:01:20,110 --> 00:01:22,725
izsaukuma zīmi, kas ir attiecināma
uz visiem pozitīvajiem veseliem 

33
00:01:22,725 --> 00:01:25,340
skaitļiem. 

34
00:01:25,340 --> 00:01:28,520
Un veids, kā tiek aprēķināts n
faktoriāls, ir reizināt kopā visus 

35
00:01:28,520 --> 00:01:31,700
skaitļus, kas ir mazāki vai vienādi
ar n, — visus veselos skaitļus, 

36
00:01:31,700 --> 00:01:34,880
kas ir mazāki vai vienādi ar n. 

37
00:01:34,880 --> 00:01:39,850
 Tātad skaitļa 5 faktoriāls ir 5
reiz 4 reiz 3 reiz 2 reiz 1.

38
00:01:39,850 --> 00:01:43,020
Un skaitļa 4 faktoriāls ir 4 reiz 3
reize2 reiz 1, un tā tālāk.

39
00:01:43,020 --> 00:01:44,800
Jūs saprotat domu.

40
00:01:44,800 --> 00:01:47,060
 Kā programmētāji mēs neizmantojam
n un izsaukuma zīmi.

41
00:01:47,060 --> 00:01:51,840
Tātad faktoriāla funkciju definēsim
kā n faktu.

42
00:01:51,840 --> 00:01:54,368
Un mēs izmantosim faktoriālu, lai
izveidotu problēmas rekursīvu 

43
00:01:54,368 --> 00:01:56,897
risinājumu. 

44
00:01:56,897 --> 00:01:59,601
Un es domāju, ka jūs piekritīsiet,
ka tas ir daudz vizuāli 

45
00:01:59,601 --> 00:02:02,305
pievilcīgāks nekā tā iteratīvā
versija, kuru mēs arī pēc brīža 

46
00:02:02,305 --> 00:02:05,010
apskatīsim. 

47
00:02:05,010 --> 00:02:07,589
Tātad, šeit ir daži fakti — runa ir
par faktoriālu — faktoriālu 

48
00:02:07,589 --> 00:02:10,169
funkciju. 

49
00:02:10,169 --> 00:02:13,090
Skaitļa 1 faktoriāls, kā jau teicu,
ir 1.

50
00:02:13,090 --> 00:02:15,690
Skaitļa 2 faktoriāls ir 2 reiz 1.

51
00:02:15,690 --> 00:02:18,470
Skaitļa 3 faktoriāls ir 3 reiz 2
reiz 1, utt.

52
00:02:18,470 --> 00:02:20,810
Mēs jau runājām par 4 un 5.

53
00:02:20,810 --> 00:02:23,940
 Bet paskatoties uz šo, vai tā nav
taisnība?

54
00:02:23,940 --> 00:02:28,220
Vai skaitļa 2 faktoriāls 2 nav
tikai 2 reiz 1?

55
00:02:28,220 --> 00:02:31,130
 Tas ir, skaitļa 1 faktoriāls ir 1.

56
00:02:31,130 --> 00:02:34,825
Tātad, kāpēc mēs nevaram tā
vienkārši pateikt, jo 2 faktoriāls ir 2 

57
00:02:34,825 --> 00:02:38,520
reiz 1, tas tiešām ir tikai 2
reizes vairāk nekā 1? 

58
00:02:38,520 --> 00:02:41,300
Un tad, paplašinot šo ideju, vai 3
faktoriāls nav tikai 3 reizes 

59
00:02:41,300 --> 00:02:44,080
lielāks nekā skaitļa 2 faktoriāls? 

60
00:02:44,080 --> 00:02:47,215
Un skaitļa 4 faktoriāls ir 4 reizes
lielāks par faktoriālu no 3 un tā 

61
00:02:47,215 --> 00:02:50,350
tālāk? 

62
00:02:50,350 --> 00:02:52,505
Faktiski jebkura skaitļa faktoriālu
var vienkārši izteikt, ja mēs to 

63
00:02:52,505 --> 00:02:54,660
izpildām tā mūžīgi. 

64
00:02:54,660 --> 00:02:57,285
Mēs varam vispārināt faktoriālu
problēmu, jo tā ir n reizes lielāka 

65
00:02:57,285 --> 00:02:59,910
par n faktoriālu mīnus 1. 

66
00:02:59,910 --> 00:03:04,840
Tas ir visu skaitļu, kas ir mazāki
par mani, reizinājums n reizes.

67
00:03:04,840 --> 00:03:09,125
Šī ideja, šis problēmas
vispārinājums, ļauj mums rekursīvi definēt 

68
00:03:09,125 --> 00:03:13,410
faktoriālu funkciju. 

69
00:03:13,410 --> 00:03:17,470
Ja funkciju definējat rekursīvi,
tai ir jābūt divām lietām.

70
00:03:17,470 --> 00:03:19,975
Jums ir nepieciešams kaut kas, ko
sauc par bāzes bloku, kas, 

71
00:03:19,975 --> 00:03:22,480
aktivizējoties, aptur rekursīvo
procesu. 

72
00:03:22,480 --> 00:03:24,675
Pretējā gadījumā funkcija, kas
izsauc sevi — kā jūs varētu iedomāties 

73
00:03:24,675 --> 00:03:26,870
— varētu turpināties mūžīgi. 

74
00:03:26,870 --> 00:03:28,625
Funkcija izsauc funkciju, izsauc
funkciju, izsauc funkciju, izsauc 

75
00:03:28,625 --> 00:03:30,380
funkciju. 

76
00:03:30,380 --> 00:03:32,570
Ja jums nav iespējas to apturēt,
jūsu programma faktiski būs 

77
00:03:32,570 --> 00:03:34,760
iestrēgusi bezgalīgā cilpā. 

78
00:03:34,760 --> 00:03:37,176
Tā galu galā avarēs, jo tai
pietrūks atmiņas.

79
00:03:37,176 --> 00:03:38,990
Bet ne par to ir runa.

80
00:03:38,990 --> 00:03:41,330
Mums ir nepieciešams kāds cits
veids, kā apturēt programmu bez 

81
00:03:41,330 --> 00:03:43,670
avārijas, jo programma, kas avarē,
visticamāk nav skaista un 

82
00:03:43,670 --> 00:03:46,010
eleganta. 

83
00:03:46,010 --> 00:03:47,690
Un tāpēc mēs to saucam par bāzes
bloku.

84
00:03:47,690 --> 00:03:52,770
Šis ir vienkāršs problēmas
risinājums, kas aptur rekursīvo procesu.

85
00:03:52,770 --> 00:03:55,220
Tātad tā ir viena no rekursīvās
funkcijas daļām.

86
00:03:55,220 --> 00:03:56,820
 Otrā daļa ir rekursīvais bloks.

87
00:03:56,820 --> 00:03:59,195
Un šeit faktiski notiks rekursija.

88
00:03:59,195 --> 00:04:02,200
Šeit funkcija izsauks sevi.

89
00:04:02,200 --> 00:04:05,940
 Tā nesauks sevi tieši tādā pašā
veidā, kā to sauca.

90
00:04:05,940 --> 00:04:08,718
Te būs neliela variācija, kas
padara problēmu, ko tā mēģina 

91
00:04:08,718 --> 00:04:11,497
atrisināt, nedaudz mazāku. 

92
00:04:11,497 --> 00:04:14,473
Taču risinājuma atbildības lielākā
daļa parasti tiek pārnesta uz 

93
00:04:14,473 --> 00:04:17,450
nākamo zvanu. 

94
00:04:17,450 --> 00:04:20,290
 Kurš no šiem šeit izskatās kā
bāzes bloks?

95
00:04:20,290 --> 00:04:25,384
Kurš no šiem šķiet vienkāršākais
problēmas risinājums?

96
00:04:25,384 --> 00:04:30,470
Mums ir daudz faktoriālu, un mēs
varētu turpināt — 6, 7, 8, 9, 10 utt.

97
00:04:30,470 --> 00:04:32,300
Bet viens no tiem izskatās kā labs
gadījums, lai to izmantotu kā 

98
00:04:32,300 --> 00:04:34,130
bāzes bloku. 

99
00:04:34,130 --> 00:04:35,310
Tas ir ļoti vienkāršs risinājums.

100
00:04:35,310 --> 00:04:37,810
Mums nav jādara nekas īpašs.

101
00:04:37,810 --> 00:04:40,560
 Skaitļa 1 faktoriāls ir tikai 1.

102
00:04:40,560 --> 00:04:42,790
Mums vispār nav jādara nekāda
reizināšana.

103
00:04:42,790 --> 00:04:46,700
Šķiet, ja mēs mēģināsim atrisināt
šo problēmu un mums kaut kur ir 

104
00:04:46,700 --> 00:04:50,610
jāpārtrauc rekursija, mēs,
iespējams, vēlēsimies to apturēt pie 1. 

105
00:04:50,610 --> 00:04:54,580
Mēs nevēlamies apstāties pirms tam.

106
00:04:54,580 --> 00:04:56,635
Tātad, ja mēs definējam savu
faktoriālu funkciju, tad šeit ir 

107
00:04:56,635 --> 00:04:58,690
skelets, kā mēs to varētu izdarīt. 

108
00:04:58,690 --> 00:05:03,110
Mums ir jāpievieno šīs divas
lietas — bāzes bloku un rekursīvo bloku.

109
00:05:03,110 --> 00:05:04,990
Kas ir bāzes bloks?

110
00:05:04,990 --> 00:05:07,570
Ja n ir vienāds ar 1, atgrieziet
1 — tā ir patiešām vienkārša 

111
00:05:07,570 --> 00:05:10,150
problēma, ko risināt. 

112
00:05:10,150 --> 00:05:11,890
Skaitļa 1 faktoriāls ir 1.

113
00:05:11,890 --> 00:05:13,860
Tas nav 1 reiz jebkas.

114
00:05:13,860 --> 00:05:15,020
Tas ir tikai 1.

115
00:05:15,020 --> 00:05:17,170
Tas ir ļoti vienkāršs fakts.

116
00:05:17,170 --> 00:05:19,620
Un tas varētu būt mūsu bāzes bloks.

117
00:05:19,620 --> 00:05:24,730
Ja šai funkcijai nodosim 1, tad mēs
atgriezīsim tikai 1.

118
00:05:24,730 --> 00:05:27,320
 Kā tad izskatās rekursīvais bloks?

119
00:05:27,320 --> 00:05:32,445
Kāda ir shēma citiem skaitļiem,
izņemot skaitli 1?

120
00:05:32,445 --> 00:05:38,160
Ja mēs ņemam n faktoriālu, tas ir
n reiz n mīnus 1 faktoriāls.

121
00:05:38,160 --> 00:05:42,676
Ja mēs izmantojam skaitļa 3
faktoriālu, tas ir 3 reiz 3 mīnus 1 

122
00:05:42,676 --> 00:05:47,193
faktoriāls. Tātad, ja mēs
neskatāmies uz 1, tad atgriežam n reiz n 

123
00:05:47,193 --> 00:05:51,710
mīnus 1 faktoriāls. 

124
00:05:51,710 --> 00:05:53,210
Tas ir diezgan vienkārši.

125
00:05:53,210 --> 00:05:56,970
Un, lai kods būtu nedaudz tīrāks un
elegantāks, ziniet, ka, ja mums 

126
00:05:56,970 --> 00:06:00,730
ir vienas rindiņas cilpas vai
vienas rindas nosacītais zarojums, mēs 

127
00:06:00,730 --> 00:06:04,490
varam atbrīvoties no visām
figūriekavām tiem apkārt. 

128
00:06:04,490 --> 00:06:06,850
Tātad mēs varam to apvienot ar šo.

129
00:06:06,850 --> 00:06:09,640
Tam ir tieši tāda pati
funkcionalitāte kā šim.

130
00:06:09,640 --> 00:06:14,070
Es tikai noņemu figūriekavas, jo
šajos nosacītajos zarojumos ir tikai 

131
00:06:14,070 --> 00:06:18,500
viena līnija. 

132
00:06:18,500 --> 00:06:21,160
Tātad šie uzvedas identiski.

133
00:06:21,160 --> 00:06:23,800
Ja n ir vienāds ar 1, atgriež 1.

134
00:06:23,800 --> 00:06:28,351
Pretējā gadījumā atgriež n reiz n
mīnus 1 faktoriāls.

135
00:06:28,351 --> 00:06:29,850
Tā mēs padarām problēmu mazāku.

136
00:06:29,850 --> 00:06:33,850
Ja n sākas ar 5, mēs atgriezīsim
skaitļa 4 faktoriāls reiz 5.

137
00:06:33,850 --> 00:06:36,443
Un pēc minūtes mēs redzēsim, kad
runāsim par zvanu steku — citā 

138
00:06:36,443 --> 00:06:39,036
videoklipā, kurā mēs runājam par
zvanu steku - mēs uzzināsim, kāpēc 

139
00:06:39,036 --> 00:06:41,630
tieši šis process darbojas. 

140
00:06:41,630 --> 00:06:44,323
Bet, lai gan skaitļā 5 faktoriāls
saka, ka tiek atgriezts 5 reiz 

141
00:06:44,323 --> 00:06:47,016
skaitļa 4 faktoriāls, un 4 teiks —
labi, labi, atgriež skaitļa 3 

142
00:06:47,016 --> 00:06:49,710
faktoriāls reiz 4. 

143
00:06:49,710 --> 00:06:51,737
Un, kā redzat, mēs tuvojamies 1.

144
00:06:51,737 --> 00:06:53,820
Mēs esam arvien tuvāk un tuvāk šim
bāzes blokam.

145
00:06:53,820 --> 00:06:57,180
Kad esam nokļuvuši pie bāzes bloka,
visām iepriekšējām funkcijām 

146
00:06:57,180 --> 00:07:00,540
parādās atbilde, ko tās meklēja. 

147
00:07:00,540 --> 00:07:03,900
Skaitļa 2 faktoriāls teica atgriezt
2 reiz skaitļa 1 faktoriāls.

148
00:07:03,900 --> 00:07:06,760
Skaitļa 1 faktoriāls atgriež 1.

149
00:07:06,760 --> 00:07:10,370
Tātad skaitļa 2 faktoriāla
izsaukums var atgriezt 2 reiz 1 un atdot 

150
00:07:10,370 --> 00:07:13,980
to skaitļa 3 faktoriālam, kas gaida
šo rezultātu. 

151
00:07:13,980 --> 00:07:16,443
Un tad tas var aprēķināt rezultātu,
3 reiz 2 ir 6, un atdot to 

152
00:07:16,443 --> 00:07:18,907
skaitļa 4 faktoriālam. 

153
00:07:18,907 --> 00:07:21,358
Un atkal, mums ir video par zvanu
steku, kur tas ir ilustrēts nedaudz 

154
00:07:21,358 --> 00:07:23,810
vairāk nekā es stāstu šobrīd. 

155
00:07:23,810 --> 00:07:25,300
Bet tas ir viss.

156
00:07:25,300 --> 00:07:29,300
Tas vien ir risinājums skaitļa
faktoriāla aprēķināšanai.

157
00:07:29,300 --> 00:07:31,527
 Tās ir tikai četras koda rindiņas.

158
00:07:31,527 --> 00:07:32,610
Tas ir diezgan forši, vai ne?

159
00:07:32,610 --> 00:07:35,480
Tas ir seksīgi.

160
00:07:35,480 --> 00:07:38,335
Tātad kopumā, bet ne vienmēr,
rekursīvā funkcija var aizstāt cilpu 

161
00:07:38,335 --> 00:07:41,190
nerekursīvajā funkcijā. 

162
00:07:41,190 --> 00:07:46,100
Tātad šeit blakus ir faktoriāla
funkcijas iteratīvā versija.

163
00:07:46,100 --> 00:07:49,650
Tie abi aprēķina tieši to pašu.

164
00:07:49,650 --> 00:07:52,170
 Tie abi aprēķina n faktoriālu.

165
00:07:52,170 --> 00:07:54,990
Kreisajā pusē esošā versija izmanto
rekursiju, lai to izdarītu.

166
00:07:54,990 --> 00:07:58,320
Labajā pusē esošā versija izmanto
iterāciju, lai to izdarītu.

167
00:07:58,320 --> 00:08:00,185
Un ievērojiet, mums ir jādeklarē
mainīgais kā vesela skaitļa 

168
00:08:00,185 --> 00:08:02,050
reizinājums. 

169
00:08:02,050 --> 00:08:02,940
Un tad mums ir cilpa.

170
00:08:02,940 --> 00:08:06,415
Kamēr n ir lielāks par 0, mēs
turpinām reizināt ar n un samazinām n, 

171
00:08:06,415 --> 00:08:09,890
līdz mēs aprēķinām reizinājumu. 

172
00:08:09,890 --> 00:08:14,600
Tātad šīs divas funkcijas atkal
veic tieši to pašu.

173
00:08:14,600 --> 00:08:19,980
Bet tās nedara to vienādā veidā.

174
00:08:19,980 --> 00:08:22,543
Tagad ir iespējams izmantot vairāk
nekā vienu bāzes bloku, vai vairāk 

175
00:08:22,543 --> 00:08:25,106
nekā vienu rekursīvo bloku,
atkarībā no tā, ko jūsu funkcija mēģina 

176
00:08:25,106 --> 00:08:27,670
darīt. 

177
00:08:27,670 --> 00:08:30,020
Jums ne vienmēr ir tikai viens
bāzes bloks vai viens rekursīvais 

178
00:08:30,020 --> 00:08:32,370
bloks. 

179
00:08:32,370 --> 00:08:35,100
Tātad piemērs tam, kam ir vairāki
bāzes bloki, varētu būt šis — 

180
00:08:35,100 --> 00:08:37,830
Fibonači skaitļu virkne. 

181
00:08:37,830 --> 00:08:41,785
Jūs atceraties no pamatskolas
laikiem, ka Fibonači virkne ir definēta 

182
00:08:41,785 --> 00:08:45,740
šādi — pirmais elements ir 0. 

183
00:08:45,740 --> 00:08:46,890
Otrais elements ir 1.

184
00:08:46,890 --> 00:08:49,230
Abi šie ir tikai pēc definīcijas.

185
00:08:49,230 --> 00:08:52,575
Tad katrs nākamais elements tiek
definēts kā n mīnus 1 un n mīnus 2 

186
00:08:52,575 --> 00:08:55,920
summa. 

187
00:08:55,920 --> 00:09:00,330
Tātad trešais elements būtu 0 plus
1 ir 1.

188
00:09:00,330 --> 00:09:03,440
Un tad ceturtais elements būtu
otrais elements 1 un trešais elements 

189
00:09:03,440 --> 00:09:06,550
1. 

190
00:09:06,550 --> 00:09:08,507
Un tas būtu 2.

191
00:09:08,507 --> 00:09:09,340
Un tā tālāk un tā tālāk.

192
00:09:09,340 --> 00:09:11,680
 Tātad šajā gadījumā mums ir divi
bāzes bloki.

193
00:09:11,680 --> 00:09:14,850
Ja n ir vienāds ar 1, atgriež 0.

194
00:09:14,850 --> 00:09:18,560
Ja n ir vienāds ar 2, atgriež 1.

195
00:09:18,560 --> 00:09:22,245
Pretējā gadījumā atgriež Fibonači
no n mīnus 1, plus Fibonači no n 

196
00:09:22,245 --> 00:09:25,930
mīnus 2. 

197
00:09:25,930 --> 00:09:27,180
 Tātad tie ir vairāki bāzes bloki.

198
00:09:27,180 --> 00:09:29,271
Kā ar vairākiem rekursīvajiem
blokiem?

199
00:09:29,271 --> 00:09:31,520
Nu, ir kaut kas, ko sauc par Kolata
minējumu.

200
00:09:31,520 --> 00:09:34,845
Es neteikšu, ka jūs zināt, kas tas
ir, jo īstenībā tas ir mūsu 

201
00:09:34,845 --> 00:09:38,170
pēdējais uzdevums šajā konkrētajā
videoklipā. 

202
00:09:38,170 --> 00:09:43,220
Un tas ir mūsu uzdevums, pie kā
strādāsim kopā.

203
00:09:43,220 --> 00:09:46,020
Tātad, lūk, kas ir Kolata
minējums — tas attiecas uz jebkuru pozitīvu 

204
00:09:46,020 --> 00:09:48,820
veselu skaitli. 

205
00:09:48,820 --> 00:09:51,940
Un tas liek domāt, ka vienmēr ir
iespējams atgriezties pie 1, ja 

206
00:09:51,940 --> 00:09:55,060
veicat šīs darbības. 

207
00:09:55,060 --> 00:09:57,560
Ja n ir 1, apstājieties.

208
00:09:57,560 --> 00:10:00,070
Mēs esam atgriezušies pie 1, ja n
ir 1.

209
00:10:00,070 --> 00:10:05,670
 Pretējā gadījumā atkārtojiet šo
procesu, kad n dalīts ar 2.

210
00:10:05,670 --> 00:10:08,200
Un pārbaudiet, vai varat
atgriezties pie 1.

211
00:10:08,200 --> 00:10:11,876
Pretējā gadījumā, ja n ir nepāra
skaitlis, atkārtojiet šo procesu 

212
00:10:11,876 --> 00:10:15,552
vēlreiz ar 3n plus 1 vai 3 reiz n
plus 1. 

213
00:10:15,552 --> 00:10:17,010
Tātad šeit mums ir viens bāzes
bloks.

214
00:10:17,010 --> 00:10:18,430
Ja n ir vienāds ar 1, apstājieties.

215
00:10:18,430 --> 00:10:20,230
Mēs vairs neveicam rekursiju.

216
00:10:20,230 --> 00:10:23,730
 Bet mums ir divi rekursīvie bloki.

217
00:10:23,730 --> 00:10:26,240
Ja n ir pāra skaitlis, mēs veicam
vienu rekursīvo bloku, izsaucot n 

218
00:10:26,240 --> 00:10:28,750
dalītu ar 2. 

219
00:10:28,750 --> 00:10:31,350
Ja n ir nepāra skaitlis, mēs veicam
citu rekursīvo bloku 3 reiz n 

220
00:10:31,350 --> 00:10:33,950
plus 1. 

221
00:10:33,950 --> 00:10:38,570
Un tāpēc šī videoklipa mērķis ir
nesteigties, nopauzēt video un 

222
00:10:38,570 --> 00:10:43,190
mēģināt uzrakstīt šo Kolata
rekursīvo funkciju, kur jūs ievadāt 

223
00:10:43,190 --> 00:10:47,810
vērtību n, un tā aprēķina, cik soļu
nepieciešams, lai nokļūtu līdz 1, 

224
00:10:47,810 --> 00:10:52,430
ja sākat no n un veicat iepriekš
norādītās darbības. 

225
00:10:52,430 --> 00:10:56,660
Ja n ir 1, tas aizņem 0 soļus.

226
00:10:56,660 --> 00:11:00,473
Pretējā gadījumā tas prasīs vienu
soli plus daudz soļu, vai nu n 

227
00:11:00,473 --> 00:11:04,286
dalīts ar 2, ja n ir pāra skaitlis,
vai 3n plus 1, ja n ir nepāra 

228
00:11:04,286 --> 00:11:08,100
skaitlis. 

229
00:11:08,100 --> 00:11:12,196
Tagad šeit uz ekrāna rādīšu dažus
piemērus , dažus testa gadījumus, 

230
00:11:12,196 --> 00:11:16,293
lai redzētu, kas ir šie dažādie
Kolata skaitļi, kā arī ilustrāciju 

231
00:11:16,293 --> 00:11:20,390
darbībām, kas jāveic, lai jūs varat
redzēt šo procesu darbībā. 

232
00:11:20,390 --> 00:11:24,222
Tātad, ja n ir vienāds ar 1, Kolata
skaitlis n ir 0.

233
00:11:24,222 --> 00:11:26,180
Jums nekas nav jādara, lai
atgrieztos pie 1.

234
00:11:26,180 --> 00:11:27,600
Jūs jau tur esat.

235
00:11:27,600 --> 00:11:30,550
 Ja n ir 2, ir nepieciešams viens
solis, lai nokļūtu līdz 1.

236
00:11:30,550 --> 00:11:31,810
Jūs sākat ar 2.

237
00:11:31,810 --> 00:11:33,100
Nu, 2 nav vienāds ar 1.

238
00:11:33,100 --> 00:11:35,557
Tātad tas būs viens solis plus
neatkarīgi no tā, cik daudz soļu tas 

239
00:11:35,557 --> 00:11:38,015
veic, n dalīts ar 2. 

240
00:11:41,280 --> 00:11:42,910
 2 dalīts ar 2 ir 1.

241
00:11:42,910 --> 00:11:45,055
Tātad tas aizņem vienu soli plus
neatkarīgi no tā, cik daudz soļu tas 

242
00:11:45,055 --> 00:11:47,200
prasa līdz 1. 

243
00:11:47,200 --> 00:11:49,720
1 veic nulli soļus.

244
00:11:49,720 --> 00:11:52,370
 Attiecībā uz 3, kā redzat, ir
jāveic vairākas darbības.

245
00:11:52,370 --> 00:11:53,590
Jūs ejat no 3.

246
00:11:53,590 --> 00:11:56,710
Un tad jūs dodaties uz 10, 5, 16,
8, 4, 2, 1.

247
00:11:56,710 --> 00:11:58,804
Lai atgrieztos pie 1, ir jāveic
septiņi soļi.

248
00:11:58,804 --> 00:12:00,637
Un, kā redzat, šeit ir daži citi
testa gadījumi, lai pārbaudītu savu 

249
00:12:00,637 --> 00:12:02,470
programmu. 

250
00:12:02,470 --> 00:12:03,970
Tāpēc vēlreiz apturiet video.

251
00:12:03,970 --> 00:12:11,390
Un es tagad atgriezīšos pie
faktiskā procesa, kas ir šis minējums.

252
00:12:11,390 --> 00:12:15,678
Skatieties, vai varat saprast, kā
definēt n Kolata skaitli, lai tas 

253
00:12:15,678 --> 00:12:19,967
aprēķinātu, cik soļu nepieciešams,
lai nokļūtu līdz 1. 

254
00:12:19,967 --> 00:12:22,893
Tāpēc cerams, ka esat apturējuši
video un negaidāt, kad es jums 

255
00:12:22,893 --> 00:12:25,820
sniegšu atbildi. 

256
00:12:25,820 --> 00:12:29,120
Bet, ja jūs gaidāt, tad šeit ir
atbilde jebkurā gadījumā.

257
00:12:29,120 --> 00:12:33,070
 Tātad šeit ir iespējama Kolata
funkcijas definīcija.

258
00:12:33,070 --> 00:12:35,610
Mūsu bāzes bloks — ja n ir vienāds
ar 1, mēs atgriežam 0.

259
00:12:35,610 --> 00:12:38,250
Nav jāveic nekādas darbības, lai
atgrieztos pie 1.

260
00:12:38,250 --> 00:12:40,480
Pretējā gadījumā mums ir divi
rekursīvie bloki — viens pāra skaitļiem 

261
00:12:40,480 --> 00:12:42,710
un otrs nepāra skaitļiem. 

262
00:12:42,710 --> 00:12:44,937
Pāra skaitļu pārbaudes veids ir
pārbaudīt, vai n mod 2 ir vienāds ar 

263
00:12:44,937 --> 00:12:47,164
0. 

264
00:12:47,164 --> 00:12:50,607
Tas būtībā atkal ir jautājums, ja
atceraties, kas ir mod - ja es dalu 

265
00:12:50,607 --> 00:12:54,050
n ar 2, vai nav atlikuma? 

266
00:12:54,050 --> 00:12:55,470
Tas būtu pāra skaitlis.

267
00:12:55,470 --> 00:12:58,420
Tātad, ja n mod 2 ir vienāds ar 0,
tiek pārbaudīts, vai tas ir pāra 

268
00:12:58,420 --> 00:13:01,370
skaitlis. 

269
00:13:01,370 --> 00:13:05,320
Ja tā, es vēlos atgriezt 1, jo tas
noteikti aizņem vienu soli plus 

270
00:13:05,320 --> 00:13:09,270
jebkura skaitļa Kolata skaitlis,
dalīts uz pusi. 

271
00:13:09,270 --> 00:13:11,590
Pretējā gadījumā es vēlos atgriezt
1 plus Kolata skaitlis no 3 reiz n 

272
00:13:11,590 --> 00:13:13,910
plus 1. 

273
00:13:13,910 --> 00:13:16,810
Tas bija otrs rekursīvais solis, ko
varējām veikt, lai aprēķinātu 

274
00:13:16,810 --> 00:13:19,710
Kolata skaitli — soļu skaits, kas
nepieciešams, lai atgrieztos pie 1, 

275
00:13:19,710 --> 00:13:22,610
ņemot vērā skaitli. 

276
00:13:22,610 --> 00:13:24,615
Tāpēc cerams, ka šis piemērs
sniedza jums nelielu priekšstatu par 

277
00:13:24,615 --> 00:13:26,620
rekursīvajām procedūrām . 

278
00:13:26,620 --> 00:13:29,690
Es ceru, ka jūs domājat, ka kods ir
nedaudz skaistāks, ja tas tiek 

279
00:13:29,690 --> 00:13:32,760
ieviests elegantā, rekursīvā veidā.


280
00:13:32,760 --> 00:13:34,357
Bet pat ja nedomājiet, rekursija
tomēr ir patiešām spēcīgs 

281
00:13:34,357 --> 00:13:35,955
instruments. 

282
00:13:35,955 --> 00:13:38,448
Tāpēc tas noteikti ir kaut kas
tāds, ko vajadzētu saprast, jo, 

283
00:13:38,448 --> 00:13:40,942
izmantojot rekursiju, varēsiet
veidot patiešām foršas programmas, 

284
00:13:40,942 --> 00:13:43,436
kuras citādi būtu sarežģīti
uzrakstītas, ja izmantojat cilpas un 

285
00:13:43,436 --> 00:13:45,930
iterāciju. 

286
00:13:45,930 --> 00:13:46,980
Es esmu Dags Loids.

287
00:13:46,980 --> 00:13:48,780
Šis ir CS50.