[MÜZİK OYUN] 

Doug LLOYD: Muhtemelen düşünüyorum Kod sadece bir görevi gerçekleştirmek için kullanılır. Bunu yazmak. Bu bir şey yok. Yani oldukça fazla. 

Bunu derlemek. Programı çalıştırın. Gitmek iyisin. 

Ama ister inan ister inanma, eğer Eğer, uzun bir süre için kodlama Aslında görmeye gelebilir güzel bir şey olarak kodu. Bu bir sorun olarak çözer çok ilginç bir şekilde, ya da gerçekten sadece bir şey var görünüyor yolu hakkında derli toplu. Sen gülüyor olabilir Bana, ama doğru. Ve yineleme bir yoludur sıralama bu fikir edinmek için güzel, zarif görünümlü kodu. Bu şekilde sorun çözer görselleştirmek kolay, ilginç ve şaşırtıcı derecede kısa. 

Yol yineleme çalışmaları özyinelemeli fonksiyon olduğunu çağıran bir fonksiyonu olarak tanımlanmaktadır kendisi yürütme parçası olarak. Yani, biraz garip görünebilir ve biz biraz göreceksiniz Bu bir an nasıl çalıştığı hakkında. Fakat yine de, bu özyinelemeli prosedürler çok zarif olacak Onlar gidiyoruz çünkü kalmadan bu sorunu çözmek için Tüm bu fonksiyonları olan ya bu uzun döngüler. Bu özyinelemeli görürsünüz prosedürler çok kısa bakmak için gidiyoruz. Ve onlar gerçekten yapacağız kodunuzu çok daha güzel görünüyorsun. 

Sana bir örnek vereyim Bu nasıl görmek için özyinelemeli prosedür tanımlanmış olabilir. Bu aşina iseniz Yani yıllar önce matematik sınıfından bir şey denir genellikle faktöryel fonksiyonu, ünlem işareti olarak gösterilen hangi tüm pozitif tamsayılar üzerinde tanımlanır. Ve yolu, n faktöryel hesaplanır Eğer tüm çarpın daha az sayılar eşit veya n beraber-- için tüm tamsayılar daha az ya da birlikte n eşittir. 

Yani 5 faktöryel 5 kat 4 kez 3 kere 2 kere 1. Ve 4 faktör 4 katıdır 3 kez 2 kez 1 ve benzerleri. Sen fikir olsun. 

Programcılar, biz yok n, ünlem işareti kullanın. Bu yüzden faktöryel tanımlarsınız n gerçeği olarak işlev. Ve biz oluşturmak için çarpınımını kullanacağız Bir soruna çözüm özyinelemeli. Ve seni bulmak düşünüyorum çok daha fazla görsel olduğunu iteratif daha çekici Bu sürümü, hangi biz de bir an bakmak gerekir. 

Yani burada bir çift vardır facts-- pun intended-- yaklaşık factorial-- faktöryel fonksiyonu. Dediğim gibi 1 faktöryel, 1'dir. 2 faktöryel 2 kez 1. 3 faktöryel 3'tür 2 katı benzeri kez 1 ve. Biz zaten 4 ve 5 hakkında konuştuk. 

Ama bu bakarak, bu doğru değil mi? 2 faktöryel değil mi sadece 2 kez 1 faktöryel? Yani, 1 faktöryel 1'dir. Peki neden biz sadece söyleyemeyiz, 2 faktöryel 2 kez 1 olduğundan, gerçekten sadece 2 kez var 1 faktöryel? 

Ve sonra, bu fikri uzanan 3 faktöryel değil sadece 3 kez 2 faktöryel? Ve 4 faktöryel 4 katıdır böylece 3, ve faktöryel? Aslında, çok etkenli herhangi bir sayı sadece can tür biz eğer ifade edilebilir sonsuza dek bu yürütmek. Biz tür genelleme olabilir faktöryel sorun o olduğu gibi n kere n eksi 1 faktöryel. Bu n kat ürün var Tüm numaralar benden daha az. 

Bu fikir, bu Sorunun genelleme, Bize özyinelemeli sağlar faktöryel fonksiyonunu tanımlar. Bir işlevi tanımladığınızda yinelemeli, var bunun bir parçası olmak için gereken iki şey. Sen bir şey denilen olması gerekir Baz durumda, hangi, bunu tetikleyebilir zaman, özyinelemeli işlemini durduracak. 

