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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Er mwyn deall
recursion, rhaid i chi

3
00:00:10,190 --> 00:00:13,820
yn gyntaf yn deall recursion.

4
00:00:13,820 --> 00:00:17,280
Mae cael recursion mewn modd dylunio rhaglen
eich bod wedi hunan-cyfeiriadol

5
00:00:17,280 --> 00:00:18,570
diffiniadau.

6
00:00:18,570 --> 00:00:21,520
Strwythurau data ailadroddus, er enghraifft,
strwythurau data a

7
00:00:21,520 --> 00:00:23,990
gynnwys eu hunain mewn
eu diffiniadau.

8
00:00:23,990 --> 00:00:27,160
Ond heddiw, rydym yn mynd i ganolbwyntio
ar swyddogaethau ailadroddus.

9
00:00:27,160 --> 00:00:31,160
>> Dwyn i gof bod y swyddogaethau cymryd mewnbynnau,
dadleuon, a dychwelyd werth fel eu

10
00:00:31,160 --> 00:00:34,480
allbwn a gynrychiolir gan
diagram hwn yma.

11
00:00:34,480 --> 00:00:38,060
Byddwn yn meddwl am y blwch fel y corff o
swyddogaeth, yn cynnwys set o

12
00:00:38,060 --> 00:00:42,340
cyfarwyddiadau sy'n dehongli'r
mewnbwn a darparu allbwn.

13
00:00:42,340 --> 00:00:45,660
Gymryd golwg agosach y tu mewn i'r corff
gallai'r swyddogaeth ddatgelu galwadau i

14
00:00:45,660 --> 00:00:47,430
swyddogaethau eraill hefyd.

15
00:00:47,430 --> 00:00:51,300
Cymerwch y swyddogaeth syml, foo, bod
cymryd llinyn unigol fel mewnbwn a

16
00:00:51,300 --> 00:00:54,630
printiau faint o lythyrau
y llinyn wedi.

17
00:00:54,630 --> 00:00:58,490
Mae'r strlen swyddogaeth, ar gyfer hyd llinyn,
gelwir, y mae ei allbwn yn

18
00:00:58,490 --> 00:01:01,890
eu hangen ar gyfer yr alwad i printf.

19
00:01:01,890 --> 00:01:05,770
>> Yn awr, yr hyn sy'n gwneud swyddogaeth ailadroddus
arbennig yw ei fod yn galw ei hun.

20
00:01:05,770 --> 00:01:09,610
Gall Rydym yn cynrychioli recursive hwn
yn galw â'r saeth oren

21
00:01:09,610 --> 00:01:11,360
dolennu yn ôl i ei hun.

22
00:01:11,360 --> 00:01:15,630
Ond gweithredu ei hun unwaith eto yn unig y bydd
gwneud yr alwad ailadroddus arall, a

23
00:01:15,630 --> 00:01:17,150
un arall ac un arall.

24
00:01:17,150 --> 00:01:19,100
Ond mae swyddogaethau recursive
ni all fod yn ddiddiwedd.

25
00:01:19,100 --> 00:01:23,490
Maent wedi dod i ben rywsut, neu eich
Bydd y rhaglen yn rhedeg am byth.

26
00:01:23,490 --> 00:01:27,680
>> Felly, mae angen i ni ddod o hyd i ffordd i dorri
allan o'r galwadau ailadroddus.

27
00:01:27,680 --> 00:01:29,900
Rydym yn galw hyn yn achos sylfaenol.

28
00:01:29,900 --> 00:01:33,570
Pan fydd y cyflwr achos sylfaen yn cael ei fodloni,
y swyddogaeth yn dychwelyd heb wneud

29
00:01:33,570 --> 00:01:34,950
alwad ailadroddus arall.

30
00:01:34,950 --> 00:01:39,610
Cymerwch y swyddogaeth hon, hi, swyddogaeth ddi-rym
sy'n cymryd int n fel mewnbwn.

31
00:01:39,610 --> 00:01:41,260
Mae'r achos sylfaenol yn dod yn gyntaf.

32
00:01:41,260 --> 00:01:46,220
Os yw n yn llai na sero, is print a
dychwelyd gyfer pob achos arall, mae'r

33
00:01:46,220 --> 00:01:49,400
Bydd swyddogaeth argraffu hi a gweithredu
yr alwad ailadroddus.

34
00:01:49,400 --> 00:01:53,600
Alwad arall i'r swyddogaeth hi gyda
gwerth mewnbwn ostwng o.

