If you're seeing this message, it means we're having trouble loading external resources on our website.

Bağlandığınız bilgisayar bir web filtresi kullanıyorsa, *.kastatic.org ve *.kasandbox.org adreslerinin engellerini kaldırmayı unutmayın.

Ana içerik

Bilgisayar Bilimi

Konu: Bilgisayar Bilimi > Ünite 1

Ders 5: Özyinelemeli Algoritmalar
Bilgisayar Bilimi
Bilgisayar Bilimi
Algoritmalar
Özyinelemeli Algoritmalar
© 2023 Khan AcademyKullanım ŞartlarıGizlilik PolitikasıÇerez Politikası

Özyinelemeli algoritmaların özellikleri

Google Classroom
Özyinelemeli algoritmalarla ilgili temel fikir şudur:
Bir problemi çözmek için, aynı problemin daha küçük bir örneği olan bir alt problemi çözün ve bu küçük örneğin çözümünü kullanarak, başlangıçtaki problemi çözün.
n!'i hesaplarken, n! çözme problemini (başlangıçtaki problem) daha küçük bir sayının faktöriyelini çözme alt problemini yani (n−1)! (aynı problemin daha küçük örneği) çözerek ve sonra bu alt problemin sonucunu n! değerini bulmakta kullanarak bulduk.
Özyinelemeli bir algoritmanın çalışması için, küçük alt problemlerin hepsi sonuçta temel duruma ulaşmalıdır. n!'i hesaplarken, alt problemler biz 0!'i hesaplayana kadar küçülür. Sonunda, temel durumu yakaladığınızdan emin olmalısınız.
Örneğin, özyinelemeli yöntemimizi kullanarak negatif bir sayının faktöriyelini hesaplamaya çalışsak ne olurdu? (−1)!'i bulmak için, önce (−2)!'i bulmaya çalışırsınız, dolayısıyla sonucu −1 ile çarpın. Ama, (−2)!'i bulmak için, önce (−3)!'i bulmaya çalışırsınız ki, sonucu −2 ile çarpın. Sonra (−3)!'i bulmaya çalışırsınız, vesaire. Elbette sayılar küçülmektedir, ama aynı zamanda 0! temel durumundan gittikçe uzaklaşmaktadır. Hiçbir zaman cevap elde etmezsiniz.
n'nin değerinin negatif olmadığını garanti edebilseniz bile, alt problemleri gittikçe küçültmezseniz, sorun yaşarsınız. İşte bir örnek. Şu formüle bakalım, n!=n⋅(n−1)! ve iki tarafı n'ye bölelim, bu da bize n!/n=(n−1)! verir. Yeni bir m değişkeni oluşturalım ve bunu n+1'e eşitleyelim. Formülümüz herhangi bir pozitif sayı için geçerli olduğundan n yerine m koyalım, ve m!/m=(m−1)! elde edelim. m=n+1 olduğundan, (n+1)!/(n+1)=(n+1−1)! diyebiliriz. İki tarafı değiş tokuş edip, ve n+1−1=n farkına vararak, n!=(n+1)!/(n+1). Bu formül, n!'yi önce (n+1)! 'i bulup sonra cevabı n+1'e bölerek hesaplayabileceğimizi gösterir. Ama (n+1)! hesaplamak için, (n+2)! ve sonra (n+3)!, vesaire hesaplamanız gerekir. 0 temel durumuna hiç ulaşamazsınız. Neden olmasın? Çünkü her özyinelemeli alt problem, daha küçük değil, daha büyük bir sayının değerini hesaplamamızı ister. n pozitifse, 0 temel durumuna ulaşamazsınız.
Özyineleme fikrini iki basit kurala indirgeyebiliriz:
  1. Her özyinelemeli çağrı, aynı problemin daha küçük bir örneğinde, yani daha küçük bir alt problemde yapılmalıdır.
  2. Özyinelemeli çağrılar, sonuçta, özyinelemeyle çözülemeyen bir temel duruma ulaşmalıdır.
Rus bebeklere geri dönelim. Bunlar herhangi bir algoritmaya girmese de, diğerlerini kaplamayan en küçük bebeğe kadar (temel duruma benzer) her bebeğin daha küçük bebekleri kapladığını (özyinelemeli duruma benzer) görebilirsiniz.
Bu içerik Dartmouth Bilgisayar Bilimleri öğretim görevlileri Thomas Cormen ve Devin Balkcom ile Khan Academy bilgisayar bölümü içeriklerini hazırlayan takımın işbirliği ile hazırlanmıştır. İçerik CC-BY-NC-SA lisanslıdır.

Tartışmaya katılmak ister misiniz?

Giriş Yap
Henüz gönderi yok.
İngilizce biliyor musunuz? Khan Academy'nin İngilizce sitesinde neler olduğunu görmek için buraya tıklayın.