1 00:00:00,000 --> 00:00:07,800 2 00:00:07,800 --> 00:00:10,190 >> ZAMYLA: D'fhonn tuiscint a fháil ar athchúrsáil, ní mór duit 3 00:00:10,190 --> 00:00:13,820 an chéad a thuiscint athchúrsáil. 4 00:00:13,820 --> 00:00:17,280 Ag athchúrsáil i modhanna dearadh cláir go bhfuil tú féin-referential 5 00:00:17,280 --> 00:00:18,570 sainmhínithe. 6 00:00:18,570 --> 00:00:21,520 Struchtúir sonraí recursive, mar shampla, Tá struchtúir sonraí a 7 00:00:21,520 --> 00:00:23,990 Áirítear iad féin i n-sainmhínithe. 8 00:00:23,990 --> 00:00:27,160 Ach lá atá inniu ann, táimid ag dul chun díriú ar feidhmeanna Athchúrsach. 9 00:00:27,160 --> 00:00:31,160 >> Thabhairt chun cuimhne go nglacfaidh feidhmeanna ionchur, argóintí, agus luach mar filleadh ar a gcuid 10 00:00:31,160 --> 00:00:34,480 aschur arna ionadú ag an léaráid anseo. 11 00:00:34,480 --> 00:00:38,060 Beidh muid smaoineamh ar an bhosca mar an comhlacht ar an fheidhm, ina bhfuil an tacar 12 00:00:38,060 --> 00:00:42,340 treoracha a léirmhíniú ionchur agus aschur a chur ar fáil. 13 00:00:42,340 --> 00:00:45,660 Ag tabhairt le breathnú níos dlúithe taobh istigh an comhlacht ar d'fhéadfaí an fheidhm glaonna nochtann le 14 00:00:45,660 --> 00:00:47,430 feidhmeanna eile chomh maith. 15 00:00:47,430 --> 00:00:51,300 Tóg an fheidhm simplí, foo, go Bíonn ar shraith amháin mar ionchur agus 16 00:00:51,300 --> 00:00:54,630 priontaí cé mhéad litreacha Tá an teaghrán. 17 00:00:54,630 --> 00:00:58,490 An strlen fheidhm, le haghaidh fad teaghrán, ar a dtugtar, a bhfuil aschur is 18 00:00:58,490 --> 00:01:01,890 ag teastáil le haghaidh an glaoch chun printf. 19 00:01:01,890 --> 00:01:05,770 >> Anois, cad a dhéanann feidhm athchúrsach Is speisialta a iarrann sé é féin. 20 00:01:05,770 --> 00:01:09,610 Is féidir linn a léiriú seo athchúrsach glaoch ar leis an arrow oráiste 21 00:01:09,610 --> 00:01:11,360 looping ar ais go dtí féin. 22 00:01:11,360 --> 00:01:15,630 Ach forghníomhaitheach féin arís beidh ach dhéanamh glaoch athchúrsach eile, agus 23 00:01:15,630 --> 00:01:17,150 eile agus eile. 24 00:01:17,150 --> 00:01:19,100 Ach na feidhmeanna Athchúrsach Ní féidir a bheith gan teorainn. 25 00:01:19,100 --> 00:01:23,490 Tá siad go deireadh ar bhealach, nó do Beidh an clár a reáchtáil go deo. 26 00:01:23,490 --> 00:01:27,680 >> Mar sin, ní mór dúinn a fháil ar bhealach a bhriseadh as na glaonna recursive. 27 00:01:27,680 --> 00:01:29,900 Tugaimid seo an cás bonn. 28 00:01:29,900 --> 00:01:33,570 Nuair a bhíonn an coinníoll gcás bonn le chéile, Filleann an fheidhm a dhéanamh gan 29 00:01:33,570 --> 00:01:34,950 glaoch athchúrsach eile. 30 00:01:34,950 --> 00:01:39,610 Tóg an fheidhm seo, Hi, feidhm neamhní go nglacann ina slánuimhir n chomh ionchur. 31 00:01:39,610 --> 00:01:41,260 Tagann an cás bonn ar dtús. 32 00:01:41,260 --> 00:01:46,220 Má tá níos lú ná náid n, fo cló agus ar ais Do gach cás eile, an 33 00:01:46,220 --> 00:01:49,400 Beidh feidhm phriontáil Hi agus a fhorghníomhú an glaoch athchúrsach. 34 00:01:49,400 --> 00:01:53,600 Glao eile ar an Hi feidhm le luach ionchur decremented. 35 00:01:53,600 --> 00:01:56,790 >> Anois, cé a phriontáil againn Hi, an Ní bheidh feidhm deireadh go dtí go againn 36 00:01:56,790 --> 00:02:00,370 ar ais dá chineál ar ais, sa chás seo ar neamhní. 37 00:02:00,370 --> 00:02:04,830 Mar sin, le haghaidh gach n eile seachas an cháis bonn, Beidh an fheidhm seo Hi Hi ais 38 00:02:04,830 --> 00:02:06,890 n lúide 1. 39 00:02:06,890 --> 00:02:10,050 Ós rud é go bhfuil an fheidhm seo ar neamhní áfach, táimid ag Ní bheidh cineál sainráite ar ais anseo. 40 00:02:10,050 --> 00:02:12,000 Beidh muid a fhorghníomhú ach an fheidhm. 41 00:02:12,000 --> 00:02:16,960 Mar sin, ag iarraidh Hi (3) Beidh phriontáil Hi agus fhorghníomhú Hi (2) a fhorghníomhú Hi (1) amháin 42 00:02:16,960 --> 00:02:20,560 a fhorghníomhú Hi (0), i gcás ina an Tá coinníoll gcás bonn le chéile. 43 00:02:20,560 --> 00:02:24,100 Mar sin, Hi (0) priontaí fo agus tuairisceáin. 44 00:02:24,100 --> 00:02:24,990 >> OK. 45 00:02:24,990 --> 00:02:28,690 Mar sin anois go dtuigimid an Basics of feidhmeanna Athchúrsach, gur gá dóibh 46 00:02:28,690 --> 00:02:32,730 gcás bonn amháin ar a laghad chomh maith le glao athchúrsach, a ligean ar bogadh ar aghaidh go dtí 47 00:02:32,730 --> 00:02:34,120 Mar shampla níos mó brí. 48 00:02:34,120 --> 00:02:37,830 Amháin nach ar ais ach neamhní is cuma cén. 49 00:02:37,830 --> 00:02:41,340 >> A ligean ar ghlacadh le breathnú ar an factorial oibríocht is coitianta a úsáidtear i 50 00:02:41,340 --> 00:02:43,660 ríomhaireachtaí dóchúlacht. 51 00:02:43,660 --> 00:02:48,120 Is factorial n an táirge ar gach slánuimhir dheimhneach níos lú ná 52 00:02:48,120 --> 00:02:49,400 agus cothrom le n. 53 00:02:49,400 --> 00:02:56,731 Tá cúig Mar sin, factorial 5 huaire 4 huaire 3 huaire 2 uair 1 a thabhairt 120. 54 00:02:56,731 --> 00:03:01,400 Tá ceithre factorial 4 huaire 3 huaire 2 uair 1 a thabhairt 24. 55 00:03:01,400 --> 00:03:04,910 Agus feidhm ag an riail chéanna d'aon slánuimhir dheimhneach. 56 00:03:04,910 --> 00:03:08,670 >> Mar sin, conas a d'fhéadfadh muid a scríobh athchúrsach fheidhm a ríomh, ríomhann an factorial 57 00:03:08,670 --> 00:03:09,960 roinnt? 58 00:03:09,960 --> 00:03:14,700 Bhuel, beidh orainn gá a aithint idir an bunchás agus an glaoch athchúrsach. 59 00:03:14,700 --> 00:03:18,250 Beidh an glao athchúrsach mar an gcéanna do gach cás ach amháin i gcás an bonn 60 00:03:18,250 --> 00:03:21,420 cás, rud a chiallaíonn go beidh orainn a patrún a aimsiú a thabhairt dúinn ár n- 61 00:03:21,420 --> 00:03:23,350 toradh inmhianaithe. 62 00:03:23,350 --> 00:03:30,270 >> Mar shampla, seo, a fheiceáil conas 5 factorial Baineann iolrú faoi 4 3 2 1 faoi 63 00:03:30,270 --> 00:03:33,010 Agus go iolrú-céanna Tá fáil anseo, an 64 00:03:33,010 --> 00:03:35,430 sainmhíniú 4 factorial. 65 00:03:35,430 --> 00:03:39,810 Mar sin, feicimid go bhfuil 5 factorial ach 5 uaire 4 factorial. 66 00:03:39,810 --> 00:03:43,360 Anois a dhéanann an patrún feidhm ag go 4 factorial chomh maith? 67 00:03:43,360 --> 00:03:44,280 Tá. 68 00:03:44,280 --> 00:03:49,120 Feicimid go bhfuil 4 factorial an iolrú 3 huaire 2 uair 1, an 69 00:03:49,120 --> 00:03:51,590 sainmhíniú an-céanna le 3 factorial. 70 00:03:51,590 --> 00:03:56,950 Mar sin, tá 4 factorial cothrom le 4 huaire 3 factorial, agus mar sin de agus mar sin de ár 71 00:03:56,950 --> 00:04:02,170 bataí patrún go dtí an 1 factorial, a de réir sainmhínithe, atá cothrom le 1. 72 00:04:02,170 --> 00:04:04,950 >> Níl aon dearfacha eile slánuimhreacha ar chlé. 73 00:04:04,950 --> 00:04:07,870 Mar sin, ní mór dúinn an patrún do ár glaoch athchúrsach. 74 00:04:07,870 --> 00:04:13,260 n Tá factorial cothrom le amanna n an factorial n lúide 1. 75 00:04:13,260 --> 00:04:14,370 Agus ár gcás bonn? 76 00:04:14,370 --> 00:04:17,370 Beidh sé sin a bheith díreach ár sainmhíniú de 1 factorial. 77 00:04:17,370 --> 00:04:19,995 >> Mar sin, anois is féidir linn bogadh ar aghaidh go dtí scríbhinn cód le haghaidh an fheidhm. 78 00:04:19,995 --> 00:04:24,110 Maidir leis an gcás bonn, beidh orainn an coinníoll n ionann ionann 1, i gcás ina 79 00:04:24,110 --> 00:04:25,780 beidh muid ar ais 1. 80 00:04:25,780 --> 00:04:29,280 Ansin, ag bogadh isteach ar an glaoch athchúrsach, beidh muid ar ais amanna n na 81 00:04:29,280 --> 00:04:32,180 factorial n lúide 1. 82 00:04:32,180 --> 00:04:33,590 >> Anois, a ligean ar thástáil ár. 83 00:04:33,590 --> 00:04:35,900 A ligean ar iarracht factorial 4. 84 00:04:35,900 --> 00:04:39,420 Per ár fheidhm is comhionann go dtí 4 uaire factorial (3). 85 00:04:39,420 --> 00:04:43,040 Factorial (3) is comhionann le 3 huaire factorial (2). 86 00:04:43,040 --> 00:04:48,700 Factorial (2) is comhionann le 2 uair factorial (1), atá ar ais 1. 87 00:04:48,700 --> 00:04:52,490 Factorial (2) Filleann anois 2 uair 1, 2. 88 00:04:52,490 --> 00:04:55,960 Factorial (3) Is féidir le filleadh anois 3 huaire 2, 6. 89 00:04:55,960 --> 00:05:02,490 Agus ar deireadh, factorial (4) Filleann 4 huaire 6, 24. 90 00:05:02,490 --> 00:05:06,780 >> Má tá tú ag dréim le haon deacracht leis an glaoch athchúrsach, ligean orthu go 91 00:05:06,780 --> 00:05:09,660 Oibríonn an fheidhm cheana féin. 92 00:05:09,660 --> 00:05:13,450 Cad a chiallaíonn mé leis seo is gur chóir duit muinín do chuid glaonna recursive a thabhairt ar ais 93 00:05:13,450 --> 00:05:15,100 na luachanna ceart. 94 00:05:15,100 --> 00:05:18,960 Mar shampla, má tá a fhios agam go factorial (5) is ionann agus 5 uaire 95 00:05:18,960 --> 00:05:24,870 factorial (4), tá mé ag dul ar iontaoibh factorial (4) a thabhairt dom 24. 96 00:05:24,870 --> 00:05:28,510 Cuimhnigh ar sé mar athróg, má tá tú Beidh, amhail is dá mba a shainmhínítear agat cheana féin 97 00:05:28,510 --> 00:05:30,070 factorial (4). 98 00:05:30,070 --> 00:05:33,850 Mar sin, le haghaidh aon factorial (n), tá sé an táirge n agus 99 00:05:33,850 --> 00:05:35,360 an factorial roimhe sin. 100 00:05:35,360 --> 00:05:38,130 Agus seo factorial roimhe fhaightear trí ghlaoch 101 00:05:38,130 --> 00:05:41,330 factorial n lúide 1. 102 00:05:41,330 --> 00:05:45,130 >> Anois, féach an féidir leat a chur i bhfeidhm Athchúrsach feidhmiú duit féin. 103 00:05:45,130 --> 00:05:50,490 Luchtaigh suas do teirminéil, nó run.cs50.net, agus suim feidhm a scríobh 104 00:05:50,490 --> 00:05:54,770 go nglacann slánuimhir n agus tuairisceáin an suim de gach dearfach i ndiaidh a chéile 105 00:05:54,770 --> 00:05:57,490 slánuimhreacha ó n 1. 106 00:05:57,490 --> 00:06:01,000 Scríobh mé amach na suimeanna roinnt Luachanna chun cabhrú leat ár. 107 00:06:01,000 --> 00:06:04,030 Gcéad dul síos, figiúr amach an coinníoll gcás bonn. 108 00:06:04,030 --> 00:06:06,170 Ansin, breathnú ar an tsuim (5). 109 00:06:06,170 --> 00:06:09,270 An féidir leat a chur in iúl dó i dtéarmaí den tsuim eile? 110 00:06:09,270 --> 00:06:11,290 Anois, cad faoi tsuim (4)? 111 00:06:11,290 --> 00:06:15,630 Conas is féidir leat a chur in iúl tsuim (4) i dtéarmaí suim eile? 112 00:06:15,630 --> 00:06:19,655 >> Nuair a bheidh tú suim (5) agus tsuim (4) arna shloinneadh i dtéarmaí suimeanna eile, féach ar 113 00:06:19,655 --> 00:06:22,970 más féidir leat a aithint ar patrún do shuim (n). 114 00:06:22,970 --> 00:06:26,190 Más rud é nach, déan iarracht cúpla uimhreacha eile agus a n-suimeanna i iúl 115 00:06:26,190 --> 00:06:28,410 dtéarmaí uimhreacha eile. 116 00:06:28,410 --> 00:06:31,930 Trí patrúin a aithint le haghaidh scoite uimhreacha, tá tú go maith ar do bhealach a 117 00:06:31,930 --> 00:06:34,320 aithint an patrún d'aon n. 118 00:06:34,320 --> 00:06:38,040 >> Recursion tá uirlis chumhachtach i ndáiríre, mar sin ar ndóigh, nach bhfuil sé teoranta dóibh 119 00:06:38,040 --> 00:06:39,820 feidhmeanna matamaiticiúla. 120 00:06:39,820 --> 00:06:44,040 Is féidir athchúrsáil a úsáid go han-éifeachtach agus iad ag déileáil le crainn mar shampla. 121 00:06:44,040 --> 00:06:47,210 Amharc ar an gearr ar chrainn le haghaidh athbhreithniú níos críochnúla, ach do anois 122 00:06:47,210 --> 00:06:51,140 thabhairt chun cuimhne go crainn cuardaigh dénártha, i go háirithe, atá déanta suas de nóid, gach 123 00:06:51,140 --> 00:06:53,820 le luach agus dhá threo nód. 124 00:06:53,820 --> 00:06:57,270 De ghnáth, is é seo ionadaíocht ag an nód tuismitheoir a bhfuil dírithe líne amháin 125 00:06:57,270 --> 00:07:01,870 leis an nód leanbh ar chlé agus ceann leis an nód leanbh ceart. 126 00:07:01,870 --> 00:07:04,510 An struchtúr cuardach dénártha lends crann féin go maith 127 00:07:04,510 --> 00:07:05,940 le cuardach athchúrsach. 128 00:07:05,940 --> 00:07:09,730 An glao athchúrsach Gabhann ceachtar sa chlé nó an nód ceart, ach tá níos mó 129 00:07:09,730 --> 00:07:10,950 sin sa ghearrthéarma gcrann. 130 00:07:10,950 --> 00:07:15,690 >> Abair gur mhaith leat a dhéanamh ar oibríocht ar gach nód amháin i gcrann dénártha. 131 00:07:15,690 --> 00:07:17,410 Cén chaoi a bhféadfaí tú ag dul faoi sin? 132 00:07:17,410 --> 00:07:20,600 Bhuel, d'fhéadfaí tú a scríobh athchúrsach feidhm go ndéanann an oibríocht 133 00:07:20,600 --> 00:07:24,450 ar an nód tuismitheoir agus a dhéanann athchúrsach cuairt a thabhairt ar an fheidhm chéanna, 134 00:07:24,450 --> 00:07:27,630 dul i chlé agus nóid leanbh ceart. 135 00:07:27,630 --> 00:07:31,650 Mar shampla, an fheidhm seo, foo, go athruithe ar an luach a bhaineann le nód a tugadh agus 136 00:07:31,650 --> 00:07:33,830 gach ceann dá chuid leanaí chun 1. 137 00:07:33,830 --> 00:07:37,400 An cás bonn de cúiseanna nód null an fheidhm a thabhairt ar ais, rud a léiríonn 138 00:07:37,400 --> 00:07:41,290 nach bhfuil aon nóid fágtha san fho-crann. 139 00:07:41,290 --> 00:07:42,620 >> A ligean ar siúl tríd. 140 00:07:42,620 --> 00:07:44,340 Is é an chéad tuismitheoir 13. 141 00:07:44,340 --> 00:07:47,930 Athrú againn ar an luach a 1, agus ansin glaoch ar ár bhfeidhm ar an taobh clé chomh maith 142 00:07:47,930 --> 00:07:49,600 leis an gceart. 143 00:07:49,600 --> 00:07:53,910 Is é an fheidhm, foo, ar a dtugtar ar thaobh na láimhe clé an chéad fho-crann, mar sin an nód chlé 144 00:07:53,910 --> 00:07:57,730 Beidh a athshannadh go dtí 1 agus foo beidh ar a dtugtar ar na páistí go nód ar, 145 00:07:57,730 --> 00:08:01,900 ar dtús leis an chlé agus ansin an ceart, agus mar sin de agus mar sin de. 146 00:08:01,900 --> 00:08:05,630 Agus insint dóibh nach bhfuil brainsí ar bith níos mó páistí sin an próiseas céanna 147 00:08:05,630 --> 00:08:09,700 leanfaidh sé ar aghaidh do na páistí ceart go dtí go bhfuil nóid an crann ar fad ar 148 00:08:09,700 --> 00:08:11,430 athshannadh 1. 149 00:08:11,430 --> 00:08:15,390 >> Mar is féidir leat a fheiceáil, nach bhfuil tú teoranta chun amháin glaoch athchúrsach. 150 00:08:15,390 --> 00:08:17,930 Díreach mar go mbeidh go leor mar a fháil ar an post a dhéanamh. 151 00:08:17,930 --> 00:08:21,200 Cad a tharlaíonn má bhí tú crann i gcás gach Bhí triúr leanaí nód, 152 00:08:21,200 --> 00:08:23,100 Clé, lár, agus an ceart? 153 00:08:23,100 --> 00:08:24,886 Conas a bheadh ​​leat in eagar foo? 154 00:08:24,886 --> 00:08:25,860 Bhuel, simplí. 155 00:08:25,860 --> 00:08:30,250 Just a cuir glaoch athchúrsach eile agus pas a fháil sa pointeoir nód lár. 156 00:08:30,250 --> 00:08:34,549 >> Tá recursion an-chumhachtach agus gan trácht galánta, ach is féidir é a bheith ina 157 00:08:34,549 --> 00:08:38,010 coincheap deacair ar dtús, mar sin a bheith othar agus a ghlacadh do chuid ama. 158 00:08:38,010 --> 00:08:39,370 Tosaigh leis an gcás bonn. 159 00:08:39,370 --> 00:08:42,650 Tá sé de ghnáth an éasca a aithint, agus ansin is féidir leat a bheith ag obair 160 00:08:42,650 --> 00:08:43,830 ar gcúl ó ann. 161 00:08:43,830 --> 00:08:46,190 Tá a fhios agat is gá duit a bhaint amach do gcás bonn, ionas go d'fhéadfadh 162 00:08:46,190 --> 00:08:47,760 a thabhairt duit cúpla leideanna. 163 00:08:47,760 --> 00:08:53,120 Bain triail as a chur in iúl i gcás ceann amháin acu téarmaí gcásanna eile, nó i bhfo-Leagann. 164 00:08:53,120 --> 00:08:54,700 >> Go raibh maith agat chun breathnú ar seo gearr. 165 00:08:54,700 --> 00:08:58,920 Ar a laghad, anois is féidir leat scéalta grinn mar seo a thuiscint. 166 00:08:58,920 --> 00:09:01,250 Is é mo ainm Zamyla, agus tá sé seo cs50. 167 00:09:01,250 --> 00:09:04,306 168 00:09:04,306 --> 00:09:07,170 >> Tóg an fheidhm seo, Hi, ina feidhm neamhní a thógann 169 00:09:07,170 --> 00:09:09,212 ina slánuimhir, n, mar ionchur. 170 00:09:09,212 --> 00:09:11,020 Tagann an cás bonn ar dtús. 171 00:09:11,020 --> 00:09:14,240 Má tá níos lú ná 0 n, cló "Beannacht" agus ar ais. 172 00:09:14,240 --> 00:09:15,490