Python'da Özyinelemeli (Recursive) Fonksiyonları Anlama

Profesyonel bir programcı olarak, değişkenler, koşul deyimleri, veri türleri, erişim belirleyicileri, fonksiyon çağrıları, kapsamlar vb. gibi temel konularda çok iyi olmanız gerekir. Orta katman yazılımı, Web Geliştirme veya Veri Bilimi için bir program yazıyor olun, bunlar bir programcı olarak kapsamlı şekilde bilmeniz gereken en temel şeylerdir. Önce programcısınız; ardından Veri Bilimci, Web Geliştirici, Makine Öğrenimi Mühendisi vb. olursunuz.

Bu temel kavramlardan biri de Özyineleme (Recursion) ve belirli türde fonksiyonlar yazarken bunu bilmek son derece önemlidir. Muhtemelen şunu zaten biliyorsunuz: "Bir fonksiyonun kendisini çağırmasına özyineleme denir." Peki, perde arkasında ne olur? Özyineleme fiziksel belleği nasıl etkiler? Her fonksiyonu özyinelemeli bir fonksiyona dönüştürebilir misiniz? Bu eğitimde, bu temel soruların yanıtlarını bulacaksınız.

Özyinelemeli Bir Fonksiyonun Anatomisi:

Bilgisayar Bilimleri veya Bilişim Teknolojileri lisans derslerinizde Özyineleme terimiyle zaten karşılaşmış olabilirsiniz. Bu bölümde o kavramları ilgi çekici bir şekilde yeniden ele alacaksınız. Hadi başlayalım.

Özyineleme tanımına tekrar dönelim: "Bir fonksiyonun kendisini çağırmasına özyineleme denir". Bu tanımı desteklemek için bir örnek verelim:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

A() fonksiyonunun kendisini çağırdığını görebilirsiniz. Bu bir özyineleme örneğidir ve A() özyinelemeli bir fonksiyondur.

Şimdi özyinelemeli bir fonksiyonun bazı temel özelliklerini inceleyelim.

Özyinelemeli bir fonksiyonun temelleri:

Özyinelemeli bir fonksiyon şu iki özelliği içermelidir:

• Bir yineleme bağıntısı
• Bir sonlandırma koşulu

Bu noktaları anlamak için yukarıdaki kod parçasını ele alın. Açıkça, fonksiyon belirli bir yineleme bağıntısına sahiptir:

$n\le 1$ sonlandırma koşulu / çapa (anchor) koşulu / taban koşuludur ve bu koşul sağlandığında özyineleme durur. Bu koşulu belirtmek zorunludur; aksi halde fonksiyon bir sonsuz döngüye girer.

(Lütfen dikkat: Yukarıdaki kod parçacığı belirli bir programlama diline ait değildir. Buradaki temel amaç, özyinelemeli bir fonksiyona örnek göstermektir.)

Şimdi şunu düşünüyor olabilirsiniz: Daha iyi alternatifler varken neden biri özyinelemeli bir fonksiyon yazar? Evet, bazen bir özyinelemeyi izlemek zor olabilir; ancak alıştığınızda, okunabilirlik ve değişkenler açısından özyinelemenin ne kadar güzel olduğunu göreceksiniz. Özyineleme çalışmak için fazladan değişken gerektirmez; ancak durması için uygun bir sonlandırma koşulu gerektirir. Çoğu zaman, bir özyineleme için doğru sonlandırma koşulunu bulmak zor olabilir. Yine de “Pratik insanı mükemmelleştirir”. Bu eğitimin ilerleyen kısımlarında, bir programın geleneksel yöntemlere kıyasla özyinelemeyle ne kadar güzel ve küçük olabileceğini göreceksiniz. Şimdi, bir özyinelemeli fonksiyonun bellek üzerindeki gösterimine geçeceksiniz.

Özyinelemeli Bir Fonksiyonun Bellek Gösterimi:

Bu bölümde, özyinelemeli fonksiyonların bellekte temel olarak ağaçlar ve yığınlar (stacks) ile nasıl temsil edildiğini inceleyeceksiniz. Bunu anlamak için aşağıdaki özyinelemeli A() fonksiyonunu ele alalım:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Önce ağaçlar kullanılarak bellek gösterimini anlayacaksınız. Kulağa biraz zor gelebilir ama oldukça basittir. Her bir fonksiyon çağrısını ağaç benzeri bir biçimde yazmak isteseydiniz, nasıl görünürdü?

