>> ZAMYLA: anlamaq üçün recursion, siz
ilk recursion başa düşürük.
Proqram dizayn vasitələri recursion olan Siz öz-özünə sened var ki,
anlayışlar.
Recursive data strukturları, məsələn, data strukturları var ki,
özlərini daxildir onların təriflər.
Ancaq bu gün biz diqqət olacaq recursive funksiyaları.
>> , Funksiyaları giriş almaq Xatırladaq ki, arqumentlər və kimi bir dəyər qayıtmaq onların
təmsil output burada bu diagram.
Biz orqanı kimi qutusuna düşünmək lazımdır toplusunu ibarət funksiyası,
Bu şərh edən təlimat Giriş və çıxış təmin edir.
Bədən daxilində yaxından nəzər alaraq funksiyası zənglər aşkar edə bilər
digər funksiyaları həmçinin.
Bu sadə funksiyası, foo edin ki, giriş kimi bir simli edir və
izləri neçə məktublar ki, simli var.
String uzunluğu üçün funksiyası strlen, onun çıxış edir, adlanır
printf zəng üçün tələb olunur.
>> İndi nə recursive funksiyası edir xüsusi özünü çağırır edir.
Biz bu recursive təmsil edə bilər bu narıncı arrow ilə zəng
geri özü üçün loop.
Amma yenə özünü həyata yalnız olacaq başqa recursive zəng etmək, və
başqa, digər.
Amma recursive funksiyaları sonsuz ola bilməz.
Onlar elə başa, və ya sizin proqram əbədi davam edəcək.
>> Beləliklə, biz pozmaq üçün bir yol tapmaq lazımdır recursive zənglər həyata.
Biz baza halda çağırırıq.
Baza halda vəziyyəti görüşüb zaman, funksiyası etmədən qaytarır
başqa recursive zəng.
Bir boşluq funksiyası, hi, bu funksiyası edin ki, giriş kimi bir int n edir.
Ėsas birinci gəlir.
N az sıfır, çap bye və əgər Bütün digər hallarda qayıtmaq
funksiyası hi çap və icra edəcək recursive zəng.
Ilə funksiyası Şueyb üçün bir zəng bir endirildiyi giriş dəyər.
>> İndi biz, hi çap baxmayaraq funksiyası ləğv edəcək biz qədər
onun qaytarılması növü qayıtmaq, Bu halda etibarsız.
Belə ki, hər n baza halda başqa, bu funksiya hi hi qayıdacaqlar
n minus 1.
Bu funksiya olsa etibarsız olduğundan, biz açıq-aydın burada geri yazın deyil.
Biz yalnız funksiyası icra edəcəyik.
Belə ki, hi zəng (3) hi çap və hi (2) (1) bir hi icra edən icra
hi icra (0), burada baza halda vəziyyət görüşüb.
Belə ki, hi (0) bye yazdıran və qaytarır.
>> OK.
Belə ki, indi biz əsasları anlamaq ki, onlar lazımdır ki, recursive funksiyaları,
ən azı bir əsas işi habelə recursive zəng, bir hərəkət edək
daha mənalı nümunəsidir.
Yalnız geri deyil ki, bir nə olursa olsun ləğv.
>> Nin faktöryel bir nəzər salaq əməliyyat ən çox istifadə olunan
ehtimal hesablamaları.
N Faktorial hər məhsuludur daha müsbət tam ədəddir
və n bərabər.
Belə ki, faktöryel beş 5 dəfə 4 dəfə 3 dəfə 2 dəfə 1 120 vermək.
Dörd faktöryel 4 dəfə 3 dəfə 2 dəfə 1 24 vermək.
Və eyni qayda tətbiq edilir hər hansı bir müsbət tam.
>> Belə ki, necə biz recursive yazmaq bilər faktöryel hesablayır ki, funksiyası
Bir sıra?
Yaxşı, biz də müəyyən etmək lazımdır baza halda və recursive zəng.
Recursive zəng eyni olacaq baza istisna olmaqla bütün hallarda
halda, biz lazımdır o deməkdir ki, bizə verəcək bir model tapmaq bizim
istənilən nəticə.
>> Bu, misal üçün, necə 5 faktöryel bax 1-2 3 4 vurulması daxildir
Və ki, çox eyni vurma , burada aşkar
4 Faktorial definition.
Belə ki, biz 5 faktöryel görürük yalnız 5 dəfə 4 faktöryel.
İndi bu model tətbiq etmir 4 eləcə də faktöryel?
Bəli.
Biz 4 faktöryel ehtiva görmək vurma 3 dəfə 2 dəfə 1,
3 Faktorial kimi çox eyni definition.
Belə ki, 4 faktöryel 4 dəfə 3 bərabərdir faktöryel, və s və s bizim
model 1 Faktorial qədər sərvətdən Açıklama 1 bərabərdir.
>> Başqa heç bir müsbət var integers ayrıldı.
Beləliklə, biz üçün model var bizim recursive zəng.
n faktöryel n dəfə bərabərdir Bu n faktöryel minus 1.
Və bizim əsas işi?
Ki, yalnız bizim definition olacaq 1 Faktorial.
>> Belə ki, indi biz yazılı üçün hərəkət edə bilər funksiyası üçün kodu.
Baza halda, biz lazımdır vəziyyəti n bərabərdir 1, bərabərdir yerləşir
biz 1 qayıtmaq lazımdır.
Sonra recursive zəng üzərində hərəkət, biz n dəfə qayıtmaq lazımdır
n faktöryel minus 1.
>> İndi bu bizim test imkan verir.
Nin Faktorial 4 cəhd edək.
Bizim funksiyası Per bərabər var 4 dəfə faktöryel (3).
Faktorial (3) bərabərdir 3 dəfə faktöryel (2).
Faktorial (2) 2 dəfə bərabərdir faktöryel (1), olan 1 qaytarır.
Faktorial (2) indi 2 dəfə 1, 2 qaytarır.
Faktorial (3) indi qayıda bilər 3 dəfə 2, 6.
Və nəhayət, faktöryel (4) 4 dəfə 6, 24 qaytarır.
>> Hər hansı bir çətinlik karşılaşırsanız recursive zəng ilə, iddia
funksiyası artıq işləyir.
Mən bu demək olmalıdır ki, qayıtmaq üçün recursive zənglər etibar
sağ dəyərlər.
Məsələn, mən bilirəm ki, əgər faktöryel (5) 5 dəfə bərabərdir
faktöryel (4), I etibar gedirəm faktöryel (4) mənə 24 verəcək.
Əgər, bir dəyişən kimi düşünün olacaq, siz artıq müəyyən kimi
faktöryel (4).
Belə ki, hər hansı bir faktöryel üçün (n), bu n məhsul və
əvvəlki faktöryel.
Bu əvvəlki faktöryel zəng etməklə əldə olunur
n faktöryel minus 1.
>> Siz həyata keçirilməsi əgər İndi, bax recursive özünüzü fəaliyyət göstərir.
Sizin terminal yük, və ya run.cs50.net, və funksiyası məbləğ yazmaq
ki, bir tam n edir və qaytarır bütün ardıcıl müsbət məbləği
n-1 integers.
Mən bəzi məbləğləri yazdıq sizə yardım etmək dəyərlər bizim.
Birincisi, anlamaq baza halda vəziyyəti.
Sonra məbləğin baxmaq (5).
Siz baxımından bunu ifadə edə bilər başqa məbləğin?
İndi nə məbləğin haqqında (4)?
Necə məbləğ ifadə edə bilər (4) başqa məbləğin baxımından?
>> Siz məbləğ var (5) və məbləği (4) başqa məbləğləri ilə ifadə bax
Bir müəyyən edə bilər məbləğin (n) üçün model.
Əgər bir neçə digər nömrələr cəhd və onların məbləğləri ifadə
başqa nömrələri şərtləri.
Diskret üçün nümunələri müəyyən nömrələri, sizin yol yaxşı deyilik
bir n üçün model müəyyən.
>> Recursion həqiqətən güclü alət var, belə əlbəttə ki, bu məhdud deyil
riyazi funksiyaları.
Recursion çox səmərəli istifadə edilə bilər Məsələn ağacları ilə məşğul olan zaman.
Bir ağac haqqında qısa oldu daha ətraflı baxış, lakin indi
ki, ikili axtarış ağac geri Xüsusilə, hər qovşaqlarının edilir
bir dəyəri və iki node göstəricilər ilə.
Adətən, bu ilə təmsil olunur bir line işarə olan valideyn node
sol uşaq node və bir sağ uşaq node.
Ikili axtarış strukturu ağac də özü verir
bir recursive axtarış.
Recursive zəng ya keçir sol və ya sağ node, lakin daha çox
ağac Qisa ildə ki.
>> Siz əməliyyat istəyirəm demək bir ikili ağac hər bir node.
Necə ki, haqqında getmək bilər?
Yaxşı, bir recursive yazmaq bilər Əməliyyatı reallaşdıran funksiyası
valideyn node və recursive edir Eyni funksiyası zəng,
sol keçən və sağ uşaq qovşaqlarının.
Məsələn, bu funksiya, foo ki, Bu bir node dəyəri və dəyişikliklər
1 onun uşaqlar bütün.
Bir null node səbəbləri əsas işi funksiyası ifadə qayıtmaq
bir qovşaqlarının var ki ki, sub-ağac ayrıldı.
>> Bunun vasitəsilə gəzmək edək.
İlk valideyn 13.
Biz dəyəri 1 dəyişdirmək, və sonra zəng Bizim sol funksiyası, habelə
hüququ kimi.
Funksiyası, foo, sol adlanır ilk sub-ağac, belə ki, sol node
1 və foo adına edəcək ki node uşaqlar adlanır,
ilk sol və sonra sağ, və s və s.
Və filialları yoxdur ki, onlara bir daha uşaq belə ki, eyni proses
sağ uşaqlar üçün davam edəcək bütün ağac qovşaqlarının qədər
1 dəyişdirilmişdir.
>> Gördüyünüz kimi, siz məhdud deyil yalnız bir recursive zəng.
Iş aparılır almaq kimi bir çox.
Bir ağac nə əgər hər bir node üç övladı var idi,
Sol, orta, və sağ?
Necə foo redaktə olardı?
Yaxşı, sadə.
Yalnız başqa recursive zəng əlavə və orta node göstərici keçir.
>> Recursion çox güclü və edir zərif qeyd, ancaq bir ola bilər
ilk çətin anlayış, belə olacaq xəstə və vaxt.
Baza işi ilə başlayın.
Bu adətən müəyyən etmək asan deyil, və sonra işləyə bilər
geri oradan.
Siz olmaq lazımdır bilirik sizin baza halda, belə ki, hünəri
bir neçə göstərişlər verir.
Müəyyən bir işi ifadə etmək üçün cəhd edin digər hallarda şərtləri, və ya sub-dəstləri.
>> Bu qısa izləmək üçün təşəkkür edirik.
Ən azı, indi bilərsiniz bu kimi zarafatlar anlamaq.
My name Zamyla və bu CS50 edir.
>> Hi, bu funksiyası edin, bir edir ki, boşluq funksiyası
bir int, n, giriş kimi.
Ėsas birinci gəlir.
N az 0, çap əgər "Bye" və qaytarılması.