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