1 00:00:00,000 --> 00:00:07,800 2 00:00:07,800 --> 00:00:10,190 >> ZAMYLA: Upang maunawaan recursion, dapat mo 3 00:00:10,190 --> 00:00:13,820 Nauunawaan unang recursion. 4 00:00:13,820 --> 00:00:17,280 Ang pagkakaroon ng recursion sa programa disenyo paraan na ikaw ay may self-referential 5 00:00:17,280 --> 00:00:18,570 kahulugan. 6 00:00:18,570 --> 00:00:21,520 Recursive mga istraktura ng data, halimbawa, ang mga istraktura ng data na 7 00:00:21,520 --> 00:00:23,990 isama ang kanilang mga sarili sa kanilang mga kahulugan. 8 00:00:23,990 --> 00:00:27,160 Ngunit ngayon, kami ay pagpunta upang tumutok sa recursive function. 9 00:00:27,160 --> 00:00:31,160 >> Isipin na mga pag-andar tumagal ng input, argumento, at nagbabalik ng halaga bilang kanilang 10 00:00:31,160 --> 00:00:34,480 output kinakatawan ng ito diagram dito. 11 00:00:34,480 --> 00:00:38,060 Susubukan naming isipin ang kahon sa bilang ng katawan ng ang pag-andar, na naglalaman ng mga hanay ng mga 12 00:00:38,060 --> 00:00:42,340 tagubilin na bigyang-kahulugan ang input at magbigay ng isang output. 13 00:00:42,340 --> 00:00:45,660 Pagkuha ng isang mas malapitan naming tingnan sa loob ng katawan ng ang function ay maaaring magbunyag ng mga tawag sa 14 00:00:45,660 --> 00:00:47,430 iba pang mga function pati na rin. 15 00:00:47,430 --> 00:00:51,300 Sagutan ang simpleng function, foo, na tumatagal ng isang solong string na ito bilang input at 16 00:00:51,300 --> 00:00:54,630 mga kopya kung gaano karaming mga titik na string ay may. 17 00:00:54,630 --> 00:00:58,490 Ang function na strlen, para sa haba string, ay tinatawag na, na ang output ay 18 00:00:58,490 --> 00:01:01,890 kinakailangan para sa mga tawag sa printf. 19 00:01:01,890 --> 00:01:05,770 >> Ngayon, kung bakit ang isang recursive function na espesyal ay tumutulong ito sa mga tawag mismo. 20 00:01:05,770 --> 00:01:09,610 Maaari naming kumatawan ito recursive tumawag sa orange na arrow 21 00:01:09,610 --> 00:01:11,360 looping bumalik sa sarili nito. 22 00:01:11,360 --> 00:01:15,630 Ngunit execute mismo muli habilin lamang gumawa ng isa pang recursive tawag, at 23 00:01:15,630 --> 00:01:17,150 isa at isa pa. 24 00:01:17,150 --> 00:01:19,100 Ngunit recursive function Hindi maaaring walang katapusan. 25 00:01:19,100 --> 00:01:23,490 Ang mga ito ay upang wakasan sa paano pa man, o ang iyong programa ay tatakbo nang permanente. 26 00:01:23,490 --> 00:01:27,680 >> Kaya kailangan namin upang makahanap ng isang paraan upang masira sa labas ng recursive tawag. 27 00:01:27,680 --> 00:01:29,900 Tinatawag namin ito ang batayang kaso. 28 00:01:29,900 --> 00:01:33,570 Kapag ang kundisyon base kaso ay nakilala, ang function ay nagbalik ng hindi ginagawang 29 00:01:33,570 --> 00:01:34,950 isa pang recursive tawag. 30 00:01:34,950 --> 00:01:39,610 Dalhin ito function, hi, isang walang bisa function na na tumatagal ng isang int n bilang input. 31 00:01:39,610 --> 00:01:41,260 Ang unang base kaso ay. 32 00:01:41,260 --> 00:01:46,220 Kung n ay mas mababa sa zero, i-print at hindi importanteng bagay bumalik Para sa lahat ng iba pang mga kaso, ang 33 00:01:46,220 --> 00:01:49,400 function na ay i-print hi at isakatuparan ang recursive tawag. 34 00:01:49,400 --> 00:01:53,600 Ang isa pang tawag sa pagpapaandar na hi may isang decremented halaga ng pag-input. 35 00:01:53,600 --> 00:01:56,790 >> Ngayon, kahit na i-print namin hi, ang function na ay hindi wakasan hanggang namin 36 00:01:56,790 --> 00:02:00,370 bumalik uri nito pagbalik, kung sakaling walang bisa ito. 37 00:02:00,370 --> 00:02:04,830 Kaya para sa bawat n bukod sa base ng kaso, ito function na hi ay magbabalik hi 38 00:02:04,830 --> 00:02:06,890 ng n minus 1. 39 00:02:06,890 --> 00:02:10,050 Dahil ito function na ay walang bisa bagaman, namin hindi tahasang type balik dito. 40 00:02:10,050 --> 00:02:12,000 Susubukan naming lamang maisagawa ang pag-andar. 41 00:02:12,000 --> 00:02:16,960 Kaya sa pagtawag hi (3) ay i-print at hi isakatuparan hi (2) na executes hi (1) isa 42 00:02:16,960 --> 00:02:20,560 na executes hi (0), kung saan ang kondisyon base kaso ay natugunan. 43 00:02:20,560 --> 00:02:24,100 Kaya hi (0) prints hindi importanteng bagay at babalik. 44 00:02:24,100 --> 00:02:24,990 >> OK. 45 00:02:24,990 --> 00:02:28,690 Kaya ngayon na naiintindihan namin ang mga pangunahing kaalaman sa recursive function, na kailangan nila 46 00:02:28,690 --> 00:02:32,730 hindi bababa sa isang base ng kaso pati na rin ang isang recursive tawag, ni lumipat sa isang ipaalam 47 00:02:32,730 --> 00:02:34,120 mas makabuluhang halimbawa. 48 00:02:34,120 --> 00:02:37,830 Ang isa na hindi nagbabalik lamang walang silbi ang kahit na ano. 49 00:02:37,830 --> 00:02:41,340 >> Hayaan ang kumuha ng isang pagtingin sa mga factorial ginamit operasyon pinakakaraniwang sa 50 00:02:41,340 --> 00:02:43,660 bagay na maaaring mangyari kalkulasyon. 51 00:02:43,660 --> 00:02:48,120 Factorial ng n ay ang produkto ng bawat positibong integer na mas mababa sa 52 00:02:48,120 --> 00:02:49,400 at pantay-pantay sa n. 53 00:02:49,400 --> 00:02:56,731 Kaya factorial limang 5 beses 4 na beses 3 beses 2 beses 1 upang bigyan 120. 54 00:02:56,731 --> 00:03:01,400 Apat na factorial ay 4 na beses 3 beses 2 beses 1 upang bigyan ang 24. 55 00:03:01,400 --> 00:03:04,910 At sa parehong panuntunan Nalalapat sa anumang positibong integer. 56 00:03:04,910 --> 00:03:08,670 >> Kaya kung paano maaari naming magsulat ng isang recursive function na kinakalkula ang factorial 57 00:03:08,670 --> 00:03:09,960 ng isang numero? 58 00:03:09,960 --> 00:03:14,700 Well, kailangan nating kilalanin ang parehong base kaso at ang recursive tawag. 59 00:03:14,700 --> 00:03:18,250 Ang recursive tawag ay ang parehong para sa lahat ng mga kaso maliban sa ang batayang 60 00:03:18,250 --> 00:03:21,420 kaso, na nangangahulugan na kakailanganin naming makahanap ng isang pattern na ay magbibigay sa amin ang aming 61 00:03:21,420 --> 00:03:23,350 ninanais na resulta. 62 00:03:23,350 --> 00:03:30,270 >> Para sa halimbawang ito, tingnan kung paano 5 factorial ay nagsasangkot ng pag-multiply 4 sa pamamagitan ng 3 sa pamamagitan ng 2 sa pamamagitan ng 1 63 00:03:30,270 --> 00:03:33,010 At na napaka-parehong pagpaparami ay nakita dito, ang 64 00:03:33,010 --> 00:03:35,430 kahulugan ng 4 factorial. 65 00:03:35,430 --> 00:03:39,810 Kaya nakita namin na 5 factorial ay lamang 5 beses 4 factorial. 66 00:03:39,810 --> 00:03:43,360 Ngayon ay ilapat ang pattern na ito 4 na factorial pati na rin? 67 00:03:43,360 --> 00:03:44,280 Oo. 68 00:03:44,280 --> 00:03:49,120 Nakita namin na 4 factorial ay naglalaman ng pagpaparami 3 beses 2 beses 1, ang 69 00:03:49,120 --> 00:03:51,590 napaka parehong kahulugan bilang 3 factorial. 70 00:03:51,590 --> 00:03:56,950 Kaya 4 factorial ay katumbas ng 4 na beses 3 factorial, at iba pa at iba pa ang aming 71 00:03:56,950 --> 00:04:02,170 pattern sticks hanggang 1 factorial, na sa pamamagitan ng kahulugan ay katumbas ng 1. 72 00:04:02,170 --> 00:04:04,950 >> Walang iba pang positibong iniwan integer. 73 00:04:04,950 --> 00:04:07,870 Kaya mayroon kaming mga pattern para sa ang aming recursive tawag. 74 00:04:07,870 --> 00:04:13,260 n factorial ay katumbas ng n beses ang factorial ng n minus 1. 75 00:04:13,260 --> 00:04:14,370 At ang aming base kaso? 76 00:04:14,370 --> 00:04:17,370 Iyon makikita lamang maging sa aming kahulugan ng 1 factorial. 77 00:04:17,370 --> 00:04:19,995 >> Kaya ngayon maaari naming magpatuloy sa pagsusulat code para sa mga function. 78 00:04:19,995 --> 00:04:24,110 Para sa mga base ng kaso, kakailanganin naming ang kondisyon n katumbas ay katumbas ng 1, kung saan 79 00:04:24,110 --> 00:04:25,780 babalik kami 1. 80 00:04:25,780 --> 00:04:29,280 Pagkatapos ay gumagalaw papunta sa recursive tawag, babalik kami n beses ang 81 00:04:29,280 --> 00:04:32,180 factorial ng n minus 1. 82 00:04:32,180 --> 00:04:33,590 >> Ngayon Subukan natin ito ang aming ipaalam. 83 00:04:33,590 --> 00:04:35,900 Subukan ni factorial 4 Hayaan. 84 00:04:35,900 --> 00:04:39,420 Alinsunod sa aming function na ito ay katumbas ng 4 na beses factorial (3). 85 00:04:39,420 --> 00:04:43,040 Factorial (3) ay katumbas ng 3 beses factorial (2). 86 00:04:43,040 --> 00:04:48,700 Factorial (2) ay katumbas ng 2 beses factorial (1), na nagbabalik 1. 87 00:04:48,700 --> 00:04:52,490 Factorial (2) ay nagbabalik ngayon 2 beses 1, 2. 88 00:04:52,490 --> 00:04:55,960 Factorial (3) ay maaari na ngayong magbalik 3 beses 2, 6. 89 00:04:55,960 --> 00:05:02,490 At sa wakas, factorial (4) Ibinabalik ng 4 na beses 6, 24. 90 00:05:02,490 --> 00:05:06,780 >> Kung ikaw ay nakakaranas ng anumang paghihirap may recursive tawag, magpanggap na 91 00:05:06,780 --> 00:05:09,660 ang function ay gumagana na. 92 00:05:09,660 --> 00:05:13,450 Ano ang ibig sabihin ko sa pamamagitan ng ito ay na dapat mong pinagkakatiwalaan ang iyong recursive tawag upang bumalik 93 00:05:13,450 --> 00:05:15,100 ang tamang halaga. 94 00:05:15,100 --> 00:05:18,960 Halimbawa, kung alam ko na factorial (5) ay katumbas ng 5 beses 95 00:05:18,960 --> 00:05:24,870 factorial (4), ako pagpunta sa pinagkakatiwalaan na factorial (4) ay magbibigay sa akin 24. 96 00:05:24,870 --> 00:05:28,510 Isipin ito bilang isang variable, kung ikaw pita, bilang kung tinukoy mo na 97 00:05:28,510 --> 00:05:30,070 factorial (4). 98 00:05:30,070 --> 00:05:33,850 Kaya para sa anumang mga factorial (n), ito ay ang produkto ng n at 99 00:05:33,850 --> 00:05:35,360 ang nakaraang factorial. 100 00:05:35,360 --> 00:05:38,130 At ito nakaraang factorial ay nakuha sa pamamagitan ng pagtawag 101 00:05:38,130 --> 00:05:41,330 factorial ng n minus 1. 102 00:05:41,330 --> 00:05:45,130 >> Ngayon, tingnan kung maaari mong ipatupad ang recursive function na ang iyong sarili. 103 00:05:45,130 --> 00:05:50,490 Mag-load up ang iyong mga terminal, o run.cs50.net, at magsulat ng isang function sum 104 00:05:50,490 --> 00:05:54,770 na kumukuha ng isang integer n at nagbabalik ang kabuuan ng lahat ng mga magkakasunod na positibo 105 00:05:54,770 --> 00:05:57,490 integer mula sa n 1. 106 00:05:57,490 --> 00:06:01,000 Na naisulat ko ang sums ng ilang mga halaga upang makatulong sa iyo na ang aming. 107 00:06:01,000 --> 00:06:04,030 Una, malaman kung ang kondisyon base kaso. 108 00:06:04,030 --> 00:06:06,170 Pagkatapos, tumingin sa sum (5). 109 00:06:06,170 --> 00:06:09,270 Maaari mong ipahayag ito sa tuntunin ng isa pang sum? 110 00:06:09,270 --> 00:06:11,290 Ngayon, kung ano ang tungkol sa sum (4)? 111 00:06:11,290 --> 00:06:15,630 Paano mo maaaring ipahayag sum (4) sa mga tuntunin ng isa pang sum? 112 00:06:15,630 --> 00:06:19,655 >> Sa sandaling mayroon ka sum (5) at sum (4) ipinahayag sa mga tuntunin ng iba pang mga sums, tingnan ang 113 00:06:19,655 --> 00:06:22,970 kung maaari mong kilalanin ang isang pattern para sa sum (n). 114 00:06:22,970 --> 00:06:26,190 Kung hindi, subukan ang ilang iba pang mga numero ng at ipahayag ang kanilang sums sa 115 00:06:26,190 --> 00:06:28,410 mga tuntunin ng isa pang numero. 116 00:06:28,410 --> 00:06:31,930 Sa pamamagitan ng pagtukoy ng mga pattern para sa hiwalay numero, ikaw ay mahusay sa iyong paraan upang 117 00:06:31,930 --> 00:06:34,320 pagkikilala ng mga pattern para sa anumang n. 118 00:06:34,320 --> 00:06:38,040 >> Recursion ang isang talagang malakas na tool na, kaya siyempre hindi ito limitado sa 119 00:06:38,040 --> 00:06:39,820 mga function sa matematika. 120 00:06:39,820 --> 00:06:44,040 Recursion ay maaaring gamitin napaka-epektibo kapag pagharap sa mga puno halimbawa. 121 00:06:44,040 --> 00:06:47,210 Tingnan ang maikling sa mga puno para sa isang higit pang masinsinang pagsusuri, ngunit sa ngayon 122 00:06:47,210 --> 00:06:51,140 isipin na binary paghahanap puno, sa partikular, ay binubuo ng mga node, ang bawat isa 123 00:06:51,140 --> 00:06:53,820 may halaga at dalawang mga payo node. 124 00:06:53,820 --> 00:06:57,270 Karaniwan, ito ay kinakatawan ng mga node magulang pagkakaroon ng isang linya pagturo 125 00:06:57,270 --> 00:07:01,870 sa kaliwa bata node at isa sa kanan bata node. 126 00:07:01,870 --> 00:07:04,510 Ang istraktura ng isang binary paghahanap puno lends mismo na rin 127 00:07:04,510 --> 00:07:05,940 sa isang recursive paghahanap. 128 00:07:05,940 --> 00:07:09,730 Ang recursive tawag alinman sa mga pagpasa sa kaliwa o kanan na node, ngunit higit pa 129 00:07:09,730 --> 00:07:10,950 ng na sa tree maikli. 130 00:07:10,950 --> 00:07:15,690 >> Sabihin nating nais mong magsagawa ng operasyon sa bawat solong node sa isang binary tree. 131 00:07:15,690 --> 00:07:17,410 Paano maaari kang pumunta tungkol sa na? 132 00:07:17,410 --> 00:07:20,600 Well, maaari mong magsulat ng isang recursive function na gumaganap ang operasyon 133 00:07:20,600 --> 00:07:24,450 sa magulang na node at gumagawa ng isang recursive tumawag sa parehong pag-andar, 134 00:07:24,450 --> 00:07:27,630 pagpasa sa kaliwa at karapatan nodes bata. 135 00:07:27,630 --> 00:07:31,650 Halimbawa, ito function, foo, na nagbabago ang halaga ng isang ibinigay na node at 136 00:07:31,650 --> 00:07:33,830 lahat ng kanyang mga anak na 1. 137 00:07:33,830 --> 00:07:37,400 Ang batayang kaso ng isang null node sanhi ang pag-andar upang bumalik, na nagpapahiwatig 138 00:07:37,400 --> 00:07:41,290 na walang anumang mga nodes naiwan sa mga sub-puno na. 139 00:07:41,290 --> 00:07:42,620 >> Ni maglakad sa pamamagitan nito Hayaang. 140 00:07:42,620 --> 00:07:44,340 Ang unang magulang ay 13. 141 00:07:44,340 --> 00:07:47,930 Baguhin namin ang halaga sa 1, at pagkatapos ay tumawag sa ang aming pag-andar sa kaliwa pati na rin 142 00:07:47,930 --> 00:07:49,600 bilang sa kanan. 143 00:07:49,600 --> 00:07:53,910 Ang function, foo, ay tinatawag na sa kaliwa sub-puno unang, kaya kaliwa node 144 00:07:53,910 --> 00:07:57,730 ay reassigned sa 1 at foo habilin tawagin sa mga bata na node ni, 145 00:07:57,730 --> 00:08:01,900 unang kaliwa at pagkatapos ay ang karapatan, at iba pa at iba pa. 146 00:08:01,900 --> 00:08:05,630 At sabihin sa kanila na sangay walang anumang higit pang mga bata kaya ang parehong proseso 147 00:08:05,630 --> 00:08:09,700 ay patuloy para sa tamang mga bata hanggang sa node ang buong punong kahoy ay 148 00:08:09,700 --> 00:08:11,430 reassigned upang 1. 149 00:08:11,430 --> 00:08:15,390 >> Tulad ng iyong nakikita, hindi mo ay limitado sa isa lang recursive tawag. 150 00:08:15,390 --> 00:08:17,930 Tulad ng maraming mga bilang ay makakuha ng trabaho tapos na. 151 00:08:17,930 --> 00:08:21,200 Paano kung nagkaroon ka ng isang puno kung saan ang bawat na node ay may tatlong mga bata, 152 00:08:21,200 --> 00:08:23,100 Kaliwa, gitna, at tama? 153 00:08:23,100 --> 00:08:24,886 Paano mo ire-edit foo? 154 00:08:24,886 --> 00:08:25,860 Well, simple. 155 00:08:25,860 --> 00:08:30,250 Magdagdag lamang ng isa pang recursive tawag at pumasa sa gitna node pointer. 156 00:08:30,250 --> 00:08:34,549 >> Recursion ay napakalakas at hindi sa banggitin eleganteng, subalit maaari itong maging isang 157 00:08:34,549 --> 00:08:38,010 mahirap konsepto sa una, kaya maging pasyente at dalhin ang iyong oras. 158 00:08:38,010 --> 00:08:39,370 Magsimula sa base ng kaso. 159 00:08:39,370 --> 00:08:42,650 Ito ay karaniwang ang pinakamadaling upang kilalanin, at pagkatapos ay maaari kang magtrabaho 160 00:08:42,650 --> 00:08:43,830 paurong mula doon. 161 00:08:43,830 --> 00:08:46,190 Alam mo na kailangan mo upang maabot ang iyong base kaso, nang sa gayon ay maaaring 162 00:08:46,190 --> 00:08:47,760 magbibigay sa iyo ng ilang mga pahiwatig. 163 00:08:47,760 --> 00:08:53,120 Subukan upang ipahayag ang isang tiyak na kaso sa mga tuntunin ng iba pang mga kaso, o sa mga sub-set. 164 00:08:53,120 --> 00:08:54,700 >> Salamat para sa panonood ang maikling. 165 00:08:54,700 --> 00:08:58,920 Sa pinakadulo hindi bababa sa, ngayon ay maaari mo Nauunawaan joke na katulad nito. 166 00:08:58,920 --> 00:09:01,250 Ang pangalan ko ay Zamyla, at ito ay cs50. 167 00:09:01,250 --> 00:09:04,306 168 00:09:04,306 --> 00:09:07,170 >> Dalhin ito function, hi, isang walang bisa function na tumatagal 169 00:09:07,170 --> 00:09:09,212 isang int, n, bilang input. 170 00:09:09,212 --> 00:09:11,020 Ang unang base kaso ay. 171 00:09:11,020 --> 00:09:14,240 Kung n Mas mababa sa 0, naka-print "Hindi importanteng bagay" at pagbalik. 172 00:09:14,240 --> 00:09:15,490