[MUSIC PLAYING] 

DOUG LLOYD: Siz yəqin ki, hesab edirəm ki, code yalnız bir tapşırıq yerinə yetirmək üçün istifadə olunur. Siz onu yazmaq. Bu bir şey yoxdur. Yəni, bu, olduqca çox var. 

Siz tərtib edir. Siz proqram run. Siz getmək iyi. 

Lakin iman və ya, əgər Siz uzun müddət kod Siz, həqiqətən, görmək üçün gəlmək bilər gözəl bir şey kimi kodu. Bu problem həll edir çox maraqlı bir şəkildə, və ya, həqiqətən, yalnız bir şey var görünür yolu haqqında səliqəli. Siz laughing ola bilər Mənə, ancaq bu doğru deyil. Və recursion bir yoldur sort bu fikir almaq üçün gözəl, zərif görünüşlü kodu. Bu yolla problemləri həll ki, , görüntüləmək üçün asan, maraqlı və təəccüblü qısa. 

yol recursion işləri bir recursive funksiyası var çağırır funksiyası kimi müəyyən edilir özü icra hissəsi kimi. Ki, bir az qəribə görünə bilər və biz bir az görürsünüz bu bir anda necə haqqında. Ancaq yenə də, bu recursive prosedurları var belə zərif olacaq onlar olacaq, çünki olmadan bu problemi həll etmək üçün Bütün bu digər funksiyaları olan və ya bu uzun loops. Siz bu recursive ki, görürsünüz prosedurları belə qısa baxmaq üçün gedir. Onlar həqiqətən etmək üçün gedir Sizin code daha çox gözəl baxmaq. 

Mən sizə bir nümunə verim Bu necə bir recursive proseduru müəyyən edilə bilər. Bu ilə tanış değilseniz belə illər əvvəl math sinif bir şey var deyirlər adətən faktöryel funksiyası, bir ünlem kimi qeydi olan bütün müsbət tam ədədlər üzərində müəyyən edilir. Və yol ki, n faktöryel hesablanır Siz bütün çoxaltmaq edilir daha nömrələri az və ya bərabər n together-- üçün bütün integers az və ya birlikdə n bərabər. 

Belə ki, 5 faktöryel 5 dəfə 4 dəfə 3 dəfə 2 dəfə 1. And 4 faktöryel 4 dəfə 3 dəfə 2 dəfə 1 və s. Siz fikir almaq. 

Proqramçılar kimi, biz deyil n, ünlem istifadə edin. Beləliklə, biz faktöryel müəyyən edəcəyik n fakt kimi fəaliyyət göstərir. Və biz yaratmaq üçün faktöryel istifadə edəcəyik bir problemin recursive həlli. Mən tapa bilər edirəm Bu daha çox vizual ki, iterativ artıq müraciət Bu versiyası olan biz də bir anda nəzər lazımdır. 

Belə ki, burada bir neçə facts-- pun intended-- haqqında factorial-- faktöryel funksiyası. Dediyim kimi 1 faktöryel, 1. 2 faktöryel 2 dəfə 1. 3 faktöryel 3 dəfə 2 belə dəfə 1, və. Biz artıq 4 və 5 bəhs etdi. 

Amma bu baxaraq, bu doğru deyil? 2 faktöryel deyil, yalnız 2 dəfə 1 faktöryel? Mən demək, 1 faktöryel 1. Belə ki, niyə biz yalnız demək olmaz ki, 2 faktöryel 2 dəfə 1-ci ildən, Bu, həqiqətən, yalnız 2 dəfə var 1 faktöryel? 

Və sonra, ki, fikir uzanan 3 faktöryel deyil yalnız 3 dəfə 2 faktöryel? Və 4 faktöryel 4 dəfə belə 3 və faktöryel? Əslində, faktöryel hər hansı bir sayı yalnız bilərsiniz cür əgər ifadə əbədi bu həyata keçirir. Biz növ ümumiləşdirmək bilər faktöryel problem bu kimi n dəfə n minus 1 faktöryel. Bu n dəfə məhsul var bütün nömrələri mənə az. 

Bu fikir, bu Problemin ümumiləşdirilməsi, Bizə recursively üçün imkan verir faktöryel funksiyası müəyyən edir. Bir funksiyası müəyyən zaman recursively var Bunun bir hissəsi olmaq üçün lazım olan iki şey. Siz bir şey deyilən lazımdır baza halda, hansı, siz onu tetiklemek zaman, recursive prosesi dayanacaq. 

