Özyinelemeyi Anlamak

Python'da Veri Yapıları ve Algoritmalar

Miriam Antona

Software engineer

Tanım

• Kendini çağıran fonksiyon
• Döngü kullandığımız durumların çoğu
  • döngüler yerine özyineleme kullanılabilir
• İlk bakışta çok karmaşık görünen sorunları çözebilir

Örnek - faktöriyel

$n!$

Örnek - faktöriyel

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120

Örnek - özyinelemeyle faktöriyel

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)

• Sonsuza dek çalışır!

Örnek - taban durumunu belirleme

• Bir koşul ekleyin
  • algoritmanın sonsuza dek çalışmamasını sağlar
• Faktöriyel taban durumu -> $n=1$

def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120

Özyineleme nasıl çalışır

• Bilgisayar, fonksiyonları izlemek için bir yığın kullanır
  • Çağrı yığını

Özyineleme nasıl çalışır

• factorial(5) başlar
• factorial(5) bitmeden -> factorial(4) başlar
• factorial(4) bitmeden -> factorial(3) başlar

Özyineleme nasıl çalışır

• factorial(5) başlar
• factorial(5) bitmeden -> factorial(4) başlar
• factorial(4) bitmeden -> factorial(3) başlar
• factorial(3) bitmeden -> factorial(2) başlar

Özyineleme nasıl çalışır

• factorial(5) başlar
• factorial(5) bitmeden -> factorial(4) başlar
• factorial(4) bitmeden -> factorial(3) başlar
• factorial(3) bitmeden -> factorial(2) başlar
• factorial(2) bitmeden -> factorial(1) başlar

Özyineleme nasıl çalışır

• factorial(5) başlar
• factorial(5) bitmeden -> factorial(4) başlar
• factorial(4) bitmeden -> factorial(3) başlar
• factorial(3) bitmeden -> factorial(2) başlar
• factorial(2) bitmeden -> factorial(1) başlar

Özyineleme nasıl çalışır

• factorial(1) biter
  • 1 döndürür
• factorial(2) biter

Özyineleme nasıl çalışır

• factorial(1) biter
  • 1 döndürür
• factorial(2) biter
  • 2 döndürür

Özyineleme nasıl çalışır

• factorial(1) biter
  • 1 döndürür
• factorial(2) biter
  • 2 döndürür
• factorial(3) biter
  • 6 döndürür

Özyineleme nasıl çalışır

• factorial(1) biter
  • 1 döndürür
• factorial(2) biter
  • 2 döndürür
• factorial(3) biter
  • 6 döndürür
• factorial(4) biter
  • 24 döndürür

Özyineleme nasıl çalışır

• factorial(1) biter
  • 1 döndürür
• factorial(2) biter
  • 2 döndürür
• factorial(3) biter
  • 6 döndürür
• factorial(4) biter
  • 24 döndürür
• factorial(5) biter
  • 120 döndürür

Özyineleme nasıl çalışır

• factorial(1) biter
  • 1 döndürür
• factorial(2) biter
  • 2 döndürür
• factorial(3) biter
  • 6 döndürür
• factorial(4) biter
  • 24 döndürür
• factorial(5) biter
  • 120 döndürür

Dinamik programlama

• Optimizasyon tekniği
• Esas olarak özyinelemede uygulanır
• Özyinelemeli algoritmaların karmaşıklığını azaltabilir
• Şunlar için kullanılır:
  • Daha küçük alt sorunlara bölünebilen her problem
  • Alt sorunlar çakışır
• Alt sorunların çözümleri kaydedilir, yeniden hesaplama önlenir
  • Bellekleme (memoization)

Hadi pratik yapalım!

Python'da Veri Yapıları ve Algoritmalar