Özyineleme Nedir?
İngilizce: Recursion
Yayın: · Son güncelleme:
Özyineleme Nedir? Kısaca
Özyineleme (recursion), bir fonksiyonun bir problemi çözmek için kendini daha küçük bir girdiyle yeniden çağırmasıdır. Her özyinelemeli fonksiyonda çağrıları durduran bir temel durum bulunmalıdır, yoksa program sonsuza kadar kendini çağırır.
Özyineleme nedir?
Özyineleme, bir fonksiyonun çalışırken kendini yeniden çağırmasıdır. Fikir, büyük bir problemi aynı türden daha küçük bir probleme indirgemektir. İngilizcede recursion denir ve algoritma derslerinin temel konularındandır.
Nasıl çalışır?
Her özyinelemeli fonksiyonun iki parçası vardır. Temel durum, cevabın doğrudan bilindiği en küçük hâldir. Özyinelemeli adım ise problemi bir kademe küçültüp fonksiyonu yeniden çağırır. Çağrılar temel duruma ulaşınca geri dönmeye başlar ve sonuçlar birleşir.
Klasik örnek faktöriyeldir. 4 faktöriyeli hesaplamak için fonksiyon "4 çarpı 3 faktöriyel" der, 3 faktöriyel için "3 çarpı 2 faktöriyel" der ve bu zincir 1 faktöriyele kadar sürer. 1 faktöriyel doğrudan 1 olarak döner; ardından 2, 6 ve 24 sonuçları sırayla hesaplanır.
Nerelerde kullanılır?
Klasör içindeki tüm alt klasörleri taramak, ağaç veri yapısı üzerinde gezinmek ve hızlı sıralama gibi böl ve yönet algoritmaları özyinelemenin doğal kullanım alanlarıdır. Bu problemlerde döngüyle yazılan çözüm çoğu zaman daha karmaşık görünür.
Nelere dikkat etmeli?
En sık hata temel durumu unutmak ya da ona hiç ulaşmayan bir koşul yazmaktır. Sonuç, çağrı yığınının dolması ve "stack overflow" hatasıdır. Fibonacci gibi problemlerde aynı alt hesap defalarca tekrarlanabilir; bunu önlemek için sonuçları önbelleğe alan dinamik programlama tekniklerine bakın. Yazdığınız her özyinelemeli fonksiyonda ilk iş olarak "bu çağrı nerede durur?" sorusunu cevaplayın.
Sıkça Sorulan Sorular
Özyineleme mi döngü mü daha iyi?
Aynı işi çoğu zaman ikisiyle de yapabilirsiniz. Ağaç dolaşma gibi doğası gereği iç içe problemlerde özyineleme daha okunaklıdır; basit tekrarlarda ise döngü genellikle daha az bellek kullanır.
Stack overflow hatası neden olur?
Her fonksiyon çağrısı çağrı yığınında yer kaplar. Temel durum hiç gelmezse ya da çağrı zinciri çok uzarsa yığın dolar ve program bu hatayla durur.