35
00:01:53,600 --> 00:01:56,790
>> Yn awr, er ein bod yn argraffu hi, y
Ni fydd swyddogaeth yn dod i ben hyd nes y byddwn

36
00:01:56,790 --> 00:02:00,370
dychwelyd ei fath yn ôl,
yn yr achos yn ddi-rym.

37
00:02:00,370 --> 00:02:04,830
Felly, ar gyfer pob n ac eithrio'r achos sylfaenol,
bydd y swyddogaeth hi yn dychwelyd hi

38
00:02:04,830 --> 00:02:06,890
n minws 1.

39
00:02:06,890 --> 00:02:10,050
Gan fod y swyddogaeth hon yn ddi-rym, fodd bynnag, rydym yn
Ni fydd deipio ddychwelyd yn benodol yma.

40
00:02:10,050 --> 00:02:12,000
Byddwn yn unig gyflawni'r swyddogaeth.

41
00:02:12,000 --> 00:02:16,960
Felly, galw hi (3) yn argraffu hi a
gweithredu hi (2) sy'n executes hi (1) un

42
00:02:16,960 --> 00:02:20,560
sy'n executes hi (0), lle mae'r
cyflwr achos sylfaenol yn cael ei fodloni.

43
00:02:20,560 --> 00:02:24,100
Felly hi (0) printiau is a ffurflenni.

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

45
00:02:24,990 --> 00:02:28,690
Felly nawr ein bod yn deall hanfodion
swyddogaethau ailadroddus, bod angen

46
00:02:28,690 --> 00:02:32,730
o leiaf un achos sylfaenol yn ogystal â
alwad ailadroddus, gadewch i ni symud ymlaen i

47
00:02:32,730 --> 00:02:34,120
enghraifft mwy ystyrlon.

48
00:02:34,120 --> 00:02:37,830
Un nad yw'n unig yn dychwelyd
ddi-rym ni waeth beth.

49
00:02:37,830 --> 00:02:41,340
>> Gadewch i ni edrych ar y ffactoraidd
gweithredu a ddefnyddir yn fwyaf cyffredin mewn

50
00:02:41,340 --> 00:02:43,660
cyfrifiadau tebygolrwydd.

51
00:02:43,660 --> 00:02:48,120
Ffactorial n yn gynnyrch pob
gyfanrif positif llai na

52
00:02:48,120 --> 00:02:49,400
a chyfartal i n.

53
00:02:49,400 --> 00:02:56,731
Pum Felly ffactoraidd 5 gwaith 4 gwaith
3 gwaith 2 waith 1 i roi 120.

54
00:02:56,731 --> 00:03:01,400
Pedwar ffactor yn 4 gwaith 3 gwaith
2 gwaith 1 i roi 24.

55
00:03:01,400 --> 00:03:04,910
Ac mae'r un rheol yn gymwys
i unrhyw gyfanrif positif.

56
00:03:04,910 --> 00:03:08,670
>> Felly, sut y gallem ysgrifennu dychweliadol
swyddogaeth sy'n cyfrifo'r ffactoraidd

57
00:03:08,670 --> 00:03:09,960
o nifer?

58
00:03:09,960 --> 00:03:14,700
Wel, bydd angen i ni ganfod y
achos sylfaenol a'r galw ailadroddus.

59
00:03:14,700 --> 00:03:18,250
Bydd yr alwad ailadroddus fod yr un fath
ar gyfer pob achos ac eithrio ar gyfer y sylfaen

60
00:03:18,250 --> 00:03:21,420
achos, sy'n golygu y bydd yn rhaid i ni
dod o hyd i batrwm a fydd yn rhoi i ni ein

61
00:03:21,420 --> 00:03:23,350
canlyniad a ddymunir.

62
00:03:23,350 --> 00:03:30,270
>> Ar gyfer yr enghraifft, weld sut 5 ffactoraidd
cynnwys lluosi 4 3 2 1

63
00:03:30,270 --> 00:03:33,010
Ac yr un iawn lluosi
yn dod o hyd yma, y

64
00:03:33,010 --> 00:03:35,430
diffiniad o 4 ffactoraidd.

65
00:03:35,430 --> 00:03:39,810
Felly, rydym yn gweld bod 5 ffactoraidd yn
dim ond 5 gwaith 4 ffactoraidd.

66
00:03:39,810 --> 00:03:43,360
Nawr mae patrwm hwn yn berthnasol
i 4 ffactor hefyd?

67
00:03:43,360 --> 00:03:44,280
Ie.

