ZAMYLA: Por kompreni rekursio, vi devas unue kompreni rekursio. Havante rekursio en programo dezajno rimedoj ke vi havas mem-referenca difinoj. Recursive datumstrukturoj, ekzemple, Estas datumstrukturoj ke inkluzivi en iliaj difinoj. Sed hodiaŭ, ni tuj enfokusigi sur rekursiaj funkcioj. 

Memoru ke funkcioj preni enigoj, argumentoj, kaj resendas valoron kiel ilia eligo reprezentita de ĉi diagramo tie. Ni pensu pri la skatolon kiel la korpo de la funkcio, enhavante la aro de instrukcioj kiujn interpretas la enigo kaj provizas eligon. Prenante pli proksiman rigardon interne de la korpo de la funkcio povus malkaŝi alvokojn al aliaj funkcioj tiel. Prenu ĉi simpla funkcio, foo, ke prenas sola kordo kiel enigo kaj impresoj kiom da literoj ke kordoj havas. La funkcio strlen, por korda longeco, estas nomita, kies eliro estas bezonata por la alvoko al printf. 

Nun, kio faras rekursia funkcio specialaj estas, ke li nomas sin. Ni povas reprezenti ĉi rekursiaj nomas per tiu oranĝo sago looping reen al sin. Sed ekzekutante denove volas nur fari alian rekursia alvoko, kaj alia kaj alia. Sed rekursiaj funkcioj ne povas esti malfinio. Ili devas fini iel, aŭ via programo kuros eterne. 

Do ni devas trovi manieron rompi el la rekursiaj vokoj. Ni nomas tiun la baza kazo. Kiam la baza kazo kondiĉo estas renkontiĝis, La funkcio redonas sen fari alia rekursia alvoko. Prenu ĉi funkcion, hi, malplena funkcio kiuj prenas int n kiel enigo. La baza kazo venas unue. Se n estas malpli ol nulo, presi bye kaj revenu Por ĉiuj aliaj kazoj, la funkcio presos hi kaj ekzekuti la rekursia alvoko. Alia alvoko al la funkcio hi kun a decremented eniga valoro. 

Nun, eĉ kvankam ni presi hi, la funkcio ne finiĝas ĝis ni redoni lian revenon tipo, en ĉi tiu kazo malplenon. Do por ĉiu n escepte la baza kazo, tiun funkcion hi redonos hi de n minus 1. Ekde ĉi tiu funkcio estas malplena kvankam, ni ne eksplicite tajpi reveno tie. Ni simple ekzekuti la funkcio. Do nomi hi (3) presos hi kaj ekzekuti hi (2) kiuj ekzekutas hi (1) unu kiuj ekzekutas hi (0), kie la bazo kazo kondiĉo renkontis. Do hi (0) presas bye kaj revenas. 

OK. Do nun ke ni komprenas la bazojn de rekursiaj funkcioj, kiujn ili bezonas almenaŭ unu baza kazo tiel kiel rekursia alvoko, ni pluiru al pli signifa ekzemplo. Kiu ne ĝuste reveni vanigas negrave kion. 

Ni rigardu la faktorialo operacion uzata plej ofte en probablo kalkuloj. Faktorialo de n estas la produto de ĉiu pozitiva entjero malpli ol kaj egalaj al n. Do faktorialo kvin estas 5 horoj 4 horoj 3 fojojn 2 horoj 1 doni 120. Kvar faktorialo estas 4 horoj 3 horoj 2 fojojn 1 doni 24. Kaj la sama regulo validas al ĉiu pozitiva entjero. 

Do kiel povus oni skribi rekursia Funkcio kiu kalkulas la faktorialo de nombro? Nu, ni bezonas por identigi ambaŭ la bazo kazo kaj la rekursia alvoko. La rekursia alvoko estos la sama por ĉiuj kazoj krom la bazo kazo, kio signifas, ke ni devos trovi modelon, kiu donos al ni nia deziratan rezulton. 

Por ĉi tiu ekzemplo, vidi kiel 5 faktorialo engaĝas multiplikante 4 de 3 per 2 per 1 Kaj tio tre sama multipliko Estas trovitaj tie, la difino de 4 faktorialo. Do ni vidas, ke la 5 faktorialo estas nur 5 horoj 4 faktorialo. Nun tiu ĉi ŝablono apliki 4 faktorialo tiel? Jes. Ni vidas ke 4 faktorialo enhavas la multipliko 3 fojojn 2 horoj 1, la tre sama difino kiel 3 faktorialo. Do 4 faktorialo estas egala al 4 fojoj 3 Faktorialo, kaj tiel plu kaj tiel plu, nia mastro bastonoj ĝis 1 faktorialo, kiuj per difino estas egala al 1. 

Estas neniu alia pozitiva entjeroj maldekstre. Do ni havas la skemon por nia rekursia alvoko. n faktorialoj estas egala al n fojoj la faktorialo de n minus 1. Kaj nia bazo kazo? Tio estos nur esti nia difino de 1 faktorialo. 

Do nun ni povas pluiri al skribo kodo por la funkcio. Por la baza kazo, ni havos la kondiĉo n egalas egaluloj 1, kie ni revenos 1. Tiam movanta sur la rekursia alvoko, ni revenos n fojoj la faktorialo de n minus 1. 

