ZAMYLA: Për të kuptuar recursion, ju duhet së pari të kuptojnë recursion. Duke recursion në mjetet e programit të projektimit që ju keni vetë-referencial përkufizime. Strukturat e të dhënave gjithkund rekursive, për shembull, janë strukturat e të dhënave që përfshijnë veten në përkufizimet e tyre. Por sot, ne do të përqëndrohet mbi funksionet gjithkund rekursive. 

Kujtojnë se funksionet marrë inpute, argumente, dhe të kthehet një vlerë e tyre si Prodhimi përfaqësuar nga ky diagram këtu. Ne do të mendojnë kutisë si organ i funksioni, që përmban tërësinë e udhëzimet që interpretojnë input dhe të sigurojë një prodhim. Duke marrë një vështrim më të afërt brenda trupit të funksion mund të zbulojë thirrjet për funksione të tjera si. Merrni këtë funksion të thjeshtë, foo, që merr një varg të vetëm si input dhe printime sa letra që ka string. Strlen funksion, për gjatësi string, quhet, prodhimi i të cilit është e nevojshme për thirrjen në printf. 

Tani, ajo që e bën një funksion gjithkund rekursive veçantë është se ai e quan veten. Ne mund të përfaqësojnë këtë recursive telefononi me këtë ngjyrë e shigjeta looping përsëri në vetvete. Por ekzekutimin veten përsëri vetëm do të bëjë një tjetër thirrje rekursive, dhe një tjetër dhe një tjetër. Por funksionet gjithkund rekursive nuk mund të jetë i pafund. Ata kanë për t'i dhënë fund disi, ose juaj Programi do të kandidojë përgjithmonë. 

Pra, ne duhet të gjejnë një mënyrë për të thyer nga thirrjet gjithkund rekursive. Ne e quajmë këtë rast bazë. Kur gjendja rastit bazë është plotësuar, funksion të kthimit pa bërë një tjetër thirrje rekursive. Merrni këtë funksion, hi, një funksion i pavlefshëm që merr një int n si input. Rastit bazë vjen e para. Nëse n është më pak se zero, bye shtypura dhe kthehen Për të gjitha rastet e tjera, funksion do të shtypura hi dhe ekzekutuar thirrje rekursive. Një tjetër thirrje të funksionit hi me një vlerë decremented input. 

Tani, edhe pse kemi shkruar hi, funksion nuk do të përfundojë deri ne kthehen llojin e vet të kthimit, në këtë rast pavlefshme. Kështu që për çdo n përveç rastit bazë, ky funksion hi do të kthehet hi i N minus 1. Që nga ky funksion është i pavlefshëm edhe pse, ne nuk do të shkruani në mënyrë të qartë kthimin këtu. Ne do të ekzekutojë vetëm funksionin. Pra, duke e quajtur hi (3) do të shtypura hi dhe ekzekutojë hi (2) e cila kryen hi (1) nje cila kryen hi (0), ku kusht rastit bazë është plotësuar. Pra hi (0) printon bye dhe të kthimit. 

OK. Pra, tani që ne e kuptojmë bazat e funksionet gjithkund rekursive, që ata kanë nevojë të paktën një rast të bazë si dhe një thirrje rekursive, le të lëvizin për në një Shembulli më kuptimplotë. Një që nuk ka vetëm të kthehet pavlefshme pa marrë parasysh çfarë. 

Le të bëjmë një vështrim në faktoriale Operacioni më të përdorura në Llogaritjet e probabilitetit. Faktoriali e n eshte produkti i çdo integer pozitiv pak se dhe barabartë me n. Pesë Pra faktoriale është 5 herë 4 herë 3 herë 2 herë 1 për të dhënë 120. Katër faktoriale është 4 herë 3 herë 2 herë 1 për të dhënë 24. Dhe e njëjta rregull vlen në çdo numër i plotë pozitiv. 

Pra, si mund të kemi shkruar një recursive funksion që llogarit faktoriale e një numri? E pra, ne do të duhet për të identifikuar të dy rastit bazë dhe thirrja rekursive. Thirrja recursive do të jetë e njëjtë për të gjitha rastet me përjashtim të bazës rasti, që do të thotë se ne do të duhet të të gjetur një model që do të na japë tonë rezultati i dëshiruar. 

Për këtë shembull, të shohim se si 5 faktoriale përfshin shumëzuar me 4 nga 3 me 2 me 1 Dhe kjo shumë e njëjtë shumëzimit është gjetur këtu, Përkufizimi i 4 faktoriale. Pra, ne shohim se 5 faktoriale është vetëm 5 herë 4 faktorial. Tani ka të bëjë ky model 4 Faktoriali si? Po. Ne shohim se 4 faktoriale përmban shumëzimit 3 herë 2 herë 1, shumë e njëjtë si përkufizim 3 faktoriale. SO 4 faktoriale është e barabartë me 4 herë 3 faktorial, dhe kështu me radhë e kështu me radhë tonë model i qëndron deri më 1 faktoriale, e cila sipas definicionit është e barabartë me 1. 

Nuk ka asnjë pozitiv të tjera integers majtë. Pra, ne kemi model për Thirrja jonë recursive. n është e barabartë tek faktorial herë n faktorial i n minus 1. Dhe rasti ynë bazë? Kjo do të jetë vetëm përkufizimi ynë e 1 faktorial. 

Deri tani ne mund të lëvizin për shkrim formuar për funksionin. Për rastin bazë, ne do të kemi Gjendja n është e barabartë është e barabartë me 1, ku ne do të kthehemi me 1. Pastaj lëviz mbi thirrjes rekursive, ne do të kthehemi herë n faktorial i n minus 1. 

Tani le të testuar këtë tona. Le të përpiqemi faktoriale 4. Per funksionin tonë është e barabartë në 4 herë faktorial (3). Faktoriali (3) është e barabartë me 3 herë faktoriale (2). Faktoriali (2) është i barabartë me 2 herë faktorial (1), e cila jep 1. Faktoriali (2) tani kthen 2 herë 1, 2. Faktorial (3) tani mund të kthehen 3 herë 2, 6. Dhe së fundi, faktoriale (4) kthen 4 herë 6, 24. 

Nëse ju jeni ndeshi në ndonjë vështirësi me thirrjen gjithkund rekursive, pretendon se funksion punon tashmë. Çfarë dua të them me këtë është se ju duhet besim thirrjet tuaja gjithkund rekursive për t'u kthyer vlerat e duhura. Për shembull, në qoftë se unë e di se faktorial (5) është e barabartë me 5 herë faktorial (4), Unë do të besoj se faktorial (4) do të më jepni 24. Mendoni se si një variabël, në qoftë se ju do, si në qoftë se ju tashmë e definuar faktorial (4). Pra, për çdo faktoriale (n), është e Produkti i N dhe faktorial mëparshme. Dhe kjo faktoriale e mëparshme është marrë duke e quajtur faktorial i n minus 1. 

Tani, të shohim nëse mund të zbatojë një recursive funksionojnë veten. Load up terminali tuaj, ose run.cs50.net, dhe shkruani një shumë funksion që merr një numër të plotë n dhe kthimit Shuma e të gjitha radhazi pozitive numra te plote nga N me 1. Unë e kam shkruar nga shumat e disa Vlerat për t'ju ndihmuar tonë. Së pari, gjej kusht rastit bazë. Pastaj, shikoni në shumën (5). A mund të shprehin atë në terma e një tjetër shumës? Tani, ajo që për shumë (4)? Si mund të shprehë shumë (4) në drejtim të një tjetër shumës? 

