Chapter 19: Yineleme

Bir çocuk uyuyamamış, annesi ona küçük, uyuyamayan bir kurbağa hakkında bir hikaye anlatmış,
  kurbağanın annesi ona küçük, uyuyamayan bir ayı hakkında bir hikaye anlatmış,
    ayının annesi ona küçük bir gelincik hakkında bir hikaye anlatmış...
      gelincik uyuya kalmış;
    ...ve küçük ayı uyuya kalmış;
  ...ve küçük kurbağa uyuya kalmış;
...ve çocuk uyuyakalmış.

Kaynak: http://everything2.com/title/recursion

Yineleme bazı tanımlandıkları terim yine kendileri olan nesneler veya işlem türleridir. Faktöriyel ve fibonacci serileri gibi matematiksel örnekler yinelemelidir. Başka dökümanlar içeren başka dökümanları içerebilen dökümanlar yinelemelidir. Fraktal(kesirsel) görüntüler ve hatta belirli biyolojik işlemler çalışma prensiplerinde yinelemelidir.

19.1 Yineleme Nerede Kullanılır?

İnternet sayfaları gibi dökümanlar doğal olarak yinelemelidir. Örneğin, alttaki kod basit bir web dökümanıdır:

Bu internet sayfası, düzenlemeye yardımcı bir "kutu"nun içerisinde yerleştirilebilir:

Bu yinelemeli çalışır. Her kutu, başka bir web sayfası içerebilecek kutuya sahip bir web sayfası içerebilir:

Yinelemeli fonksiyonlar çoğu zaman CmSc 155'te incelenecek olan ileri seviye sıralama algoritmaları ile birlikte kullanılır.

Bir kişi programcı haline gelmese bile, yinelemeli sistemlerin anlaşılması önemli bir husustur. Eğer yinelemeli tablo yapılarına, dökümanlara veya başka bir şeye ihtiyaç duyan bir iş varsa, bunu programcıya açık bir şekilde nasıl söyleyeceğini bilmek önemlidir.

Örneğin, bir kişi, yemek tarifi için içindekileri ve yapılışını içeren bir web programı isteyebilir. Yinelemeye alışık bir kişi içindekiler kısmında listelenen her şeyin başka içindekiler menüsünde bulunanların bir tarif(ya da tarifler) olabileceğini belirtebilir. İkinci sistem çok daha güçlüdür.

19.2 Program seviyesinde yineleme ne demektir?

Önceki bölümlerde, kullandığımız fonksiyonlar diğer fonksiyonları çağırmıştı. Örneğin:

def f():
    g()
    print("f")

def g():
    print("g")
    
f()

Ayrıca, bir fonksiyonun kendisini çağırması da mümkündür. Bir fonksiyınun kendisini çağırması yineleme adlı fikir kullanılarak yapılır. Mesela:

def f():
    print("Merhaba")
	f()

f()

Yukarıdaki örnek Merhaba yazdıracak ve sonra tekrar f() fonksiyonunu çağıracaktır. Bu da başka bir Merhaba ifadesinin yazdırılmasına ve f() fonksiyonunun tekrar çağırılmasına neden olacaktır. Bu bilgisayar stack space(yığın alanı) olarak adlandırılan bir şeyle durana kadar devam edecektir. Bu gerçekleştiğinde, Python şununla biten uzun bir hata verecektir:
RuntimeError: maximum recursion depth exceeded

Bilgisayarın size, programcıya demek istediği, tavşan yuvasından çok fazla ufaklaştığıdır.

19.3 Yineleme Derinliğini Kontrol Etmek

Yinelemeyi başarılı bir şekilde kullanmak için, fonksiyonun durmadan kendini tekrar tekrar çağırmasını engellemenin bir yolu olmalıdır. Alttaki örnek fonksiyonun kaç kere çağırıldığını sayar ve fonksiyon kendisini on kez çağırdığında çıkmak için bir if yapısı kullanır.