Aşağıdakine benzer bir şey mi?

Burada dikkat edilmesi gereken birkaç nokta:

• Fonksiyon A(3) ile çağrılıyor ve bunun için burada 4 (3+1) fonksiyon çağrısı yapılıyor. Bunu genellersek, A(n) çağrılırsa toplam (n+1) fonksiyon çağrısı gerekir.
• P() çağrıları, print(n) tarafından üretilen yazdırmalardır.
• Fonksiyon, A(0) fonksiyon çağrısıyla durur; çünkü A(0) çağrısından sonraki if deyimi n < 1 alır ve bu da fonksiyonun sonlanmasına neden olur.

Önce bu ağaç benzeri gösterimi gördünüz; çünkü bir özyinelemeli fonksiyonu bir yığın üzerinde temsil etmek için bu gösterime ihtiyaç vardır. Şimdi bunu göreceksiniz.

(Yığın, son giren ilk çıkar (LIFO) düzenini izleyen bir veri yapısıdır)

Yığın gösterimi için ağacı yukarıdan aşağıya ve soldan sağa sırayla dolaşmanız gerekir. Aşağıdaki görsel bunu netleştirecek.

Bu tuhaf görünen şeyi (ağacı) yorumlayalım. Bir yığında iki işlem olduğunu unutmayın: 1. Push — bir öğeyi yığına ekleme, 2. Pop — bir öğeyi yığından çıkarma.

Şimdi ağacı yukarıdan aşağıya ve soldan sağa sırayla dolaşmaya başlayın:

• Bir fonksiyon çağrısı gördüğünüzde onu yığına iteceksiniz (push).
• Bir print()/ P() çağrısı görürseniz, ilgili öğeyi o anda geldiği şekilde yazdıracaksınız.

A(3)'ten A(0)'a sadece yukarıdan aşağıya dolaşımın sonucu olarak yığının öğeleri şöyle olacaktır:

Şimdi ağaç dolaşımının ikinci yarısına, yani soldan sağa sıraya başlıyorsunuz. Bir fonksiyon çağrısını ikinci kez gördüğünüzde onu pop edeceksiniz. Şaşırtıcı biçimde, yığından ilk pop edilecek öğe (A(0)) yığına en son giren öğeydi (LIFO, unutmayın). Yol boyunca üç P() çağrısıyla karşılaşacaksınız — P(1), P(2) ve P(3). Bunları, dolaşım sırasında geldikleri sırada yazdıracaksınız. Sıra şu şekilde olacaktır:

Son olarak, dolaşımı tamamladığınızda yığın tamamen boş olacaktır. Pop işlemini daha iyi anlamak için, tamamen boşaltıldıktan sonraki yığının görüntüsü aşağıdadır.

Basit bir özyinelemeli fonksiyonun bellekte bir ağaç ve bir yığın kullanılarak nasıl temsil edileceğini gördünüz. Şimdi bir özyinelemeyi nasıl izleyebileceğinizi göreceksiniz.

Bir Özyinelemeyi İzleme:

Bu bölümde, bir özyinelemeyi yöntemli bir şekilde nasıl izleyebileceğinizi öğreneceksiniz. Aşağıdaki özyinelemeli fonksiyonu ele alın:

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}

Buradaki kritik nokta şudur: Bir fonksiyon her çağrıldığında bellekte o fonksiyonun yerel değişkenlerini ve bir komut işaretçisini (çağrı o fonksiyona döndüğünde yürütülecek bir sonraki işi gösteren) içeren bir etkinleşim kaydı (activation record) oluşturulur. Diyelim ki main() adlı bir fonksiyon yukarıdaki A() fonksiyonunu A(3) olarak çağırdı. Daha iyi anlamak için A()'nın satırlarını if deyiminden itibaren numaralandıralım:

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}

Etkinleşim kayıtları aşağıdaki gibi görünecektir:

Daha önce belirtildiği gibi, fonksiyonların yerel değişkenlerin ve komut işaretçilerinin (bu durumda satır numarası) kendi kopyaları vardır. A(0)'dan sonra A() fonksiyonu sonlanacak ve pop işlemleri gerçekleşecektir. Burada yatay bir yığın kullanıldığını ve bunun, eğitimde daha önce gördüğünüzle tamamen aynı olduğunu unutmayın. Kayıtlar yığına itilirken yazdırmalar da gerçekleşecek ve şu öğeler yazdırılacaktır:

Komut işaretçileri burada önemlidir; çünkü özyinelemeli bir fonksiyonda denetim sıklıkla aynı fonksiyona gider ancak değişken değeri farklı olur. Her şeyi senkron tutmak için bu işaretçiler gerçekten yardımcı olur. Bir özyinelemeyi ağaç gösterimi kullanarak izlemek için bu süreci birebir uygulayabilirsiniz.

Şimdi bir özyinelemeli fonksiyonun uzay-zaman (space-time) analizinin nasıl yapılacağını inceleyeceksiniz.

Özyinelemeli Bir Fonksiyonun Uzay-Zaman Analizi:

DataCamp'in Python'da Asimptotik Analiz konulu harika bir makalesi var; bu bölümü okumadan önce göz atmanız önerilir. Hızla tekrar edelim: bir fonksiyonun uzay ve zaman analizlerinden (diğer adıyla uzay karmaşıklığı ve zaman karmaşıklığı) ne kastedilir?

Verilen bir girdi için bir fonksiyonun bir çıktı üretmesi beklenir. Bunu yapmak için fonksiyon ne kadar süre alır? Zaman karmaşıklığı ölçüsü bu süreyi yaklaşıklar; buna fonksiyonun çalışma süresi de denir. Benzer şekilde, uzay karmaşıklığı ölçüsü, bir fonksiyonun (verilen bir girdi için) ihtiyaç duyduğu bellek miktarını yaklaşıklar. Peki bunlar neden gereklidir?

• Farklı boyutlarda girdiler üzerinde fonksiyonu çalıştırmak yerine, fonksiyonun farklı boyuttaki girdilerde nasıl davranacağını kolayca yaklaşık olarak tahmin edebilirsiniz.
• Aynı amacı yerine getiren iki fonksiyonunuz varsa hangisini seçersiniz? Kararı vermek için hangi ölçütleri dikkate alırsınız? Evet, doğru tahmin ettiniz. Uzay ve zaman karmaşıklıklarını analiz ederek karşılaştırır ve hangisinin daha iyi performans gösterdiğine bakarsınız.

Şimdi basit bir özyinelemeli fonksiyon alıp uzay ve zaman karmaşıklığını analiz edelim.

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}

Önce zaman karmaşıklığı analizini yapalım. Yukarıdaki A() fonksiyonu için toplam alınan süreyi $T(n)$ olarak varsayalım. $T(n)$, n'in 1'den büyük olup olmadığının karşılaştırılma süresi ile A(n-1)'in çalıştırılma süresinin toplamıdır. Dolayısıyla $T(n)$ şöyle ifade edilebilir:

Buradaki 1, karşılaştırma için harcanan süredir (buraya herhangi bir sabit koyabilirsiniz). Peki A(n-1)'in çalıştırılma süresi (yani $T(n)$ cinsinden) ne olur?

Benzer şekilde,

ve bu şekilde devam eder.

Dikkatle bakarsanız, bu denklemlerin hepsi birbiriyle bağlantılıdır. Öyle değil mi? Bunları ardışık olarak yerine koyarsanız şunu elde edersiniz:

$T(n)$ = 1 + (1 + $T(n-2)$) = 2 + $T(n-2)$ = 3 + $T(n-3)$ = .... = k + $T(n-k)$ (k terim çalıştırıldıktan sonra)

Şimdi, fonksiyonun hangi noktada duracağını belirlemeniz gerekir. Verilen çapa koşuluna göre şunu yazabilirsiniz:

Varsayalım ki fonksiyon k terim çalıştıktan sonra duruyor. Öyleyse şu geçerli olmalıdır:

$n - k = 1 => k = n - 1$