68
00:03:44,280 --> 00:03:49,120
Rydym yn gweld bod 4 ffactoraidd yn cynnwys y
lluosi 3 gwaith 2 waith 1, mae'r

69
00:03:49,120 --> 00:03:51,590
yr un iawn diffiniad 3 ffactoraidd.

70
00:03:51,590 --> 00:03:56,950
Hynny 4 ffactoraidd yn hafal i 4 gwaith 3
ffactor, ac yn y blaen ac yn y blaen ar ein

71
00:03:56,950 --> 00:04:02,170
patrwm ffyn tan 1 ffactoraidd, a oedd yn
trwy ddiffiniad yn hafal i 1.

72
00:04:02,170 --> 00:04:04,950
>> Does dim cadarnhaol eraill
cyfanrifau ar ôl.

73
00:04:04,950 --> 00:04:07,870
Felly, rydym yn cael y patrwm ar gyfer
i'n galwad ailadroddus.

74
00:04:07,870 --> 00:04:13,260
n ffactoraidd yn hafal i amseroedd n
y ffactor n minws 1.

75
00:04:13,260 --> 00:04:14,370
Ac mae ein achos sylfaenol?

76
00:04:14,370 --> 00:04:17,370
Bydd hynny'n unig fod ein diffiniad
o 1 ffactoraidd.

77
00:04:17,370 --> 00:04:19,995
>> Felly nawr gallwn symud ymlaen i ysgrifennu
cod ar gyfer y swyddogaeth.

78
00:04:19,995 --> 00:04:24,110
Ar gyfer yr achos sylfaenol, bydd gennym y
cyflwr n hafal hafal 1, lle

79
00:04:24,110 --> 00:04:25,780
byddwn yn dychwelyd 1.

80
00:04:25,780 --> 00:04:29,280
Yna, symud ymlaen i'r alwad ailadroddus,
byddwn yn dychwelyd amseroedd n y

81
00:04:29,280 --> 00:04:32,180
ffactorial n minws 1.

82
00:04:32,180 --> 00:04:33,590
>> Nawr, gadewch i ni brofi ein hyn.

83
00:04:33,590 --> 00:04:35,900
Gadewch i ni geisio ffactoraidd 4.

84
00:04:35,900 --> 00:04:39,420
Fesul ein swyddogaeth ei fod yn gyfartal
i 4 gwaith ffactoraidd (3).

85
00:04:39,420 --> 00:04:43,040
Ffactoraidd (3) yn hafal i
3 gwaith ffactoraidd (2).

86
00:04:43,040 --> 00:04:48,700
Ffactoraidd (2) yn hafal i 2 gwaith
ffactoraidd (1), sy'n dychwelyd 1.

87
00:04:48,700 --> 00:04:52,490
Ffactoraidd (2) yn dychwelyd 2 waith 1, 2.

88
00:04:52,490 --> 00:04:55,960
Ffactoraidd (3) yn awr yn dychwelyd
3 gwaith 2, 6.

89
00:04:55,960 --> 00:05:02,490
Ac yn olaf, ffactoraidd (4)
dychwelyd 4 gwaith 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Os ydych yn dod ar draws unrhyw anhawster
â'r alwad ailadroddus, esgus bod

91
00:05:06,780 --> 00:05:09,660
y swyddogaeth yn gweithio'n barod.

92
00:05:09,660 --> 00:05:13,450
Beth allaf i ei olygu wrth hyn yw y dylech
ymddiried yn eich galwadau ailadroddus i ddychwelyd

93
00:05:13,450 --> 00:05:15,100
gwerthoedd cywir.

94
00:05:15,100 --> 00:05:18,960
Er enghraifft, os wyf yn gwybod y
ffactoraidd (5) yn hafal i 5 gwaith

95
00:05:18,960 --> 00:05:24,870
ffactoraidd (4), yr wyf i'n mynd i ymddiried yn y
ffactoraidd (4) yn rhoi i mi 24.

96
00:05:24,870 --> 00:05:28,510
Meddyliwch am y peth fel newidyn, os ydych yn
fydd, fel pe baech eisoes wedi'u diffinio

97
00:05:28,510 --> 00:05:30,070
ffactoraidd (4).

98
00:05:30,070 --> 00:05:33,850
Felly, ar gyfer unrhyw ffactoraidd (n), mae'n
gynnyrch n ac

99
00:05:33,850 --> 00:05:35,360
y ffactoraidd flaenorol.

100
00:05:35,360 --> 00:05:38,130
Ac mae hyn yn ffactoraidd blaenorol
yn cael ei sicrhau drwy ffonio