def f(level): # Bulunduğumuz seviyeyi ekrana yaz print("Yineleme çağrısı, seviye",level) # Eğer onuncu seviyeye erişmediysek... if level < 10: # Bu fonksiyonu tekrar çağır # ve bir seviye daha ekle f(level+1) # 1. seviyeden yinelemeli çağrılara başla f(1)

Çıktı: Yineleme çağrısı, seviye 1 Yineleme çağrısı, seviye 2 Yineleme çağrısı, seviye 3 Yineleme çağrısı, seviye 4 Yineleme çağrısı, seviye 5 Yineleme çağrısı, seviye 6 Yineleme çağrısı, seviye 7 Yineleme çağrısı, seviye 8 Yineleme çağrısı, seviye 9 Yineleme çağrısı, seviye 10

19.4 Yineleme ile Faktöriyel Hesabı

Yinelemeli şekilde yazılabilen her kod yineleme kullanılmadan da yazılabilir. Bazı programcılar yinelemeli kodun anlaşılmasının daha rahat olduğunu düşünüyor.

Bir sayının faktöriyelini hesaplamak yineleme kullanımının klasik bir örneğidir. Faktöriyeller olasılık ve istatistikte kullanışlıdır. Örneğin:
$10! = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

Yinelemali olarak, bu şu şekilde ifade edilebilir:
$n! = \begin{cases} 1 & \text{if } n = 0, \\ n \cdot (n-1)! & \text{if } n > 0. \end{cases}$

Altta $n!$'i hesaplamak için iki örnek fonksiyon var. İlki yinelemeli değil, ikincisi ise yinelemeli.

# Bu program faktöriyeli
# yineleme KULLANMADAN hesaplıyor
def factorial_nonrecursive(n):
    answer = 1
    for i in range(2,n+1):
        answer = answer * i
    return answer

# Bu program faktöriyeli
# yineleme KULLANARAK hesaplıyor
def factorial_recursive(n):
    if( n == 1 ):
        return n
    else:
        return n * factorial_recursive(n-1)   

Bu fonksiyonlar kendi başlarına hiçbir şey yapmazlar. Altta her şeyi bir araya getirdiğimiz bir örnek var. Bu örnek aynı zamanda fonksiyonun içerisinde ne olduğunu anlamamız için bazı print() ifadeleri de ekliyor:

# Bu program faktöriyeli # yineleme KULLANMADAN hesaplıyor def factorial_nonrecursive(n): answer = 1 for i in range(2,n+1): print( i,"*",answer,"=", i*answer) answer = answer * i return answer print("Faktöriyeli hesaplayabilirim!") user_input = input ("Bir sayı girin:") n = int(user_input) answer = factorial_nonrecursive(n) print (answer) # Bu program faktöriyeli # yineleme KULLANARAK hesaplıyor def factorial_recursive(n): if( n == 1 ): return n else: x = factorial_recursive(n-1) print( n, "*", x, "=", n * x ) return n * x print("Faktöriyeli hesaplayabilirim!") user_input = input ("Bir sayı girin:") n = int(user_input) answer = factorial_recursive(n) print (answer)

Çıktı: Faktöriyeli hesaplayabilirim! Bir sayı girin:7 2 * 1 = 2 3 * 2 = 6 4 * 6 = 24 5 * 24 = 120 6 * 120 = 720 7 * 720 = 5040 5040 Faktöriyeli hesaplayabilirim! Bir sayı girin:7 2 * 1 = 2 3 * 2 = 6 4 * 6 = 24 5 * 24 = 120 6 * 120 = 720 7 * 720 = 5040 5040

19.5 Yinelemeli Dikdördgenler