Şimdi k'nın değerini (= n - 1) $T(n) = k + T(n-k)$ ifadesine yerleştirelim:

$T(n) = (n-1) + T(n-(n-1))$
$=> T(n) = (n-1) + T(1)$
$=> T(n) = n-1 + 1 = n$ // T(1) için yalnızca karşılaştırma gereklidir

Asimptotik analiz kuralına göre, $T(n) = n$ ifadesi $T(n) = \mathcal{O}(n)$ şeklinde yeniden yazılabilir. Bu, fonksiyonun (en kötü durum) zaman karmaşıklığının $\mathcal{O}(n)$ olduğu anlamına gelir.

Burada biraz yavaşlayıp sürecin her adımını dikkatle incelemek isteyebilirsiniz. Her ayrıntıyı anlamak için bunu kalem-kağıtla yapmanız şiddetle önerilir.

Fonksiyonun uzay karmaşıklığı analizi basittir. Fonksiyon bellek içi bir fonksiyondur ve fazladan değişken kullanmaz. Dolayısıyla fonksiyonun uzay karmaşıklığının $\mathcal{O}(n)$ olduğunu söyleyebilirsiniz.

Şimdi tüm bunları bir araya getirip Python'da basit bir özyinelemeli fonksiyon uygulayacaksınız.

Python'da Basit Bir Özyinelemeli Fonksiyonun Uygulanması:

Verilen bir sayının faktöriyelini bulmak için özyinelemeli bir fonksiyon yazacaksınız. Ardından aynı fonksiyonun yinelemeli (iteratif) bir sürümünü yazacaksınız. Hadi başlayalım.

# Recursive function factorial_recursion()

def factorial_recursion(n):  
   if n == 1:  
       return n  
   else:  
       return n*factorial_recursion(n-1)

# Call the function

num = 7
print("The factorial of ",num," is ",factorial_recursion(num))

The factorial of  7  is  5040

Özyinelemeli bir fonksiyon yazmak için gereken iki temel bileşeni hatırlıyor musunuz?

• Yineleme bağıntısı
• Sonlandırma koşulu

Bu durumda yineleme bağıntısı şöyle olabilir:

$f(n) = n!$
$f(n) = n * f(n-1)$ vb.

Sonlandırma koşulu, n'in 1'e eşit olduğu durumdur.

Basit, değil mi?

Şimdi, aynı fonksiyonun yinelemeli sürümünü uygulayacaksınız.

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)

factorial_iterative(7)

The factorial of 7 is 5040

İki sürüm arasındaki farkı açıkça görebilirsiniz. Özyinelemeli sürüm, yinelemeli sürümden çok daha zariftir. Öyle değil mi?

Tebrikler!

Sona kadar geldiniz. Bu eğitimde, özyinelemeli fonksiyonları kapsamlı biçimde incelediniz. En temel bilgilerden başlayıp bir özyinelemeli fonksiyonun uzay ve zaman karmaşıklıklarını analiz etmeye kadar hepsini ele aldınız. Ayrıca, belirli bir özelliğe sahip problemleri çözerken özyinelemenin nasıl faydalı olabileceğini gördünüz. Artık (yineleme bağıntısı ve sonlandırma koşulu olan) problemleri özyinelemeyle çözebilecek durumdasınız. Özyineleme kullanarak bir aralık içindeki Fibonacci Sayılarını bulma problemini çözmek isteyebilirsiniz.

İkili Arama, Birleştirmeli Sıralama (Merge Sort), Hanoi Kuleleri vb. gibi yaygın problemleri de özyineleme ile çözmenizi ve bir uzay-zaman analizi yapmanızı öneririm. Bu kesinlikle sizi daha iyi bir programcı yapacaktır.

Giriş düzeyinde ele alınanlar yeterlidir. Ancak özyineleme hakkında daha fazla çalışmak isterseniz aşağıdaki bağlantıları mutlaka ziyaret edin:

• Prof. Grimson'dan Özyineleme ve Sözlükler
• Özyinelemeli fonksiyonların performansını iyileştirmek için Dinamik Programlama

Daha fazla Python öğrenmek istiyorsanız, DataCamp'in ücretsiz Intro to Python for Data Science kursunu alın.