Öz yineleme (recursion) nedir?

Python ile Kodlama Mülakatı Soruları Pratiği

Kirill Smirnov

Data Science Consultant, Altran

Tanım

Öz yineleme, bir problemi kendisiyle tanımlama sürecidir
Öz yineleme, bir fonksiyonun kendini alt yordam olarak çağırmasıdır

Örnek: Faktöriyel $n!$

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

$n = 4$:

$4! = 4\cdot3\cdot2\cdot1$

4! = 24

Faktöriyel - Yinelemeli Yaklaşım

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1 = $

$ = 1\cdot2\cdot3\cdot...\cdot n$

Yinelemeli (iteratif) çözüm:

# iterative factorial
def fact_iter(n):
    result = 1
    # 1'den n'e kadar sayılarda döngü
    for num in range(1, n+1)
        result = num * result

    return result

$n = 4:$

result = 1

result = 1 * result(1) = 1
result = 2 * result(1) = 2
result = 3 * result(2) = 6
result = 4 * result(4) = 24

$4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$

Faktöriyel - Öz Yinelemeli Yaklaşım

$n!$ $=n\cdot(n-1)!$

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

Bu koddaki sorun nedir?

fact_rec(4)

RecursionError

Bir temel durum tanımlamalıyız!

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

Durdurma ölçütü / temel durum: $1! = 1$

def fact_rec(n):
    if n == 1:
        return 1
    return n * fact_rec(n-1)

fact_rec(4)

Özet

Öz yinelemeli fonksiyonların iki ana bileşeni vardır:

kendisinin daha küçük bir alt problemine yapılan öz yinelemeli çağrı
sonsuz çağrıyı önleyen bir temel durum (base case)

Örnek - Karar Ağaçları

Karar Ağacı

Karar ağacıyla sınıflandırma

Karar Ağacında Gezinme

Karar ağacında gezinme

x - yeni bir örnek $(x_1, x_2)$

# Kategoriyi bulmak için sözde algoritma:

category = pred(node, x):

  # Bölünme var mı kontrol et  
  if node.hasSplitting:

    # Hangi çocuk düğüme gidileceğini kontrol et
    if node.goToLeftChild(x):
      return pred(node.leftChild, x)   
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

Karar Ağacında Gezinme

Karar ağacıyla tahmin

x - yeni bir örnek $(x_1, x_2)$

# Kategoriyi bulmak için sözde algoritma:

category = pred(node, x):

  # Bölünme var mı kontrol et  
  if node.hasSplitting:

    # Hangi çocuk düğüme gidileceğini kontrol et
    if node.goToLeftChild(x):
      return pred(node.leftChild, x) 
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

  # Kategoriyi döndür
  return node.category

Hadi pratik yapalım!

Python ile Kodlama Mülakatı Soruları Pratiği