Nun ni testi tiun nian. Ni provu faktorialo 4. Per nia funkcio estas egala 4 fojoj faktorialo (3). Faktorialo (3) estas egala al 3 fojoj faktorialo (2). Faktorialo (2) estas egala al 2 fojoj faktorialo (1), kiu denove 1. Faktorialo (2) nun revenas 2 fojoj 1, 2. Faktorialo (3) povas nun revenu 3 fojojn 2, 6. Kaj fine, faktorialo (4) Revenas 4 fojoj 6, 24. 

Se vi renkontis ajna malfacilaĵo kun la rekursia alvoko, ŝajnigi ke la funkcio laboras jam. Kion mi celas per tio, ke vi devus fidi vian rekursiaj alvokoj reveni dekstre valoroj. Ekzemple, se mi scias ke faktorialo (5) egalas 5 fojoj faktorialo (4), mi iros kaj esperas, ke faktorialo (4) donos al mi 24. Pensu pri ĝi kiel variablon, se vi volo, kiel se vi jam difinita faktorialo (4). Do pro ajna faktorialo (n), ĝi estas la produto de n kaj la antaŭan faktorialo. Kaj tion antaŭa faktorialo estas ricevita per vokante faktorialo de n minus 1. 

Nun, ĉu vi povas apliki rekursia funkcio mem. Ŝarĝi vian terminalo, aŭ run.cs50.net, kaj skribi funkcion sumo kiu prenas entjero n kaj redonas la sumo de ĉiuj sinsekva pozitiva entjeroj el n al 1. Mi jam skribis el la sumoj de iu valorojn por helpi al vi nian. Unue, eltrovi la bazo kazo kondiĉo. Tiam, rigardu sumo (5). Ĉu vi povas esprimi ĝin en terminoj de alia sumo? Nun, kio pri sumo (4)? Kiel vi povas esprimi sumo (4) en terminoj de alia sumo? 

Kiam vi havas sumo (5) kaj sumo (4) esprimita en terminoj de aliaj sumoj, vidu se vi povas identigi mastron por sumo (n). Se ne, provu kelkaj aliaj nombroj kaj esprimi siajn sumoj en terminoj de alia numerojn. Per identiganta ŝablonoj por diskreta numerojn, vi bone sur via vojo al identiganta la ŝablono por ĉiu n. 

Rekursio estas vere potenca ilo, do kompreneble ĝi ne estas limigita al matematikaj funkcioj. Rekursio povas uzi tre efike kiam kontraktanta kun arboj ekzemple. Kontrolu la mallonga sur arboj por pli funda revizio, sed por nun memoras ke duuma serĉo arboj, en aparta, estas formitaj de nodoj, ĉiu kun valoro kaj du nodo montriloj. Kutime, tiu estas reprezentita de la patro nodo havanta unu linio notante maldekstren infano nodo kaj unu al la dekstra infano nodo. La strukturo de duuma serĉo arbo pruntas bone al rekursia serĉo. La rekursia alvoko ĉu pasas en la maldekstra aŭ la dekstra nodo, sed pli de tiu en la arbo mallonga. 

Diru vi volas plenumi operacion en ĉiu simpla nodo en duuma arbo. Kiel eble vi iru sur tio? Nu, vi povus skribi rekursia funkcio kiu plenumas la operacio je la patro nodo kaj faras rekursia vokas la saman funkcion, pasante en la maldekstra kaj dekstra infano nodoj. Ekzemple, ĉi tiu funkcio, foo, ke ŝanĝu la valoron de donita vertico kaj ĉiujn ĝiajn infanojn al 1. La baza kazo de nula nodo kaŭzoj la funkcio por reveni, indikante ke estas nenia nodoj lasis en tiu sub-arbo. 

Ni iru tra ĝi. La unua patro estas 13. Ni ŝanĝu la valoron 1, kaj tiam nomita nia funkcio sur la maldekstra tiel kiel la rajto. La funkcio, foo, nomiĝas maldekstre sub-arbo unue, do la maldekstra vertico estos reasignada al 1 kaj foo volo nomi sur tiu nodo de filoj, unue la maldekstran kaj tiam dekstre, kaj tiel plu kaj tiel plu. Kaj diru al ili, ke branĉoj ne havas plu filoj por la sama procezo sekvos por la rajto infanoj ĝis la tuta arbo de la nodoj estas reasignada al 1. 

Kiel vi povas vidi, vi ne estas limigita al nur unu rekursia alvoko. Nur tiom, kiom ricevos la laboron farita. Kio, se vi havis arbon kie ĉiu nodo havis tri filojn, Maldekstra, meza, kaj ĝuste? Kiel vi redaktanton foo? Nu, simplaj. Nur aldonu alian rekursia alvoko kaj Iam en la mezo nodo montrilo. 

Rekursio estas tre potenca kaj ne mencii eleganta, sed gxi povas esti malfacila koncepto je la komenco, tiel estu pacienca kaj prenu vian tempon. Starti kun la baza kazo. Ĝi estas kutime la plej facila al identigi, kaj tiam vi povas labori malantaŭen de tie. Vi scias, ke vi bezonas por atingi viajn bazo kazo, tiel ke forteco doni al vi kelkajn aludojn. Provu esprimi unu specifa kazo en terminoj de aliaj kazoj, aŭ en la sub-aroj. 

Dankon por rigardi ĉi mallonga. Almenaŭ, nun vi povas kompreni ŝercoj kiel ĉi tio. Mia nomo estas Zamyla, kaj ĉi tiu estas cs50. 

Prenu ĉi funkcion, hi, a void funkcio kiu prenas an int n, kiel enigo. La baza kazo venas unue. Se n estas malpli ol 0, presi "Bye" kaj reveno.