Aksi takdirde, bir işlev çağrıları itself-- sen imagine-- edebileceğiniz gibi sonsuza kadar gidebiliriz. Fonksiyon işlevini çağırır işlev çağrıları çağrıları fonksiyon işlevini çağırır. Eğer bir yol yoksa , programınızı bunu durdurmak için etkin bir şekilde sıkışmış olacak sonsuz bir döngüye de. Bu, sonuçta kilitlenmesine bellekte dışarı kaçıyorum çünkü. Ama konumuz bu değil. 

Biz durdurmak için başka bir yol olması gerekir Program çökmesini yanında şeyler, çöker bir program için Muhtemelen güzel ya da şık değil. Ve böylece bu temel durum diyoruz. Bu basit bir çözümdür durur bir sorun meydana gelen özyineli süreç. Yani bir parçası özyinelemeli bir işlev. 

İkinci bölüm özyinelemeli bir durumdur. Ve bu nerede özyineleme olduğunu Aslında gerçekleşecek. Burası işlevi kendisini arayacak. 

Tam kendini aramayacağım Aynı şekilde o denirdi. Bu hafif bir varyasyon olacak İşte bu sorunun yapar ufacık biraz daha küçük çözmeye çalışıyor. Fakat genellikle bu kova geçer çözeltisinin bir kısmını çözmek satır aşağı farklı bir çağrı. 

Bu görünüm hangisi Burada taban durum gibi? Hangi gibi bu görünüyor biri Bir sorunun en basit çözüm? Biz faktöriyellerinin bir grup var, ve biz devam edebiliriz böylece on-- 6, 7, 8, 9, 10, ve gidiyor. 

Ama böyle bu görünüyor biri İyi durumda temel durum olması. Bu çok basit bir çözüm var. Biz özel bir şey yapmanıza gerek yok. 

1 faktöryel sadece 1'dir. Biz herhangi birini yapmak zorunda değilsiniz çarpma vasıl tüm. Biz gidiyoruz gibi görünüyor denemek ve bu sorunu çözmek için, ve biz durdurmak gerekir yerde tekrarlama, biz muhtemelen durdurmak istiyorsanız biz 1 vardığımızda. Biz bundan önce durdurmak istemiyorum. 

Biz tanımlarken eğer öyleyse Bizim faktöryel fonksiyonu, Burada bir iskelet için var Biz bunu nasıl. Biz bu iki seyleri takmanız gerekir temel durum ve özyinelemeli durumda. Temel durum nedir? N 1 eşitse, dönüş 1-- işte Gerçekten basit bir sorun çözmek için. 

1 faktöryel 1'dir. O değil 1 kez şey var. Bu sadece 1 var. Bu çok kolay bir gerçektir. Ve böylece bizim temel durum olabilir. Biz bu işe 1 geçmiş olsun Eğer fonksiyon, sadece 1 dönersiniz. 

Recursive neler var dava muhtemelen benziyor? Her numara için 1 yanında, desen nedir? Eh, biz alıyorsun eğer n faktöryel, bu kadar n kez n faktöryel eksi 1. 

Biz 3 faktoriyelini çekiyorsanız, o, 3 eksi 1 3 kez faktöryel var ya da 2. Ve biz değiliz eğer öyleyse Aksi takdirde, 1 bakıyor Dönüş n kere n eksi 1 faktöryel. Oldukça basit değil. 

Ve biraz sahip uğruna daha temiz ve kod daha şık, biliyoruz ki biz tek hat döngülere varsa ya da tek hat koşullu dallar, Biz tüm kurtulabilirsiniz çevrelerindeki kaşlı. Yani biz bu bu birleştirebilirsiniz. Bu aynı vardır Bu işlevsellik olarak. 

Ben sadece kıvırcık uzakta alıyorum sadece bir satır var, çünkü parantez Bu koşullu dallar içinde. Yani bunlar aynı şekilde davranır. N, 1 'e eşit olması durumunda, 1 dönmek. Aksi takdirde n kez iade n eksi 1 faktöryel. Bu yüzden küçük bir sorun yapıyoruz. N 5 olarak başlar, biz gidiyoruz 4 5 kez çarpınımını dönün. Ve biz konuşurken bir dakika içinde göreceksiniz Başka bir videoda çağrı stack-- hakkında nerede hakkında konuşmak Biz öğreneceksiniz stack-- çağrı tam olarak bu süreç çalıştığı hakkında neden. 

