DSA Interview Prep · Ders

Özyineleme ve Özyineleme Ağacı Yöntemi

Özyinelemeli çağrıları ağaçlara dönüştürerek izleyin, Ana Teoremi uygulayın ve birleştirmeli sıralama, faktöriyel ve Fibonacci türevleri için zaman karmaşıklıklarını çıkarın.

Özyineleme ve Özyineleme Ağacı Yöntemi, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.

Özyineleme ve Çağrı Yığını

Bir işlev kendisini çağırdığında, her çağrı bir yığın çerçevesi ekler. Bir temel duruma ulaşılana kadar bu çerçeveler üst üste birikir ve ardından çözülür. Bunu zihninizde canlandırmak, özyinelemeyi analiz etmenin ilk adımıdır.

def factorial(n):
    if n == 0:       # base case
        return 1
    return n * factorial(n - 1)  # recursive call

# Call chain: factorial(4)
#   4 * factorial(3)
#     3 * factorial(2)
#       2 * factorial(1)
#         1 * factorial(0) -> 1
# Unwinds: 1, 2, 6, 24
print(factorial(5))  # 120

Fibonacci İçin Özyineleme Ağacı

Bir özyineleme ağacı, her çağrıyı alt çağrılarına ayırarak genişletir. Saf Fibonacci her seferinde iki dala ayrılır ve yaklaşık 2^n düğümden oluşan bir ağaç meydana getirir; bu da O(2^n) demektir. Kodu inceleyin.

call_count = [0]

def fib_naive(n):
    call_count[0] += 1
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

for n in [5, 10, 15, 20]:
    call_count[0] = 0
    result = fib_naive(n)
    print(f'fib({n})={result}, calls={call_count[0]}')
# Calls roughly double each time n increases by 1

Tekrarlanan Alt Problemleri Belirleme

Bu ağaçta fib(3) gibi aynı çağrılar farklı dallarda tekrarlanır. Bu örtüşen alt problemler, önbellekleme kullanmanız gerektiğini gösterir; önbellekleme O(2^n) değerini O(n)'e indirir.

# Memoised: each unique sub-problem computed once
def fib_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1:    return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

call_count2 = [0]
def fib_counted(n, memo={}):
    call_count2[0] += 1
    if n in memo: return memo[n]
    if n <= 1:    return n
    memo[n] = fib_counted(n-1, memo) + fib_counted(n-2, memo)
    return memo[n]

fib_counted(20)
print(f'calls with memo: {call_count2[0]}')  # only 21

Birleştirmeli Sıralamanın Özyineleme Ağacı

Birleştirmeli sıralamanın ağacında log n düzey vardır ve her düzey toplamda O(n) iş yapar; her öğeye bir kez dokunulur. Bu değerleri çarparak O(n log n) elde edersiniz. Kodu inceleyin.

# Merge sort: at each level, n total elements are merged
# Level 0:  1 merge of n elements    -> n work
# Level 1:  2 merges of n/2 each     -> n work
# Level 2:  4 merges of n/4 each     -> n work
# ...log(n) levels...
# Total: n * log(n)

# Verify with operation counter:
def merge_sort_counted(arr):
    ops = [0]
    def _sort(a):
        if len(a) <= 1: return a
        m = len(a) // 2
        l, r = _sort(a[:m]), _sort(a[m:])
        result, i, j = [], 0, 0
        while i < len(l) and j < len(r):
            ops[0] += 1
            if l[i] <= r[j]: result.append(l[i]); i+=1
            else:             result.append(r[j]); j+=1
        return result + l[i:] + r[j:]
    return _sort(arr), ops[0]

_, c = merge_sort_counted(list(range(64, 0, -1)))
print(f'Merge ops: {c}')  # ~384 ~ 64*log2(64)=384

Ana Teorem

Ana Teorem, T(n) = a*T(n/b) + O(n^d) bağıntısını üç durumla çözer. Birleştirmeli sıralama için (a=2, b=2, d=1) O(n log n) sonucunu verir. Sınav için bu üç durumu ezberleyin.

# Merge sort: T(n) = 2*T(n/2) + O(n)
# a=2, b=2, d=1, log_b(a)=log2(2)=1=d  => O(n log n)

# Binary search: T(n) = 1*T(n/2) + O(1)
# a=1, b=2, d=0, log2(1)=0=d  => O(log n)

# Strassen matrix mult: T(n) = 7*T(n/2) + O(n^2)
# a=7, b=2, d=2, log2(7)~2.81 > 2 => O(n^log2(7)) ~ O(n^2.81)

import math
print('log2(7) =', math.log2(7))  # 2.807...

Özyineleme Ağaçlarını Adım Adım Çizme

Bir özyineleme ağacı çizmek için T(n)'i en üste yazın, her çağrıyı genişletin, her düzeydeki işi toplayın ve ardından düzey sayısıyla çarpın. Bu işlem otomatik hâle gelene kadar pratik yapın.

# Factorial: T(n) = T(n-1) + O(1)
# Tree is a chain: n levels, O(1) each -> O(n)