101
00:05:38,130 --> 00:05:41,330
ffactorial n minws 1.

102
00:05:41,330 --> 00:05:45,130
>> Yn awr, weld a allwch chi weithredu
recursive weithredu eich hun.

103
00:05:45,130 --> 00:05:50,490
Llwytho i fyny eich terfynell, neu run.cs50.net,
ac ysgrifennu swm swyddogaeth

104
00:05:50,490 --> 00:05:54,770
sy'n cymryd cyfanrif n ac yn dychwelyd y
swm yr holl positif yn olynol

105
00:05:54,770 --> 00:05:57,490
chyfanrifau o n i 1.

106
00:05:57,490 --> 00:06:01,000
Rwyf wedi ysgrifennu allan y symiau o rai
gwerthoedd i helpu chi ein.

107
00:06:01,000 --> 00:06:04,030
Yn gyntaf, chyfrif i maes y
cyflwr achos sylfaenol.

108
00:06:04,030 --> 00:06:06,170
Yna, edrychwch ar swm (5).

109
00:06:06,170 --> 00:06:09,270
Allwch chi fynegi mewn termau
o'r swm arall?

110
00:06:09,270 --> 00:06:11,290
Nawr, beth am swm (4)?

111
00:06:11,290 --> 00:06:15,630
Sut y gallwch fynegi swm (4)
o ran swm arall?

112
00:06:15,630 --> 00:06:19,655
>> Unwaith y byddwch yn cael swm (5) a swm (4)
mynegi yn nhermau symiau eraill, gweler

113
00:06:19,655 --> 00:06:22,970
os gallwch nodi
patrwm ar gyfer swm (n).

114
00:06:22,970 --> 00:06:26,190
Os nad yw, rhowch gynnig ar ychydig o rifau eraill
a mynegi eu symiau yn

115
00:06:26,190 --> 00:06:28,410
ran niferoedd arall.

116
00:06:28,410 --> 00:06:31,930
Drwy nodi patrymau ar gyfer arwahanol
rhifau, rydych yn dda ar eich ffordd i

117
00:06:31,930 --> 00:06:34,320
nodi'r patrwm ar gyfer unrhyw n.

118
00:06:34,320 --> 00:06:38,040
>> Recursion yn arf pwerus iawn,
felly, wrth gwrs nid yw'n gyfyngedig i

119
00:06:38,040 --> 00:06:39,820
swyddogaethau mathemategol.

120
00:06:39,820 --> 00:06:44,040
Gellir defnyddio recursion yn effeithiol iawn
wrth ymdrin â choed er enghraifft.

121
00:06:44,040 --> 00:06:47,210
Edrychwch ar y byr ar goed ar gyfer
mwy o adolygiad trwyadl, ond am y tro

122
00:06:47,210 --> 00:06:51,140
dwyn i gof bod coed chwiliad deuaidd, yn
benodol, yn cynnwys nodau, pob

123
00:06:51,140 --> 00:06:53,820
gyda gwerth a dau awgrymiadau nod.

124
00:06:53,820 --> 00:06:57,270
Fel arfer, mae hyn yn ei gynrychioli gan y
rhiant nod cael un pwyntio llinell

125
00:06:57,270 --> 00:07:01,870
at y nôd plentyn chwith ac un
at y nôd plentyn cywir.

126
00:07:01,870 --> 00:07:04,510
Mae strwythur chwiliad deuaidd
goeden yn benthyg ei hun yn dda

127
00:07:04,510 --> 00:07:05,940
i chwilio ailadroddus.

128
00:07:05,940 --> 00:07:09,730
Mae'r alwad ailadroddus naill ai yn mynd yn y
chwith neu y nod iawn, ond yn fwy

129
00:07:09,730 --> 00:07:10,950
o hynny yn y tymor byr coed.

130
00:07:10,950 --> 00:07:15,690
>> Dywedwch eich bod chi eisiau i berfformio llawdriniaeth ar
pob un nod mewn coeden deuaidd.

131
00:07:15,690 --> 00:07:17,410
Sut y gallwch fynd am hynny?

132
00:07:17,410 --> 00:07:20,600
Wel, gallech chi ysgrifennu dychweliadol
swyddogaeth sy'n perfformio y llawdriniaeth

133
00:07:20,600 --> 00:07:24,450
ar y rhiant nôd ac yn gwneud dychweliadol
yn galw i'r un swyddogaeth,

134
00:07:24,450 --> 00:07:27,630
pasio yn y chwith a
nodau plentyn iawn.