Ama 5 iken faktöryel diyor 5 kez faktöryel 4 dönmek ve 4 Evet, tamam, demek oluyor, geri dönüş 4 kez 3 faktöryel. Gördüğünüz gibi, biz konum çeşit 1 yaklaşıyor. Biz yakın alıyoruz ve Bu taban durumda yakın. 

Ve biz baz davayı vurmak kez Önceki tüm fonksiyonlarını aradıkları cevabı var. 2 Faktöriyel dönüşü diyordu 2 kez 1 faktöryel. Peki, 1 getiri 1 faktöryel. Faktöriyel Yani çağrısı 2, 2 kez 1 dönebilirsiniz ve faktöriyele için geri ver Bu sonuç için beklemektedir 3. 

Ve o zaman hesaplayabilirsiniz onun sonucu, 3 kez 2, 6 ve 4 faktöriyele geri verin. Ve yine, biz var çağrı yığını video bu biraz gösterilmiş olup, Şu an söylüyorum daha fazla. Ama bu öyle. Bu tek başına çözüm Bir sayının faktöriyel hesaplarken. 

Bu kod sadece dört satırlık var. Bu doğru, oldukça serin? Seksi tür. 

Bu nedenle, genel olarak, ancak Her zaman, bir özyinelemeli fonksiyon Bir bir döngü yerine olmayan recursive fonksiyon. Yani burada, yan yana, iteratif bir faktöriyel fonksiyonunun sürümü. Bu hesapla her iki tam olarak aynı şey. 

Her ikisi de n faktöriyel hesaplayabilirsiniz. Soldaki versiyon Bunu yapmak için yineleme kullanır. Sağdaki sürümü Bunu yapmak için yineleme kullanır. 

Ve haber, biz bildirmek zorunda bir tamsayıdır ürünü değişken. Ve sonra döngü. Çok uzun n olarak biz, daha büyük 0 n tarafından bu ürün çarparak tutmak ve kadar n azaltma Biz ürünü hesaplar. Peki bu iki işlev, yine Tam olarak aynı şeyi yapmak. Ama bunu yapmayın aynı şekilde. 

Şimdi, bu mümkündür Birden fazla tabanı var durumda ya da birden fazla özyinelemeli durumda, bağlı Ne üzerinde işlev yapmaya çalışıyor. Sen mutlaka sadece bunlarla sınırlı değildir Tek bir temel durum ya da tek bir özyinelemeli dava. Şey Yani bir örnek Birden fazla baz vakalarla olabilir paha Fibonacci sayı dizisi. 

Sizden Hatırlayacağınız ilkokul günleri Fibonacci dizisi tanımlanır bu-- gibi ilk öğe 0 olduğunu. İkinci unsur 1'dir. Bunların ikisi de sadece tanım gereği vardır. 

Daha sonra her eleman tanımlanmıştır n eksi 1 ve n eksi 2 toplamı olarak. Üçüncü eleman 0 artı 1 1 olacaktır. Ve sonra dördüncü unsur İkinci unsur, 1 olur, artı üçüncü unsur, 1. Ve bu 2 olur. Ve böylece vb. 

Yani bu durumda, iki baz olgu var. N, 1 'e eşit olması durumunda, 0 dönmek. N, 2 ye eşit olduğu takdirde, 1 dönmek. Aksi takdirde, n Fibonacci'yi dönüş eksi 1 artı n eksi 2 Fibonacci. 

Böylece birden fazla baz davaları var. Ne Birden özyinelemeli durumlar hakkında? Peki, bir şey var Collatz varsayım denir. Ben söylemek gitmiyorum Eğer, ne olduğunu biliyorum Aslında bizim nihai çünkü Bu özel video için sorun. Ve bu bizim egzersiz Birlikte çalışmak. 

Yani burada ne Collatz varsayım o-- Her pozitif tamsayı için geçerlidir. Ve o olduğunu spekülasyon her zaman mümkün geri almak için 1 adımları izlerseniz. N 1 ise, dur. N 1 ise biz 1'e geri var. 

Aksi takdirde, bu geçmesi süreç tekrar n 2'ye bölünür. Eğer 1'e geri alabilirsiniz ve bakın. N garip Aksi takdirde, geçmesi Yine 3n artı 1 bu süreç, veya 3 kez n artı 1. Yani burada biz tek bir baz durum var. N 1 eşitse, dur. Biz daha fazla özyineleme yapmıyoruz. 

