Özyinelemeli algoritmaların özellikleri

Özyinelemeli algoritmalarla ilgili temel fikir şudur:

$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\cdot (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:

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.