[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.