Kendi kendilerine yinelemeli yapıda olan dökümanlarla çalışmak için yineleme harikadır. Örneğin, bir internet dökümanı yerleşime yardımcı olması amacıyla satır ve sütunlardan oluşan bir tabloya sahip olabilir. Bir satır üst kısım, diğer satır ana gövde ve son olarak da alt kısım. Bir tablo hücresinin içinde başka bir tablo olabilir. Ve bunun içerisinde de başka bir tablo olabilir.

Başka bir örnek ise e-posta. Başka bir kişinin e-postasını kendi e-postanıza eklemeniz mümkündür. Fakat bu e-posta kendisine eklenmiş başka bir e-posta içerebilir, ve bu şekilde devam eder.

Altta dikdördgen çizdiren ve yinelemeli olarak her biri bir üst dikdördgenden %20 küçük dikdördgenler çizdiren bir pygame kodu örneği var. recursive_draw() fonksiyonunda bulunan yinelemeli çağırmayı iyi inceleyin.

# Örnek Python/Pygame Programları
# Simpson College Computer Science
# http://cs.simpson.edu
# Çeviri hata/düzeltme(Translation mistakes/corrections):
# yildirimgur@itu.edu.tr

import pygame
 
# Bazı renkleri tanımla
black    = (   0,   0,   0)
white    = ( 255, 255, 255)
green    = (   0, 255,   0)
red      = ( 255,   0,   0)
 
def recursive_draw(x,y,width,height):
    # Dikdördgeni çiz
    pygame.draw.rect(screen,black,[x,y,width,height],1)

	# Dikdördgen tekrar çizmek için yeterince geniş mi?
    if( width > 14 ):
        # Azalt
        x += width * .1
        y += height * .1
        width *= .8
        height *= .8
        # Yinelemeli olarak tekrar çiz
        recursive_draw(x,y,width,height)
    
pygame.init()
  
# Ekranın genişliğini ve yüksekliğini belirle
size=[700,500]
screen=pygame.display.set_mode(size)
 
pygame.display.set_caption("Oyunum")
 
# Kullanıcı kapat butonuna basana kadar döngü
done=False
 
# Ekran yenilenme hızını ayarlamak için kullanılır
clock=pygame.time.Clock()
 
# -------- Ana Program Döngüsü -----------
while done==False:
    for event in pygame.event.get(): # Kullanıcı bir şey yaptı
        if event.type == pygame.QUIT: # Kapat butonuna tıkladıysa
            done=True # Döngüden çıkabilmek için işimizin bittiğini söyle
 
    # Arkaplanı ayarla
    screen.fill(white)
 
    # ÇİZİM İÇİN OLAN BÜTÜN KOD BU YORUMUN ALTINDA YER ALMALI
    recursive_draw(0,0,700,500)
    # ÇİZİM İÇİN OLAN BÜTÜN KOD BU YORUMUN ÜSTÜNDE YER ALMALI
     
    # Saniyede 20 frame ile sınırla
    clock.tick(20)
 
	# İlerle ve ekranı yeni çizdiklerimiz ile güncelle
    pygame.display.flip()
     
# IDLE dostu olun. Bu satırı unutursanız, program çıkışta 
# 'asılı' kalacaktır
pygame.quit ()

19.6 Faktöriyeller

Fraktaller(Daha küçük boyutta aynı şekilleri defalarca içeren şekillerdir.) yinelemeli olarak tanımlanırlar. Burda yinelemenin "derinliğine" bağlı olarak nasıl değiştiğini gösteren oldukça basit bir fraktal vardır.

# Örnek Python/Pygame Programları
# Simpson College Computer Science
# http://programarcadegames.com/
# http://simpson.edu/computer-science/
# Çeviri hata/düzeltme(Translation mistakes/corrections):
# yildirimgur@itu.edu.tr
 
import pygame
 
# Bazı renkleri tanımla
black    = (   0,   0,   0)
white    = ( 255, 255, 255)
green    = (   0, 255,   0)
red      = ( 255,   0,   0)
 