Ama biz iki özyinelemeli olgu var. N bile varsa, biz tek özyinelemeli yapmak durum, n 2 bölü arıyor. N tek ise, farklı bir do 3 kez n-plus, 1 özyinelemeli durum. 

Ve böylece bu video için hedefi Bir saniye sürer videoyu duraklatmak için, ve denemek ve bu bilgileri recursive fonksiyon Collatz nerede bir değer n geçmesi ve o kaç adım onu ​​hesaplar Eğer n başlatırsanız 1 almak sürer ve yukarıdaki bu adımları takip. N 1 ise, 0 adımlar atmaktadır. Aksi takdirde, gidiyor Ancak bir adım artı almak o da n alır birçok adım 2 bölü n bile, ya da 3n + 1 ise n tek ise. 

Şimdi, burada ekranda koyduk Sizin için deney bir kaç şey, Sizin için testler durumlarda bir çift görmek için Bu çeşitli Collatz numaraları ne ve aynı zamanda bir örnek adımlardan böylece yapabilirsiniz gitti gerekiyor tür eylem bu süreci bakın. N eşittir Yani eğer 1, n Collatz 0'dır. Yapacak gerekmez şey 1'e geri almak için. Zaten oradayız. 

N, 2 ise, bu alır bir adım 1'e almak için. Sen 2 ile başlayın. Eh, 2 1'e eşit değildir. Yani bir adım olacak artı ancak birçok adım onu alır n 2'ye bölünür. 

2 ile bölünmesiyle 2 1'dir. Yani ancak bir adım artı alır birçok adım 1'e sürer. 1 sıfır adımlar atmaktadır. 

Gördüğünüz gibi 3 için, var epeyce adımları içeriyordu. Sen 3 gidin. Ve sonra gitmek 10, 5, 16, 8, 4, 2, 1. O 1'e geri almak için yedi adımlar atmaktadır. Gördüğünüz gibi, orada bir Burada birkaç diğer test durumlarda Programınızı test etmek. Yani yine Videoyu duraklatmak. Ve ben şimdi geri atlamak gidersiniz Gerçek bir süreç burada ne Bu varsayım nedir. 

Eğer dışarı anlamaya görün n Collatz nasıl tanımlanacağı o kaç hesaplar, böylece 1'e almak için gereken adımları. Yani umarım, video duraklatılmış var ve sadece beni bekliyor değil Seni buraya cevap vermek için. Ama eğer, iyi, Burada cevabı zaten var. 

Yani burada bir olası tanım var Collatz fonksiyonunun. N ise bizim temel case-- 1'e eşit, biz 0 dönmek. Herhangi almaz adımlar, 1 geri almak için. 

Aksi takdirde, biz iki özyinelemeli cases-- var Hatta numaraları için tek ve garip için. Hatta sayılar test yolu n mod 2 0 eşitse kontrol etmektir. Bu, yine, temelde soruyu soran, Ne mod bu-- hatırlayacak olursak eğer 2 ile bölme n hiçbir kalan var mı? Bu bir çift sayı olacaktır. 

Ve böylece n mod 2 0 eşitse Test, bu bir çift sayıdır. Eğer öyleyse, ben 1 dönmek istiyorum, Bu kesinlikle, çünkü Bir adım artı Collatz alarak ne olursa olsun sayı benden yarısı kadardır. Aksi takdirde, ben 1 dönmek istiyorum artı Collatz 3 kez n artı 1. Bu da diğer oldu özyinelemeli adım biz hesaplamak sürebilir Adımların sayısını Collatz-- geri almak için gereken 1 bir numara verilir. Yani umarım, bu örnek Sana biraz verdi özyinelemeli prosedürlerin bir tat. Umarım, kod olduğunu düşünüyorum biraz daha, eğer güzel uygulanan Zarif, özyinelemeli bir şekilde. Bile Ama, özyineleme bir yine çok güçlü bir araçtır. Ve bu yüzden kesinlikle bir şey başınızın etrafında almak için, oluşturmak mümkün olacak çünkü özyineleme kullanarak oldukça serin programlar aksi takdirde yazmak için karmaşık olabilir Eğer döngüler ve yineleme kullanıyorsanız. Ben Doug Lloyd değilim. Bu CS50 olduğunu.