135
00:07:27,630 --> 00:07:31,650
Er enghraifft, y swyddogaeth hon, foo, bod
yn newid y gwerth nod a roddwyd ac

136
00:07:31,650 --> 00:07:33,830
ei holl blant i 1.

137
00:07:33,830 --> 00:07:37,400
Yr achos sylfaenol o achosion nod null
y swyddogaeth i ddychwelyd, gan nodi

138
00:07:37,400 --> 00:07:41,290
nad oes unrhyw nodau
ar ôl yn yr is-coed.

139
00:07:41,290 --> 00:07:42,620
>> Gadewch i ni gerdded trwyddo.

140
00:07:42,620 --> 00:07:44,340
Y rhiant cyntaf yw 13.

141
00:07:44,340 --> 00:07:47,930
Rydym yn newid y gwerth i 1, ac yna galw
ein swyddogaeth ar y chwith, yn ogystal

142
00:07:47,930 --> 00:07:49,600
fel yr hawl.

143
00:07:49,600 --> 00:07:53,910
Mae'r swyddogaeth, foo, a elwir yn ar y chwith
is-goeden gyntaf, felly y nod chwith

144
00:07:53,910 --> 00:07:57,730
Bydd yn cael ei symudir i 1 a foo yn
cael eu galw ar blant y nod, yn

145
00:07:57,730 --> 00:08:01,900
yn gyntaf y chwith ac yna i'r dde,
ac yn y blaen ac yn y blaen.

146
00:08:01,900 --> 00:08:05,630
A dweud wrthynt nad yw canghennau oes gan
unrhyw mwy o blant felly mae'r un broses

147
00:08:05,630 --> 00:08:09,700
yn parhau ar gyfer y plant cywir
hyd nes y nodau y goeden gyfan yn

148
00:08:09,700 --> 00:08:11,430
symudir i 1.

149
00:08:11,430 --> 00:08:15,390
>> Fel y gwelwch, nid ydych yn gyfyngedig
i ddim ond un recursive alwad.

150
00:08:15,390 --> 00:08:17,930
Yn union fel y mae llawer gan y bydd yn cael y swydd ei wneud.

151
00:08:17,930 --> 00:08:21,200
Beth os oedd gennych coeden lle mae pob
Roedd nod dri o blant,

152
00:08:21,200 --> 00:08:23,100
Chwith, canol, ac i'r dde?

153
00:08:23,100 --> 00:08:24,886
Sut fyddech chi olygu foo?

154
00:08:24,886 --> 00:08:25,860
Wel, yn syml.

155
00:08:25,860 --> 00:08:30,250
Dim ond ychwanegu alwad recursive arall ac
pasio yn y pwyntydd nod canol.

156
00:08:30,250 --> 00:08:34,549
>> Recursion yn bwerus iawn ac i beidio â
sôn am cain, ond gall fod yn

157
00:08:34,549 --> 00:08:38,010
gysyniad anodd ar y dechrau, felly byddwch yn
cleifion a chymerwch eich amser.

158
00:08:38,010 --> 00:08:39,370
Dechreuwch gyda'r achos sylfaenol.

159
00:08:39,370 --> 00:08:42,650
Fel arfer yw'r hawsaf i nodi,
ac yna gallwch weithio

160
00:08:42,650 --> 00:08:43,830
yn ôl oddi yno.

161
00:08:43,830 --> 00:08:46,190
Rydych yn gwybod mae angen i chi gyrraedd eich
achos sylfaenol, fel y gallai

162
00:08:46,190 --> 00:08:47,760
rhoi ychydig o awgrymiadau i chi.

163
00:08:47,760 --> 00:08:53,120
Ceisiwch i fynegi un achos penodol yn
o ran achosion eraill, neu yn is-setiau.

164
00:08:53,120 --> 00:08:54,700
>> Diolch am wylio hyn byr.

165
00:08:54,700 --> 00:08:58,920
Ar y lleiaf, yn awr gallwch
deall jôcs fel hyn.

166
00:08:58,920 --> 00:09:01,250
Fy enw i yw Zamyla, ac mae hyn yn CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Cymerwch y swyddogaeth hon, hi, a
swyddogaeth eiddo gwag sy'n cymryd

169
00:09:07,170 --> 00:09:09,212
yn int, n, fel mewnbwn.

170
00:09:09,212 --> 00:09:11,020
Mae'r achos sylfaenol yn dod yn gyntaf.

171
00:09:11,020 --> 00:09:14,240
Os yw n yn llai na 0, print
"Bye" a dychwelyd.

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