Əks halda, bir funksiyası çağırır özü siz imagine-- bilər əbədi davam edə bilər. Function funksiyasını çağırır funksiyası zənglər çağırır funksiyası funksiyası çağırır. Bir yol yoxsa , proqram dayandırmaq üçün səmərəli vurulmuş olunacaq sonsuz loop edir. Bu, nəticədə qəza edəcək Bu yaddaş tökülmək lazımdır, çünki. Amma bu nöqtədə başqa var. 

Biz dayandırmaq üçün bəzi digər yol lazımdır proqram şaqqıltılı başqa şeylər Yeməyini bir proqramdır, çünki yəqin ki, gözəl və ya zərif deyil. Və belə ki, biz bu əsas işi çağırırıq. Bu sadə həll edir Nöqtə bir problem meydana gələn recursive prosesi. Belə ki, bir hissəsi var bir recursive funksiyası. 

ikinci hissəsi recursive haldır. Bu harada recursion edir həqiqətən keçiriləcək. Bu harada funksiyası özü zəng edəcək. 

Məhz özünü zəng deyil Eyni şəkildə bu adlanırdı. Bu cüzi variasiya olacaq ki, bu problem edir bir ufacık az kiçik həll etməyə çalışırıq. Amma ümumiyyətlə dollar keçir həlli hissəsini həll xətti aşağı fərqli zəng. 

Bu görünüşü hansı Burada əsas halda kimi? Hansı kimi bu görünür bir bir problem üçün sadə həll? Biz factorials bir dəstə var, və davam edə bilər belə Us 6, 7, 8, 9, 10, və gedir. 

Amma kimi bu görünür bir yaxşı hal baza halda olmaq. Bu, çox sadə həll edir. Biz xüsusi bir şey yoxdur. 

1 faktöryel yalnız 1-dir. Biz heç nə yoxdur vurma bütün. Gedirik əgər kimi görünür cəhd və bu problemi həll etmək, və biz dayandırmaq lazımdır haradasa Recursion, biz yəqin ki, dayandırmaq istəyirəm biz 1 almaq zaman. Biz bundan əvvəl dayandırmaq istəmirəm. 

Biz müəyyən edirik Belə ki Bizim faktöryel funksiyası, Burada bir skelet üçün var biz bunu necə. Biz o iki şey plug lazımdır baza halda və recursive halda. Baza halda nədir? N 1 bərabər deyil, qayıtmaq 1 var ki həqiqətən sadə problem həll etsin. 

1 faktöryel 1. Bu 1 dəfə bir şey var. Bu, sadəcə 1 var. Bu, çox asan faktdır. Və belə ki, bizim əsas işi ola bilər. Biz bu 1 keçdi almaq funksiyası, biz yalnız 1 qayıtmaq lazımdır. 

Recursive nədir hal yəqin ki, kimi baxmaq? Hər sayı üçün 1 Bundan başqa, model nədir? Yaxşı, biz qəbul edirsinizsə n faktöryel, bu n dəfə n faktöryel minus 1. 

Biz 3 faktöryel alaraq edirsinizsə, Bu, 3 minus 1 3 dəfə faktöryel və ya 2. Və biz deyilik əgər başqa, 1 baxaraq qaytarılması n dəfə n minus 1 faktöryel. Bu olduqca sadə. 

Və az olan naminə təmiz və kodu daha zərif, bilirik ki, biz bir-line loops varsa və ya bir-line şərti filialları, Biz bütün xilas edə bilərsiniz onların ətrafında qıvrım aşırma. Beləliklə, biz bu bu birləşdirmək olar. Bu eyni var bu kimi funksionallıq. 

Mən yalnız buruq üz alaraq alıram yalnız bir xətt var, çünki, aşırma həmin şərti filial daxilində. Belə ki, bu eyni davranırlar. N 1 bərabər deyil, 1 qayıtmaq. Əks halda n dəfə qayıtmaq n minus 1 faktöryel. Belə ki, biz kiçik problem edirik. N 5 kimi başlayır, biz olacaq 4 5 dəfə faktöryel qayıtmaq. Və biz danışmaq zaman bir dəqiqə görürsünüz başqa video zəng yığını haqqında biz haqqında danışmaq biz öyrənmək lazımdır yığını zəng məhz bu prosesi işləri niyə. 

