Python’da Recursion (Özyineleme) ve Örnek Problemler
Selamun aleyküm. Ben Lütfullah Erkaya. Bu yazımda Python’da recursive (özyineli) fonksiyonlara değinmek istiyorum. Örnekleri Python üzerinde gösterecek olsam da çözümler birçok programlama dilinde uygulanabilir. Yazdığım kodlar Python 2’ye de Python 3’e de uygundur. Paylaşacağım örneklerin ve bildiklerimin büyük bir kısmı ODTÜ CENG111 dersindendir.
Öncelikle recursive fonksiyonlardan bahsedelim. Recursive fonksiyonlar, tanımlarında kendi kendini tekrar kullanan fonksiyonlardır. Bu fonksiyonlar, zor ve uzun problemleri daha kolay hallerine dönüştürerek adım adım çözmeyi sağlar. Mesela faktoriyel fonksiyonunu recursive olarak tanımlayalım:
n! = n * (n-1)!Bu basit örnekte bir sayının faktoriyelini sayının kendisi ile sayının bir eksiğinin faktoriyelinin çarpımı olarak tanımlıyoruz. Ama burada bir sorun var. “(n-1)! = (n-1)* (n-2)!” diyemez miyiz? Sonsuza kadar aynı şeyi yapabilir miyiz? Bir yerde durması gerekiyor, değil mi? İşte bu yere base case (temel durum) diyoruz ve bu fonksiyonda base case n’nin 0 olmasıdır. n = 0 olunca recursion en derine inmiş olur ve artık kendini tekrar etmeyi bırakır, geri dönmeye başlar artık. Python’da şöyle yazabiliriz bu fonksiyonu:
Recursion sayesinde böyle temiz ve ilginç bir çözüme ulaşabiliyoruz.
Bir de recursive olarak fibonacci dizisinin n. terimini bulma fonksiyonuna bakalım. Bu dizinin özelliği her bir terimin kendinden bir önceki ve iki önceki terimin toplamı olmasıdır. Kodun yaptığı şey basit. Öncelikle ilk iki terimin 1 olduğunu belirliyoruz. Burada base case’imiz n ≤ 2 olmasıdır, 1 döner. n > 2 olduğu durumlarda ise recursive fonksiyonumuz her bir çağırmada base case’e inene kadar çalışır.
Dikkat ederseniz başarılı olarak çalışmasına rağmen bu kodun kötü bir tarafı var. Zaten hesapladığı değerleri tekrar tekrar hesaplıyor. Mesela fibonacci(n)’yi hesaplarken zaten fibonacci(n-2)’yi bulmuştu ama fibonacci(n-1)’i hesaplarken fibonacci(n-2)’yi boş yere tekrar hesaplamak zorunda kalıyor.
fibonacci(5) fonksiyonunun değerinin hesaplanma grafiğini inceleyelim.
Gördüğünüz gibi bir sürü gereksiz hesaplama var. Bu fonksiyon küçük sayılarla hemen hesaplama yapabilir ama 100, 200 gibi çok da büyük sayılmayan sayılar girerseniz hesaplamanın yapılması dakikalar, belki de saatler sürebilir. İsterseniz deneyebilirsiniz. Ben mesela 200'ü denediğimde program hesaplamaya başladı, en başta hiçbir cevap yoktu. İşlemcinin tam gaz çalıştığını fanından gelen sesten anlayabiliyordum. Dakikalarca bekledikten sonra Alt+F4'ten başka çözüm kalmadı :). Tabii böyle durumlarda Ctrl+C yaparsanız Python programı yarıda kesecektir ve Alt+F4'e gerek kalmayacaktır.
Recursive fonksiyonlar, her ne kadar temiz bir şekilde yazılabilseler de böyle boş yere hesap yaptırabiliyorlar. Bu sorunu yine recursion ile şöyle çözebiliriz:
Bu fonksiyonun yaptığı şey aslında öncekinin tam tersi. Büyük problemden küçük probleme gitmek yerine küçükten büyüğe inşa ediyor.Else durumundaki recursive fonksiyonun yaptığı şey bir sonraki terimi hesaplamak. Fonksiyonun son iki parametresine bakalım. Fonksiyon ilk çağrıldığında her iki parametrenin de değeri 1 olarak başlıyor. Yani ilk iki terimi 1 kabul ederek başlıyoruz. Else durumundaki fonksiyon her çağırıldığında şu anki terim ile bir önceki terimi topluyor. Bu toplam suAnki’nin yeni değeri, suAnki’nin eski değeri ise onceki’nin yeni değeri oluyor. Fonksiyondaki n parametresi ise sonraki terimi bulma işleminin kaç kere yapılması gerektiğini belirtiyor. Mesela 3. terimi bulmak için 1 kere yapmak yeterli çünkü ilk iki terim zaten elimizde var. 5 terimi bulmak için ise 3 kere terim hesaplamamız gerekiyor. Yani fonksiyona n girmek, n-2 kere fonksiyon tekrar etsin demek oluyor. Bir sayaç yani.
Bu fonksiyon bir önceki fibonacci fonksiyonundan kat kat daha verimlidir. Öncekinde saatler sürebilecek fibonacci(500)’ü bu fonksiyon anında hesaplayabilir. Ama 1000'den büyük bir sayı girerseniz Python’un recursion derinliği sınırına takılacaktır. Python’da recursive fonksiyonlar 1000 derinlik limiti bulunur.
Tabii bu problemler recursive fonksiyon kullanılmadan da çözülebilir ama recursion kullanarak bir çözüm bulmak diğer türlü çözmemizi de kolaylaştıracaktır.
Aşağıda çeşitli örnek problem ve çözümlerini inceleyeceğiz. Size tavsiyem çözüme bakmadan önce kendinizin çözmeye çalışmasıdır. En az on dakika harcayın mesela her birine çünkü böyle yapmadan, problemlerin üzerine düşünmeden öğrenmek zor olur.
Bir sayının rakamları toplamını bulma
Listenin elemanlarının sıralarını ters çevirir (Python’da yerleşik gelen list.reverse() metodu ile aynı işlevlidir ama reverse metodunun farkı orijinal listeyi değiştirmesidir.)
Bu yeni liste oluşturma yöntemi güzel bir yöntemdir. Dikkat edin, Python’da -1 indeksi, son elemanın indeksini belirtir. Diğer örneklerde de kullanacağız. Bu fonksiyon listeyi alır, son elemanını alıp yeni bir listeye koyar ve sonra son eleman bulunan listeyi başa alıp son elemanı içinden çıkarılmış listeyle birleştirir. Dikkat ederseniz nereden birleştirdiğiniz önemli.
liste_ters_dondur(liste[:-1]) + [liste[-1]] deseydiniz mesela listenin sırası aynı kalır, ters dönmemiş olurdu.
İki tam sayı arasındaki tam sayıları bulucu
Bir listenin en büyük ve en küçük elemanını bulucu
Bir fonksiyonu bir listenin tüm elemanlarına uygulayan fonksiyon (Python’da yerleşik olarak gelen map fonksiyonu ile işlevi aynıdır.)
Tanımladığımız fibonacci fonksiyonunun n. terimini değil de n tane terimini liste halinde döndüren versiyonu
Listenin elemanlarının sırasını ters çevirir. Eğer listenin içinde iç içe listeler varsa her bir listenin de elemanını ters çevirir.
Bu fonksiyon ilginçtir. Düşününce zor bir problem gibi ama recursive çözümü o kadar da zor değil. Linux’te terminalde mesela bir klasör kopyalarken veya başka bir işlem yaparken klasörün içinde de klasörler varsa -r yazmak gerekiyor. Oradaki r, recursive’nin r’sidir. Muhtemelen orada da buna benzer bir fonksiyon bulunuyor. Yani böyle problemleri çözmek gerçek hayatta daha çok işimize yarayacak problemleri çözmemize yardım edebiliyor.
Listedeki sayıları toplar. Eğer listenin içinde iç içe listeler varsa her bir listenin içindeki sayıları da toplar. (Python’da yerleşik olarak sum(iterable) fonksiyonu vardır ama iç içe listelerde çalışmaz.)
Listede belirli bir elemanın tekrar sayısını döner. (list.count(eleman) metodu ile aynı işlevlidir.)
Belirli bir fonksiyondan True vermeyen liste elemanlarını siler. (filter fonksiyonu ile işlevi aynıdır.)
Bir listenin içinde listeler olsun. Her bir iç listeye belirli bir elemanı ekler.
Bir küme, liste olarak veriliyor. Bu fonksiyon, listenin tüm alt kümelerinin liste olarak bulunduğu listeyi döndürmelidir. Yukarıdaki fonksiyondan yardım alabilirsiniz.
Bu fonksiyonun çalışma prensibini aşağıdaki resimde görebilirsiniz:
Bu problemleri çözmenin recursive düşünmeyi geliştireceğini düşünüyorum. Buradaki çoğu problemin recursive olsun olmasın muhtemelen çok daha verimli ve hızlı çözümleri vardır ama her şeyi hazır alıp kullanmaktansa bazı problemlere kendi çözümlerimizi üretmek güzel bir his bence. Hani yine daha verimli çözümü kullanırım da kendim de çözüm üretmeyi bilirim mesela.
Bu yazıda paylaşacaklarım bu kadar. Başka bir Bilgisayar Mühendisliği yazısında görüşmek üzere Allah’a emanet olun.
Github:
