>> [Ag seinm ceoil]
>> DOUG LLOYD: Cheapann tú dócha go Tá cód úsáid ach a chur i gcrích tasc.
Scríobhann tú amach é.
A dhéanann sé rud éigin.
Sin go leor i bhfad é.
>> Tú thiomsú é.
Ritheann tú an clár.
Tá tú go maith chun dul.
>> Ach chreideann sé nó nach, más rud é chódú agat ar feadh i bhfad,
go dtiocfadh leat teacht iarbhír a fheiceáil cód mar rud éigin go bhfuil go hálainn.
Réitíonn sé an fhadhb i ar bhealach an-spéisiúil,
nó níl ach rud éigin i ndáiríre néata mar gheall ar an mbealach tá sé.
D'fhéadfá a bheith ag gáire ag dom, ach tá sé fíor.
Agus is é recursion bealach amháin a fháil ar an smaoineamh seo saghas
de álainn, galánta-lorg cód.
Réitíonn sé fadhbanna ar bhealaí a atá suimiúil, éasca a shamhlú,
agus ionadh gearr.
>> Na hoibreacha ar bhealach recursion , tá feidhm recursive
Is é an sainmhíniú mar fheidhm go bhfuil gá é féin mar chuid dá fhorghníomhú.
D'fhéadfadh sin is cosúil beagán aisteach, agus beidh orainn a fheiceáil le beagán
faoi ​​conas a oibríonn sé seo i láthair na huaire.
Ach arís, na Tá nósanna imeachta recursive
ag dul a bheith chomh galánta toisc go bhfuil siad ag dul
chun an fhadhb seo a réiteach gan fíor ina leith gach na feidhmeanna eile
nó na lúba fada.
Feicfidh tú a fheiceáil go bhfuil na Athchúrsach nósanna imeachta ag dul chun breathnú chomh gearr.
Agus tá siad i ndáiríre ag dul a dhéanamh do chód breathnú ar a lán níos áille.
>> Beidh mé a thabhairt duit ar shampla de seo a fheiceáil conas
D'fhéadfadh nós imeachta athchúrsach a shainiú.
Mar sin, má tá tú eolach ar seo ó rang math blianta fada ó shin,
níl rud ar a dtugtar an feidhm factorial, a bhfuil de ghnáth
in iúl mar phointe exclamation, a Is é an sainmhíniú ar gach slánuimhreacha dearfach.
Agus an dóigh a n factorial ríomh
Tá tú a iolrú ar fad de na huimhreacha níos lú ná
nó cothrom le together-- n go léir na slánuimhreacha níos lú ná
nó cothrom le n le chéile.
>> Mar sin, tá 5 factorial 5 uaire 4 huaire 3 huaire 2 uair 1.
Agus is é 4 factorial 4 huaire 3 huaire 2 uair 1 agus mar sin de.
A gheobhaidh tú an smaoineamh.
>> Mar ríomhchláraitheoirí, ní dhéanaimid úsáid n, pointe exclamation.
Mar sin, beidh orainn a shainmhíniú ar an factorial feidhm mar go bhfuil an n.
Agus beidh muid ag úsáid factorial a chruthú ar réiteach athchúrsach ar fhadhb.
Agus sílim go d'fhéadfá a fháil go bhfuil sé a lán níos mó amhairc
achomharc ná an atriallach leagan seo, atá
beidh orainn a ghlacadh freisin le breathnú ar i láthair.
>> Mar sin, tá anseo cúpla punt facts-- intended--
faoi ​​factorial-- an feidhm factorial.
An factorial de 1, mar a dúirt mé go bhfuil, 1.
Is é an factorial de 2 2 uair 1.
Is é an factorial de 3 3 amanna 2 uair 1, agus mar sin de.
Labhair muid faoi 4 agus 5 cheana féin.
>> Ach ag féachaint ar seo nach bhfuil, sé sin fíor?
Nach factorial de 2 díreach 2 uair an factorial de 1?
Ciallaíonn mé, is é an factorial de 1 1.
Mar sin, cén fáth nach féidir linn a rá go díreach, ós rud é factorial de 2 2 uair 1,
tá sé i ndáiríre ach 2 uair an factorial de 1?
>> Agus ansin leathnaítear an smaoineamh, Níl an factorial de 3
díreach 3 huaire an factorial de 2?
Agus is é an factorial de 4 4 ​​huaire an factorial de 3, agus mar sin de?
Go deimhin, ar an factorial de líon ar bith is féidir ach
a chur in iúl má táimid de chineál den chur seo amach go deo.
Is féidir linn a ghinearálú cineál an fhadhb factorial
mar tá sé n-uaire an factorial de n lúide 1.
Tá sé n-uaire an táirge de na huimhreacha níos lú ná mise.
>> An smaoineamh, seo ginearálú na faidhbe,
ligeann dúinn hathchúrsach shainmhíniú fheidhm factorial.
Nuair a shainiú tú feidhm hathchúrsach, níl
dhá rud gur gá a bheith ina chuid de.
Ní mór duit go bhfuil rud éigin ar a dtugtar cás bonn, a, nuair a chuireann tús tú é,
Beidh stop a chur leis an bpróiseas athchúrsach.
>> Seachas sin, feidhm a glaonna itself-- mar a d'fhéadfá imagine--
D'fhéadfadh dul ar aghaidh go deo.
Glaonna Feidhm an fheidhm iarrann an glaonna fheidhm
glaonna an fheidhm an fheidhm.
Más rud é nach bhfuil tú ar bhealach chun stop a chur leis, do chlár
Beidh a bheith ligthe go héifeachtach ag lúb gan teorainn.
Beidh sé tuairteála sa deireadh, toisc go mbainfidh sé ar siúl amach as cuimhne.
Ach sin in aice leis an bpointe.
>> Ní mór dúinn a bheith acu ar bhealach éigin eile chun stop a rudaí sa bhreis ar ár crashing gclár,
toisc go bhfuil clár a tuairteanna is dócha nach álainn nó galánta.
Agus mar sin táimid ag glaoch ar an bunchás.
Tá sé seo le réiteach simplí chun fadhb a stopann
an próiseas athchúrsach ó a fhaightear.
Mar sin, go bhfuil cuid amháin de feidhm athchúrsach.
>> Is é an dara cuid an cás athchúrsach.
Agus é seo i gcás an recursion Beidh a chur i ndáiríre ar siúl.
Tá sé seo i gcás an Beidh feidhm glaoch féin.
>> Ní bheidh sé glaoch féin i díreach ar an mbealach céanna go raibh sé ar a dtugtar.
Beidh sé a bheith ina athrú beag go ndéanfaidh an bhfadhb tá sé
ag iarraidh a réiteach le beagán teeny níos lú.
Ach Gabhann sé go ginearálta an buck de réiteach an chuid is mó den réiteach
go glaoch difriúil síos ar an líne.
>> Cé acu de na Breathnaíonn cosúil leis an cás bonn anseo?
Cé acu ceann de na Breathnaíonn cosúil leis an réiteach is simplí ar fhadhb?
Ní mór dúinn a bunch de factorials, agus d'fhéadfadh muid ar aghaidh
dul on-- 6, 7, 8, 9, 10, agus mar sin de.
>> Ach ar cheann de na Breathnaíonn cosúil le cás maith a bheith ar an cás bonn.
Tá sé ar réiteach an-simplí.
Ní chuirimid bhfuil aon rud speisialta a dhéanamh.
>> Is é an factorial de 1 díreach 1.
Nach bhfuil againn a dhéanamh ar bith iolrú ar chor ar bith.
Dealraíonn sé cosúil má táimid ag dul chun iarracht a dhéanamh agus tá sé seo fhadhb a réiteach,
agus ní mór dúinn chun stop a chur recursion áit éigin,
ba mhaith linn is dócha a stopadh sé nuair a fhaigheann muid go 1.
Ní chuirimid ag iarraidh a stopadh roimh.
>> Mar sin, má tá muid ag sainiú ár bhfeidhm factorial,
anseo tá creatlach do conas a d'fhéadfadh muid a dhéanamh.
Ní mór dúinn chun an breiseán i dá things-- an cás bonn agus an cás athchúrsach.
Cad é an cás bonn?
Má tá n cothrom le 1, ar ais 1-- sin fadhb i ndáiríre simplí a réiteach.
>> Is é an factorial de 1 1.
Níl sé 1 uair rud ar bith.
Tá sé díreach 1.
Tá sé an rud an-éasca.
Agus mar sin is féidir a bheith ár gcás bonn.
Má fhaigheann dúinn aghaidh 1 isteach sa fheidhm, beidh muid ar ais díreach 1.
>> Cad é an athchúrsach cás is dócha cuma mhaith?
Le haghaidh gach uimhir eile sa bhreis ar 1, cad é an patrún?
Bhuel, má tá muid ag cur an factorial n,
tá sé amanna n an factorial de n lúide 1.
>> Má tá muid ag cur an factorial de 3, tá sé 3 huaire an factorial de 3 lúide 1,
nó 2.
Agus mar sin má nach bhfuil muid ag féachaint ar 1, ar shlí eile
ar ais n uair an factorial de n lúide 1.
Tá sé deas simplí.
>> Agus ar mhaithe le bheith beagán níos glaine agus níos galánta cód,
Tá a fhios go má táimid tar lúba aon-líne nó aonair-líne brainsí coinníollach,
Is féidir linn a fháil haitheantas coibhneasta de gach ceann de na braces gcuach thart timpeall orthu.
Ionas gur féidir linn a chomhdhlúthú seo a ghabhann leis an.
Seo tá an gcéanna go díreach feidhmiúlacht mar sin.
>> Tá mé ag cur amach an chatach guailleáin, mar níl ach líne amháin
taobh istigh de na brainsí coinníollach.
Mar sin, iad féin a iompar ar na identically.
Má tá n cothrom le 1, ar ais 1.
Seachas sin ar ais amanna n an factorial de n lúide 1.
Mar sin, tá muid ag déanamh an bhfadhb níos lú.
Má thosaíonn n amach mar 5, táimid ag dul chun ar ais 5 uaire an factorial de 4.
Agus beidh orainn a fheiceáil i nóiméad nuair a labhairt linn mar gheall ar an stack-- glaoch i físeán eile
i gcás ina labhairt linn faoi na glaoch stack-- beidh linn a fhoghlaim
faoi ​​cén fáth a oibríonn go díreach leis an bpróiseas seo.
>> Ach deir cé factorial de 5 ar ais 5 uaire factorial de 4, agus 4
ag dul a rá, OK, go maith, ar ais 4 huaire an factorial de 3.
Agus mar is féidir leat a fheiceáil, tá muid saghas druidim 1.
Táimid ag fáil níos gaire agus níos gaire chás sin bonn.
>> Agus nuair a bhuail muid an cás bonn, gach ceann de na feidhmeanna roimhe
tá an freagra go raibh siad ag lorg.
Factorial de 2 bhí ag rá ar ais 2 uair an factorial de 1.
Bhuel, factorial de 1 thuairisceáin 1.
Mar sin, an glao ar factorial de 2 Is féidir le filleadh ar 2 uair 1,
agus a thabhairt go ais go dtí factorial de 3, atá ag fanacht le toradh sin.
>> Agus ansin is féidir é a ríomh a toradh, 3 huaire 2 6,
agus é a thabhairt ar ais go dtí factorial de 4.
Agus arís, ní mór dúinn a físeán ar an chairn glaoch
ina bhfuil sé seo léirithe beagán níos mó ná cad mé ag rá ceart anois.
Ach tá sé seo é.
Tá sé seo ina n-aonar an réiteach a an factorial de roinnt ríomh.
>> Tá sé ach ceithre líne de chód.
Sin deas fionnuar, ceart?
Tá sé de chineál sexy.
>> Mar sin, i gcoitinne, ach ní i gcónaí, feidhm recursive
féidir ionad lúb i fheidhm neamh-recursive.
Mar sin anseo, taobh le taobh, an atriallach Leagan na feidhme factorial.
Tá an dá ríomh díreach an rud céanna.
>> Siad araon ríomh an factorial de n.
An leagan ar thaobh na láimhe clé Úsáideann athchúrsáil a dhéanamh.
An leagan ar an gceart Úsáideann atriall é a dhéanamh.
>> Agus fógra, ní mór dúinn a dhearbhú athróg táirge slánuimhir.
Agus ansin dúinn lúb.
Fad a n Tá níos mó ná 0, táimid ag choinneáil a iolrú táirge sin de réir n
agus decrementing n dtí táimid ag ríomh an táirge.
Mar sin, an dá feidhmeanna, arís, dhéanamh go díreach an rud céanna.
Ach ní dhéanann siad é a dhéanamh i go díreach ar an mbealach céanna.
>> Anois, is féidir tá bonn níos mó ná aon
cás nó níos mó ná ceann amháin cás athchúrsach, ag brath
ar a bhfuil do fheidhm ag iarraidh a dhéanamh.
Nach bhfuil tú gá go díreach teoranta do cás bonn amháin nó athchúrsach amháin
cás.
Mar sin, sampla de rud éigin le cásanna bonn il
d'fhéadfadh a bheith this-- an Fibonacci ord uimhir.
>> Is féidir leat a thabhairt chun cuimhne ó laethanta scoil tosaigh
go bhfuil an t-ord Fibonacci sainithe cosúil leis this-- is é an chéad eilimint 0.
Is é an dara gné 1.
Tá an dá de na bhfuil ach ag sainmhíniú.
>> Ansin, tá gach gné eile a shainmhínítear mar shuim na n lúide 1 agus n lúide 2.
Mar sin, an tríú eilimint bheadh ​​0 móide 1 Tá 1.
Agus ansin an ceathrú eilimint a bheadh ​​ar an dara gné, 1,
móide an tríú gné, 1.
Agus bheadh ​​2.
Agus mar sin de agus mar sin de.
>> Mar sin, sa chás seo, ní mór dúinn dhá chás bonn.
Má tá n cothrom le 1, ar ais 0.
Má tá n cothrom le 2, ar ais 1.
Seachas sin, ar ais Fibonacci de n lúide 1 móide Fibonacci de n lúide 2.
>> Mar sin tá go cásanna bonn il.
Cad mar gheall ar chásanna Athchúrsach il?
Bhuel, tá rud éigin ar a dtugtar an conjecture Collatz.
Níl mé ag dul a rá, tá a fhios agat cad é go bhfuil,
mar tá sé i ndáiríre ar ár deiridh fadhb le haghaidh an físeán ar leith.
Agus tá sé ar ár fheidhmiú a bheith ag obair ar le chéile.
>> Mar sin, anseo cad an Collatz tuairimíocht is--
feidhm aige maidir le gach slánuimhir dheimhneach.
Agus speculates sé go bhfuil sé i gcónaí agus is féidir a fháil ar ais
go 1 má leanann tú na céimeanna seo.
Má tá n 1, stop.
Táimid agam ar ais go dtí 1 má tá n 1.
>> Seachas sin, dul tríd an próiseas arís ar n roinnt ar 2.
Agus féach an féidir leat a fháil ar ais go dtí 1.
Seachas sin, más rud é go n corr, dul tríd an próiseas seo arís ar 3n móide 1,
nó 3 huaire n móide 1.
Mar sin anseo ní mór dúinn cás bonn amháin.
Má tá n cothrom le 1, stop.
Nach bhfuil muid ag déanamh aon recursion níos mó.
>> Ach ní mór dúinn dhá chás Athchúrsach.
Má tá n fiú, a dhéanann muid recursive amháin cás, ag glaoch n roinnt ar 2.
Má tá n corr, a dhéanann muid difriúil cás Athchúrsach ar 3 huaire n móide 1.
>> Agus mar sin is é an sprioc do físeán seo a ghlacadh ar an dara, sos an físeán,
agus iarracht a dhéanamh agus scríobh seo feidhm athchúrsach Collatz
áit a théann tú i luach n, agus Ríomhann sé cé mhéad bearta
Bíonn a fháil chun 1 má thosaíonn tú ó n agus leanann tú na céimeanna suas thuas.
Má tá n 1, a thógann sé 0 céimeanna.
Seachas sin, tá sé ag dul go dtí ghlacadh céim amháin móide, áfach
go leor céimeanna a thógann sé ar an dá n arna roinnt ar 2 má tá n fiú, nó 3n móide 1
más rud é go n corr.
>> Anois, tá mé a chur suas ar an scáileán anseo cúpla rudaí tástála ar do shon,
cúpla cásanna tástálacha ar do shon, a fheiceáil cad iad na huimhreacha Collatz éagsúla,
agus chomh maith léiriú de na céimeanna sin
Ní mór a bheith imithe tríd ionas gur féidir leat sort féach an bpróiseas seo i ngníomh.
Mar sin, má tá n cothrom le 1, is é Collatz de n 0.
Ní gá duit a dhéanamh rud ar bith a fháil ar ais go dtí an 1.
Go bhfuil tú ann cheana féin.
>> Má tá N 2, a thógann sé céim amháin a fháil go dtí 1.
Tosaíonn tú le 2.
Bhuel, nach bhfuil 2 cothrom le 1.
Mar sin, tá sé ag dul a bheith céim amháin móide áfach, go leor bearta
Bíonn ar n roinnt ar 2.
>> 2 arna roinnt 2 Tá 1.
Mar sin, a thógann sé céim amháin móide, áfach go leor céimeanna a thógann sé ar feadh 1.
1 Bíonn náid céimeanna.
>> Ar feadh 3, mar is féidir leat a fheiceáil, níl go leor le roinnt céimeanna i gceist.
Théann tú ó 3.
Agus ansin a théann tú chuig 10, 5, 16, 8, 4, 2, 1.
Bíonn sé seacht céimeanna a fháil ar ais go dtí an 1.
Agus mar is féidir leat a fheiceáil, níl a lánúin cásanna tástála eile anseo
a thástáil amach do chlár.
Mar sin arís, sos an físeán.
Agus beidh mé ag dul léim ar ais go dtí anois cad é an próiseas iarbhír anseo,
cad é an conjecture.
>> Féach an féidir leat an figiúr amach conas a shainmhíniú Collatz de n
ionas go ríomhann sé cé mhéad céimeanna a thógann sé chun a fháil go dtí an 1.
Mar sin tá súil againn, tá tú ar shos na físeáin agus nach bhfuil tú ag fanacht ach le haghaidh dom
a thabhairt duit an freagra anseo.
Ach má tá tú, go maith, anseo an freagra ar aon nós.
>> Mar sin, tá anseo sainmhíniú féideartha na feidhme Collatz.
Case-- ár mbonn má tá n cothrom le 1, ar ais muid 0.
Ní thógann sé aon céimeanna a fháil ar ais go dtí 1.
>> Seachas sin, tá dhá cases-- Athchúrsach ceann amháin le haghaidh ré-uimhreacha agus ceann do corr.
An bealach a thástáil mé do ré-uimhreacha Is a sheiceáil má ionann n mod 2 0.
Sé seo go bunúsach, arís, ag iarraidh ar an cheist,
má tá tú chun cuimhne is-- cad mod má mé Tá deighilt n 2 nach bhfuil aon chuid?
Bheadh ​​sin ré-uimhir.
>> Agus mar sin má ionann n mod 2 0 Tá Tá tástáil seo ré-uimhir.
Más amhlaidh, ba mhaith liom a thabhairt ar ais 1, mar is é seo cinnte
ag cur céim amháin móide Collatz de is cuma cad líon is leath de dom.
Seachas sin, ba mhaith liom a thabhairt ar ais 1 móide Collatz de 3 huaire n móide 1.
Go raibh an ceann eile céim Athchúrsach go ndéanaimid
D'fhéadfadh a ghlacadh a ríomh ar an Collatz-- ar líon na céimeanna
a thógann sé a fháil ar ais go 1 tugtar uimhir.
Mar sin tá súil againn, sampla seo Thug tú beagán
de blas de nósanna imeachta Athchúrsach.
Súil go dtosnódh, cheapann tú go bhfuil cód a beag níos áille má chuirtear i bhfeidhm
ar, ar bhealach recursive galánta.
Ach fiú amháin más rud é nach, tá recursion a uirlis chumhachtach i ndáiríre mar sin féin.
Agus mar sin tá sé cinnte rud éigin a fháil do cheann timpeall,
toisc go mbainfidh tú in ann a chruthú Cláir deas fionnuar ag baint úsáide as recursion
d'fhéadfadh a bheith ar shlí eile casta a scríobh má tá tú ag baint úsáide as lúba agus atriall.
Tá mé Doug Lloyd.
Is é seo an CS50.