Bilgisayar Programcılığında problem çözmek için bilgisayara komut dizileri verilir. Bu dizilerin çoğu akış diyagramında doğrusal bir karar ağacını işler. Ancak Recursive (özyinelemeli) algoritma oldukça sibernetik bir şekilde kendini tekrar tekrar çalıştıran, aradığı şartlara ulaşana dek durmayan bir yöntemi anlatır.
Recursive (özyinelemeli) algoritmalar, asla aynı şekilde uygulanmıyor. Bir işlem yapılır ve oluşan sonuç tartışılıyor böylece bir sonraki döngüde bu sonuçtan yola çıkılarak farklı bir giriş sisteme geri veriliyor.
Recursive, çözülmesi zor bir problemin, yapı olarak aslına benzeyen ancak, çözülmesi daha kolay olan ufak problemlere bölünerek çözülmesidir. Aynı işlem oluşturulan tüm ufak problemler için tekrarlanır. Ne zaman alt problem o kadar kolay ve açık hale gelir de artık çözülmesi için daha ufak parçalara bölünmesi gerek kalmaz, işte o zaman bu bulunan çözümler birleştirilerek esas problemin çözümü meydana getirilir.
Özyineleme’ye en iyi örnek faktöriyel fonksiyondur. Recursive tanımlaması;
Fibonacci sayıları ile Recursive tanımlamak kolay olmasına rağmen çok yavaştır. Örneğin; F5’i hesaplamak istiyoruz, Recursive algoritmanız F4 ve F3'ü isteyecektir. F4 için ise F3 ve F2'yi hesaplamamız gerekli. Yukarıdaki şekilde görüldüğü üzere F3'ü iki kez hesaplamak zorundayız. Eğer F200'ü hesaplamış olsaydık ağaç gösterimi nasıl olurdu?
Fibonacci sayıları etkili ama genel tanımlamalarda yeterli değil.
n.ci Fibonacci sayısını hesaplamanında bir formülü var;
Recursive algoritmasına bir kaç örnek;
- Bir ağacın yaprakları arasındaki mesafe (Fibonacci’nin bir kopyasıdır.)
- Faktöriyel
- Hanoi Kuleleri
- EBOB (En Büyük Ortak Bölen)
- İkili arama algoritması
Kaynaklar;
http://www.gunesintamicinde.com/hayat-denen-recursive-algoritma/
http://www.cargalmathbooks.com/5%20Recursive%20Algorithms.pdf
http://en.wikipedia.org/wiki/Recursion_(computer_science)
0 yorum:
Yorum Gönder