Pasi të keni shumë (5) dhe shuma (4) shprehur në terma të shumave të tjera, shih në qoftë se ju mund të identifikojë një model për shumën (n). Nëse jo, provoni një numër pak të tjera dhe shprehin shuma e tyre në kushtet e një tjetër numrave. Duke identifikuar modele për diskrete numrat, ju jeni edhe në rrugën tuaj për identifikuar model për çdo n. 

Recursion është një mjet me të vërtetë i fuqishëm, kështu që sigurisht nuk është i kufizuar në Funksionet matematikore. Recursion mund të përdoret shumë në mënyrë efektive kur kanë të bëjnë me pemë për shembull. Kontrollo të shkurtër në pemë për një më shumë rishikim i plotë, por tani për tani kujtojnë se pemët e kërkimit binare, në veçanti, janë të përbërë nga nyjet, çdo me vlerë dhe dy nyjeve pointers. Zakonisht, kjo është përfaqësuar nga nyja prind që ka një duke treguar linjë në nyjen e majtë të fëmijëve dhe një në nyjen e duhur të fëmijëve. Struktura e një kërkimi binar pemë jep edhe vetë në një kërkim gjithkund rekursive. Thirrja recursive ose kalon në majtas ose nyjen e drejtë, por më shumë e që në pemë të shkurtër. 

Thonë se ju doni të kryer një operacion në çdo nyje të vetëm në një pemë binare. Si mund të ju shkoni në lidhje me këtë? E pra, ju mund të shkruani një recursive funksion që kryen operacionin në nyjen prind dhe e bën një recursive thirrje për të njëjtin funksion, duke kaluar në të majtë dhe nyjet e drejtë të fëmijëve. Për shembull, ky funksion, foo, që ndryshon vlerën e një nyje të caktuar dhe gjithë fëmijëve me 1. Rasti Baza e një shkaqeve null nyjeve funksion të kthehen, duke treguar se nuk ka ndonjë nyje mbetur në këtë nën-pemë. 

Le të ecin nëpër atë. Prind i parë është 13. Ne ndryshoni vlerën në 1, dhe pastaj të telefononi funksion ynë në të majtë, si dhe si e drejta. Funksioni, foo, quhet në të majtë nën-pemë e parë, kështu që nyja e majtë do të caktohen për të 1 dhe foo do të thirret mbi fëmijët se Nyja-së, pari majtë dhe pastaj të drejtë, dhe kështu me radhë e kështu me radhë. Dhe tregoni atyre se degët nuk kanë më fëmijë aq i njëjti proces do të vazhdojë për fëmijët drejtë deri në nyje gjithë pemën janë ricaktuar në 1. 

Siç mund ta shikoni, ju nuk janë të kufizuara të vetëm një telefonatë recursive. Ashtu të gjithë ata që do të marrë punë të bërë. Çfarë ndodh nëse keni pasur një pemë ku çdo nyje kishte tre fëmijë, Majtas, të mesëm, dhe të drejtë? Si do ta redaktoni foo? E pra, e thjeshtë. Vetëm të shtoni një tjetër thirrje rekursive dhe të kalojë në treguesin nyjen e mesme. 

Recursion është shumë i fuqishëm dhe jo të përmend elegante, por ajo mund të jetë një koncept i vështirë në fillim, në mënyrë të pacientit dhe të marrë kohën tuaj. Filloni me rastin bazë. Kjo është zakonisht më e lehtë për të identifikuar, dhe pastaj ju mund të punojnë prapa nga atje. Ju e dini që ju duhet për të arritur tuaj rastit bazë, në mënyrë që fuqia ju jap disa lë të kuptohet. Mundohuni për të shprehur një rast të veçantë në Kushtet e raste të tjera, ose në nën-grupe. 

Faleminderit për të shikuar këtë short. Në shumë pak, tani ju mund të kuptojnë shaka si kjo. Emri im është Zamyla, dhe kjo është CS50. 

Merrni këtë funksion, hi, një Funksioni i pavlefshëm që merr një int, n, si hyrje. Rastit bazë vjen e para. Nëse n është më pak se 0, print "Bye" dhe kthim.