# Fibonacci: T(n) = T(n-1) + T(n-2) + O(1)
# Binary tree of depth n, ~2^n nodes -> O(2^n)

# Merge sort: T(n) = 2*T(n/2) + O(n)
# Log levels, n work each -> O(n log n)

def count_recursive_calls(n, results=[]):
    if n <= 1:
        results.append(n)
        return n
    return count_recursive_calls(n-1, results) + count_recursive_calls(n-2, results)

results = []
count_recursive_calls(8, results)
print(f'fib(8) leaf calls: {len(results)}')

Üstel Özyineleme: Alt Kümeler

Tüm alt kümeleri oluşturmak O(2^n) değerindedir; tam olarak 2^n alt küme vardır, bu nedenle bundan daha iyisini yapamazsınız. Her öğe ya kümenin içinde ya da dışındadır ve bu seçimler ikili bir ağaç oluşturur. Kodu inceleyin.

def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(list(current))  # O(n) copy
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

nums = [1, 2, 3]
ss = subsets(nums)
print(len(ss))  # 8 = 2^3
print(ss)

Kuyruk Özyinelemesi ve Optimizasyon

Kuyruk özyinelemesi, özyinelemeli çağrının son adım olmasıdır. Bazı diller bu çağrı için çerçeveyi yeniden kullanır, ancak Python bunu yapmaz; bu nedenle derin özyinelemelerde yığın taşması yine yaşanır. Bunun yerine döngü kullanın.

# Tail-recursive factorial (accumulator pattern)
def fact_tail(n, acc=1):
    if n == 0:
        return acc
    return fact_tail(n - 1, n * acc)  # tail call

# Python does NOT TCO, so this overflows for large n
# Instead, convert to iterative:
def fact_iter(n):
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

print(fact_tail(10))  # 3628800
print(fact_iter(10))  # 3628800

Özyinelemenin Uzay Karmaşıklığı

Her özyinelemeli çağrı bir çerçeve tuttuğu için özyineleme O(derinlik) alan kullanır. Doğrusal özyineleme O(n), dengeli ağaçta DFS ise O(log n) değerindedir. Fazla derine giderseniz RecursionError alırsınız.

import sys
print(sys.getrecursionlimit())  # default 1000

# Increase limit for deep problems
sys.setrecursionlimit(10000)

# Track max depth manually
def max_depth_tracker(n, depth=0, max_seen=[0]):
    max_seen[0] = max(max_seen[0], depth)
    if n <= 0:
        return
    max_depth_tracker(n - 1, depth + 1, max_seen)
    return max_seen[0]

print(max_depth_tracker(50))  # 50  => O(n) stack frames

Hızlı Sıralamanın Özyineleme Ağacı

Hızlı sıralama, iyi bir pivot ile O(n log n) değerindedir; ancak sıralanmış bir girdide kötü bir pivot seçilirse O(n^2) değerine düşer. Pivotu rastgele seçmenin önemli olmasının nedeni budur. Kodu inceleyin.

import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)  # randomised -> O(n log n) expected
    less    = [x for x in arr if x < pivot]
    equal   = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

print(quick_sort([3, 6, 8, 10, 1, 2, 1]))  # sorted

Kuvvet İşlevi: Log n Özyinelemesi

Saf x^n hesabı O(n) çarpma gerektirir; ancak karesini alma işlemi her adımda işi yarıya indirir: x^n = (x^(n/2))^2. Böylece temiz bir O(log n) elde edilir; yarıya indirme iş başındadır. Kodu inceleyin.

def fast_pow(x, n):
    if n == 0: return 1
    if n < 0:  return 1 / fast_pow(x, -n)
    if n % 2 == 0:
        half = fast_pow(x, n // 2)
        return half * half          # O(log n) calls
    return x * fast_pow(x, n - 1)

print(fast_pow(2, 10))   # 1024
print(fast_pow(3, 5))    # 243
# Only log2(10)=3-4 recursive calls for n=10

Hızlı Kontrol

Hızlı kontrol — özyineleme ağacı yönteminin size ne öğrettiğini gösterin. Tek bir soru var; acele etmeyin. 🌳

Ders Özeti

Özet: bir özyineleme ağacı toplam işi ortaya çıkarır, Ana Teorem böl ve yönet bağıntılarını çözer ve özyineleme O(derinlik) yığın alanı kullanır.

Sıkça Sorulan Sorular

“Özyineleme ve Özyineleme Ağacı Yöntemi” dersi ücretsiz mi?

Evet — “Özyineleme ve Özyineleme Ağacı Yöntemi” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.

“Özyineleme ve Özyineleme Ağacı Yöntemi” dersinde ne öğreneceğim?

Özyinelemeli çağrıları ağaçlara dönüştürerek izleyin, Ana Teoremi uygulayın ve birleştirmeli sıralama, faktöriyel ve Fibonacci türevleri için zaman karmaşıklıklarını çıkarın. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.

“Özyineleme ve Özyineleme Ağacı Yöntemi” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

← DSA Interview Prep Sayfasına Dön