def recursive_draw(x,y,width,height,count):
    # Dikdördgeni çiz
    #pygame.draw.rect(screen,black,[x,y,width,height],1)
    pygame.draw.line(screen,black,[x+width*.25,height//2+y],[x+width*.75,height//2+y],3)
    pygame.draw.line(screen,black,[x+width*.25,(height*.5)//2+y],[x+width*.25,(height*1.5)//2+y],3)
    pygame.draw.line(screen,black,[x+width*.75,(height*.5)//2+y],[x+width*.75,(height*1.5)//2+y],3)

    if count > 0:
        count -= 1
        # Sol üst
        recursive_draw(x,y,                    width//2,height//2,count)
        # Sağ üst
        recursive_draw(x+width//2,y,           width//2,height//2,count)
        # Sol alt
        recursive_draw(x,y+width//2,           width//2,height//2,count)
        # Sağ alt
        recursive_draw(x+width//2,y+width//2,  width//2,height//2,count)
    
pygame.init()
  
# Ekranın genişliğini ve yüksekliğini belirle
size=[700,500]
screen=pygame.display.set_mode(size)
 
pygame.display.set_caption("Oyunum")
 
# Kullanıcı kapat butonuna basana kadar döngü
done=False
 
# Ekran yenilenme hızını ayarlamak için kullanılır
clock=pygame.time.Clock()
 
# -------- Ana Program Döngüsü -----------
while done==False:
    for event in pygame.event.get(): # Kullanıcı bir şey yaptı
        if event.type == pygame.QUIT: # Kapat butonuna tıkladıysa
            done=True # Döngüden çıkabilmek için işimizin bittiğini söyle
 
    # Arkaplanı ayarla
    screen.fill(white)
 
    # ÇİZİM İÇİN OLAN BÜTÜN KOD BU YORUMUN ALTINDA YER ALMALI
    fractal_level=3
    recursive_draw(0,0,700,500)
    # ÇİZİM İÇİN OLAN BÜTÜN KOD BU YORUMUN ÜSTÜNDE YER ALMALI
     
    # Saniyede 20 frame ile sınırla
    clock.tick(20)
 
	# İlerle ve ekranı yeni çizdiklerimiz ile güncelle
    pygame.display.flip()
     
# IDLE dostu olun. Bu satırı unutursanız, program çıkışta 
# 'asılı' kalacaktır
pygame.quit ()

Yineleme ayrıca bölerek aramada da kullanılabilir. Burada 17. bölümden yinelemeli olmayan bir bölerek arama örneği var:

def binary_search_nonrecursive(search_list,key):
    lower_bound = 0
    upper_bound = len(search_list)-1
    found = False
    while lower_bound < upper_bound and found == False:
        middle_pos = (int) ((lower_bound+upper_bound) / 2)
        if search_list[middle_pos] < key:
            lower_bound = middle_pos+1
        elif list[middle_pos] > key:
            upper_bound = middle_pos
        else:
            found = True
     
    if found:
        print( "İsmin bulunduğu yer",middle_pos)
    else:
        print( "İsim listede bulunamadı." )
        
binary_search_nonrecursive(name_list,"Morgiana the Shrew")

Aynı bölerek arama, yinelemeli şekilde yazıldı:

def binary_search_recursive(search_list,key, lower_bound, upper_bound):
    middle_pos = (int) ((lower_bound+upper_bound) / 2)
    if search_list[middle_pos] < key:
        binary_search_recursive(search_list,key, middle_pos+1, upper_bound)
    elif search_list[middle_pos] > key:
        binary_search_recursive(search_list,key, lower_bound, middle_pos )
    else:
        print("Bulunduğu konum",middle_pos)
        
lower_bound = 0
upper_bound = len(name_list)-1
binary_search_recursive(name_list,"Morgiana the Shrew",lower_bound,upper_bound)

You are not logged in. Log in here and track your progress.