Amma 5 isə faktöryel deyir 5 dəfə faktöryel 4 qayıtmaq və 4 yaxşı, OK, demək gedir, geri 4 dəfə 3 faktöryel. Gördüyünüz kimi, biz istəyirik sort 1-yaxınlaşır. Biz yaxın əldə edirik və ki, baza halda yaxın. 

Və biz baza halda hit bir dəfə, əvvəlki funksiyaları bütün onlar aradığınız cavab var. 2 faktöryel qaytarılması deyirdi 2 dəfə 1 faktöryel. Yaxşı, 1 yekunları 1 faktöryel. Faktorial Belə ki zəng 2, 2 dəfə 1 qayıda bilər və faktöryel ki, geri vermək Ki, nəticə gözləyir 3. 

Və sonra hesablamaq olar onun nəticəsində 3 dəfə 2, 6 və 4 faktöryel geri verir. Və yenə, biz var zəng yığını video bu bir az təsvir olunur İndi deyirəm daha çox. Lakin bu deyil. Bu tək həll edir bir sıra faktöryel hesablanması. 

Bu kod yalnız dörd xətləri var. Bu doğru, olduqca sərin var? Bu sexy növü var. 

Belə ki, ümumiyyətlə, lakin həmişə bir recursive funksiyası bir bir loop əvəz edə bilməz qeyri-recursive funksiyası. Belə ki, burada, yan-yana, iterativ var faktöryel funksiyası versiyası. Bu hesablamaq, həm də eyni şey. 

Onlar həm n faktöryel hesablamaq. sol version bunu recursion istifadə edir. sağ version bunu iteration istifadə edir. 

Və bildiriş, biz elan var tam məhsul dəyişən. Və sonra biz loop. Belə ki, uzun n kimi, daha çox 0 n ki, məhsul vurulması saxlamaq qədər n decrementing biz məhsul hesablamaq. Belə ki, bu iki funksiyaları, yenə, eyni şey. Amma onlar bunu etməyin tam eyni şəkildə. 

İndi, bu mümkündür daha çox bazası cinayət işinə və ya daha çox recursive halda, asılı olaraq nə sizin funksiyası etməyə çalışır. Siz mütləq yalnız məhdud deyil bir baza halda və ya bir recursive halda. Bir şey belə bir nümunə Çox bazası hallarda ola bilər şeylərdir Fibonacci sayı ardıcıllığı. 

Siz geri bilər ibtidai məktəb gün Fibonacci ardıcıllığı müəyyən edilir ki, Bu kimi ilk element 0. İkinci element 1. O həm də yalnız müəyyən olunur. 

Sonra hər element müəyyən edilir n minus 1 və n minus 2 cəmi kimi. Üçüncü element So 0 plus 1 1 olacaq. Və sonra dördüncü element İkinci element, 1 olacaq, plus üçüncü element, 1. Və 2 olardı. Və s və s. 

Belə ki, bu halda, biz iki baza hallarda var. N 1 bərabər deyil, 0 qayıtmaq. N 2 bərabər olduqda, 1 qayıtmaq. Əks halda, n Fibonacci qayıtmaq minus 1 plus n minus 2 Fibonacci. 

Belə ki, bir çox baza hallarda var. Nə çox recursive barədə? Yaxşı, bir şey var Collatz zənn çağırıb. Mən demək fikrində deyiləm Siz ki, nə Bu, həqiqətən, bizim son çünki bu video üçün problem. Və bu, bizim həyata var birlikdə işləmək üçün. 

Belə ki, burada nə Collatz zənn is-- hər müsbət tam tətbiq edilir. Və bu ki, speculates həmişə mümkün geri almaq üçün 1 bu adımları əgər. N 1 deyil, dayandırmaq. N 1 əgər biz 1 geri var. 

Əks halda, bu keçir proses yenidən n 2 bölünür. Siz 1 geri ala bilərsiniz, əgər baxın. N tək Əks təqdirdə, keçmək daha 3n plus 1-də bu proses, və ya 3 dəfə n plus 1. Belə ki, burada biz bir baza halda var. N 1 bərabər deyil, dayandırmaq. Biz bir daha recursion məşğul deyilik. 

Amma biz iki recursive hallarda var. N hətta varsa, biz bir recursive etmək halda, n 2 bölünür zəng. N tək deyil, fərqli bir etmək 3 dəfə n plus 1-də recursive halda. 

Və bu video üçün məqsədi , ikinci almaq video fasilə, və cəhd və bu yazmaq recursive funksiyası Collatz harada, dəyəri n keçir və Bu necə bir çox addımlar hesablayır Siz n başlamaq əgər 1 almaq üçün və yuxarıda bu adımları edin. N 1 olarsa, bu, 0 addımlar atır. Əks halda, bu olacaq Lakin bir addım plus almaq bu da n qalır çox addımlar 2 bölünür n hətta, və ya 3N plus 1, əgər n tək deyil. 

İndi mən burada ekranda qoymaq etdik Sizin üçün test şeyi bir neçə, Sizin üçün testlər hallarda bir neçə görmək bu müxtəlif Collatz nömrələri nə, və həmçinin illüstrasiya addımlar ki, belə ki, siz keçmişdir lazımdır sort fəaliyyət bu prosesi görmək. N bərabərdir Belə ki 1, n Collatz 0. Siz nə yoxdur bir şey 1 geri almaq üçün. Əgər siz artıq orada istəyirik. 

N 2 olarsa, bu, davam edir bir addım 1 almaq üçün. Siz 2 ilə başlayın. Yaxşı, 2 1 bərabər deyil. Belə ki, bir addım olacaq plus lakin çox addımlar onu qalır n 2 bölünür. 

2 bölünür 2 1. Belə ki, lakin bir addım plus edir çox addımlar 1-edir. 1 sıfır addımlar atır. 

Gördüyünüz kimi 3, var bir neçə addımlar iştirak edir. Siz 3 gedin. Və sonra getmək 10, 5, 16, 8, 4, 2, 1. Bu 1 geri almaq üçün yeddi addımlar atır. Gördüyünüz kimi, var bir Burada neçə digər test hallarda proqram test üçün. Belə ki, yenə, video fasilə. Mən indi geri jump getmək lazımdır faktiki prosesi burada nə, bu zənn nə. 

Siz anlamaq bilər baxın n Collatz müəyyən etmək üçün necə Bu necə bir çox hesablayır ki, Bu 1 almaq üçün addımlar. Beləliklə, ümid edirəm, Siz video durdurulmuş var və yalnız məni gözləyir deyil Burada sizə cavab vermək. Amma əgər, yaxşı, Burada cavab hər halda var. 

Belə ki, burada mümkün müəyyən var Collatz funksiyası. N, əgər baza case-- 1 bərabər, biz 0 qayıtmaq. Hər hansı bir daşımır addımlar 1 geri almaq üçün. 

Əks halda, biz iki recursive cases-- var hətta nömrələri üçün bir və tək üçün. Mən hətta nömrələri üçün test yolu n mod 2 0 bərabərdir yoxlamaq üçün edir. Bu, yenə əsasən sual, nə mod is-- geri əgər, əgər mən 2 bölmək n heç bir qalıq var? Yəni hətta sayı olardı. 

Və belə n mod 2 0 bərabərdir əgər test Bu daha sayı. Əgər belədirsə, mən 1 qayıtmaq istəyirəm, bu mütləq, çünki bir addım plus Collatz alaraq nə sayı mənə yarısı. Əks halda, mən 1 qayıtmaq istəyirəm plus Collatz 3 dəfə n plus 1. Digər oldu recursive addım ki, biz hesablamaq bilər Addımlar sayı Collatz-- geri almaq üçün 1 bir sıra verilir. Belə ki, ümid edirəm ki, bu nümunə bir az verdi recursive prosedurlar bir dad. Ümid edirəm ki, kodu hesab edirəm az daha əgər gözəl həyata zərif, recursive şəkildə. Hətta əgər Lakin, recursion bir Buna baxmayaraq, həqiqətən güclü bir vasitədir. Və belə ki, mütləq bir şey ətrafında baş almaq üçün, yaratmaq edə bilərsiniz, çünki recursion istifadə olduqca sərin proqramları ki, əks halda yazmaq üçün mürəkkəb ola bilər Siz loops və iteration kullanıyorsanız. Mən Doug Lloyd edirəm. Bu CS50 edir.