0Pricing
Coding Interview Prep · Ders

Özyineleme Çerçevesi: Temel Durum, Güven, Oluşturma

Her çağrıyı izlemek zorunda kalmadan faktöriyel, üs alma ve basamakların toplamı için doğru özyinelemeli çözümler yazmak üzere üç adımlı yöntemi uygulayın.

Özyineleme Çerçevesi: Temel Durum, Güven, Oluşturma, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 1. 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Özyineleme Neden Zor Gelir

Yeni başlayanların çoğu her özyinelemeli çağrıyı zihinsel olarak izlemeye çalışır; ancak beş düzey derinliğindeki bir özyineleme bile kısa sürede bunaltıcı hâle gelir. Profesyonel yaklaşım, tüm çağrı ağacını zihinsel olarak canlandırmadan doğru özyinelemeli işlevler yazmanızı sağlayan üç adımlı bir çerçeve kullanmaktır: Temel Durum, Güven, Oluşturma.

Bu çerçeve bazen kabul sıçraması olarak adlandırılır: işlevinizin daha küçük girdiler üzerinde çalıştığına güvenirsiniz ve bu varsayımı daha büyük girdiler için çözümü oluşturmada kullanırsınız.

Adım 1: Temel Durumu Tanımlama

Temel durum, daha fazla özyineleme olmadan yanıtı bilinen en basit girdidir. Her özyinelemeli işlevin en az bir temel durumu olmalıdır; aksi hâlde işlev sonsuza kadar özyinelemeli çağrı yapar (yığın taşması). İyi temel durumlara şunlar örnektir: boş liste, tek öğe, n == 0, n == 1 veya problemin basit bir özdeşliğe indirgenmesi.

Özyinelemeli mantıktan önce temel durumu yazın. Şu soruyu sorarak temel durumu belirleyin: 'Bu problemin hemen yanıtlayabileceğim en küçük hâli nedir?'

# Base cases for common problems
def factorial(n):
    if n == 0:          # base case: 0! = 1
        return 1
    # ... recursive step below

def sum_list(lst):
    if not lst:         # base case: sum of empty list is 0
        return 0
    # ...

def height(node):
    if node is None:    # base case: height of null node is 0
        return 0
    # ...

print('Base cases identified')

Adım 2: Özyinelemeli Çağrıya Güvenme

Güven adımı, bir inanç sıçramasıdır: işlevinizin mevcut girdiden kesinlikle daha küçük herhangi bir girdi için zaten doğru çalıştığını varsayın. Şu anda her küçük girdi için bunu kanıtlamanız gerekmez; tümevarımsal kanıt bunu garanti eder. İşlevinizi daha küçük alt probleme uygulayın ve doğru sonucu döndüreceğine güvenin.

Yeni başlayanlar bu adımı genellikle atlar ve bunun yerine süreci zihinsel olarak benzetmeye çalışır. Bu dürtüye direnin; bu çerçeveyi özümsediğinizde, ne kadar derin olursa olsun özyinelemede işe yarar.

# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11  (we TRUST this, don't trace it)
# Build: 3 + 11 = 14

# So:
def sum_list(lst):
    if not lst:
        return 0
    # Trust that sum_list(lst[1:]) returns sum of the rest
    return lst[0] + sum_list(lst[1:])

print(sum_list([3, 1, 4, 1, 5]))  # 14

Adım 3: Çözümü Oluşturma

Oluşturma adımı, güvenilen alt problemin sonucunu mevcut öğenin katkısıyla birleştirerek tüm girdinin yanıtını üretir. Bu genellikle tek bir satırdır: mevcut öğeye ve özyinelemeli çağrının sonucuna bir işlem uygulayın. Yaygın oluşturma işlemleri şunlardır: toplama eklemek, öğeyi listenin başına eklemek, sayacı artırmak ve iki alt sonucun birleştirilmesi.

def factorial(n):
    if n == 0:
        return 1
    # Trust: factorial(n-1) gives (n-1)!
    # Build: n * (n-1)! = n!
    return n * factorial(n - 1)

def power(base, exp):
    if exp == 0:
        return 1
    # Trust: power(base, exp-1) gives base^(exp-1)
    # Build: base * base^(exp-1) = base^exp
    return base * power(base, exp - 1)

print(factorial(6))    # 720
print(power(2, 10))    # 1024

Basamaklar Toplamına Çerçeveyi Uygulama

Problem: negatif olmayan bir tamsayının basamakları toplamını hesaplayın. Temel durum: n == 0 → toplam 0'dır (veya n < 10 → sayının kendisidir). Güven: sumDigits(n // 10), son basamak dışındaki tüm basamakların toplamını döndürür. Oluşturma: son basamak olan n % 10 değerini güvenilen sonuca ekleyin. Bu çerçeve, çözümü üç bildirime dayalı adımda üretir.

def sumDigits(n):
    if n < 10:
        return n            # base case: single digit
    # Trust: sumDigits(n // 10) gives sum of all digits except last
    # Build: add the last digit
    return n % 10 + sumDigits(n // 10)

print(sumDigits(0))      # 0
print(sumDigits(7))      # 7
print(sumDigits(123))    # 6
print(sumDigits(9999))   # 36

Fibonacci: İki Alt Problem

Fibonacci iki özyinelemeli çağrı gerektirir: fib(n-1) ve fib(n-2). Çerçeveyi uygulayın: temel durumlar fib(0) = 0 ve fib(1) = 1 şeklindedir. Güven: her iki küçük çağrı da doğru Fibonacci değerlerini döndürür. Oluşturma: bu iki değerin toplamını döndürün. Bu saf uygulamanın zaman karmaşıklığı O(2^n)'dir; bunu önbellekleme dersinde düzelteceğiz.

def fib(n):
    if n <= 1:
        return n      # base cases: fib(0)=0, fib(1)=1
    # Trust both smaller sub-problems
    return fib(n - 1) + fib(n - 2)

for i in range(8):
    print(f'fib({i}) = {fib(i)}')  # 0,1,1,2,3,5,8,13

Bir Dizgeyi Özyinelemeli Olarak Ters Çevirme

Problem: bir dizgeyi özyinelemeli olarak ters çevirin. Temel durum: boş dizge veya tek karakter; bunlar zaten terstir. Güven: reverse(s[1:]), ilk karakterden sonraki her şeyin tersini döndürür. Oluşturma: ilk karakteri ters çevrilmiş kalan bölümün sonuna ekleyin. Bu çerçeve üç satırlık bir çözüm sağlar.

def reverse_str(s):
    if len(s) <= 1:
        return s            # base case
    # Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
    # Build: append first character at end
    return reverse_str(s[1:]) + s[0]

print(reverse_str(''))        # ''
print(reverse_str('a'))       # 'a'
print(reverse_str('hello'))   # 'olleh'
print(reverse_str('racecar')) # 'racecar'

Görülme Sayılarını Özyinelemeli Olarak Hesaplama

Problem: bir listedeki hedef değerin kaç kez geçtiğini özyinelemeli olarak sayın. Temel durum: boş liste; sayı 0'dır. Güven: count(lst[1:], target), kuyruğun içindeki sayıyı döndürür. Oluşturma: ilk öğe hedefle eşleşiyorsa 1, aksi hâlde 0 ekleyin. Her özyinelemeli adım, listenin boyutunu 1 azaltarak temel duruma doğru ilerler.

def count_occurrences(lst, target):
    if not lst:
        return 0
    # Trust: count in rest of list is handled recursively
    # Build: add 1 if first element matches, else 0
    return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)

print(count_occurrences([1, 2, 3, 2, 4, 2], 2))  # 3
print(count_occurrences([], 5))                    # 0
print(count_occurrences([7, 7, 7], 7))             # 3

Bir Listenin Sıralı Olup Olmadığını Denetleme

Problem: bir listenin artan sırada sıralı olup olmadığını özyinelemeli olarak denetleyin. Temel durum: 0 veya 1 öğeden oluşan liste her zaman sıralıdır. Güven: is_sorted(lst[1:]), kuyruğun sıralı olup olmadığını söyler. Oluşturma: ilk öğe <= ikinci öğeyse AND kuyruk sıralıysa liste sıralıdır. Bu, oluşturma adımında iki koşulun mantıksal AND işlemini kullanan açık bir örnektir.

def is_sorted(lst):
    if len(lst) <= 1:
        return True
    # Trust: is_sorted(lst[1:]) tells us if tail is sorted
    # Build: head <= second element AND tail is sorted
    return lst[0] <= lst[1] and is_sorted(lst[1:])

print(is_sorted([]))           # True
print(is_sorted([1]))          # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # False

Özyinelemeli İkili Arama (Yeniden Ele Alındı)

Çerçeve kullanılarak ifade edilen özyinelemeli ikili arama: temel durum: lo > hi → bulunamadı (-1 döndürülür). Güven: doğru yarıya yapılan özyinelemeli çağrı hedefi bulur veya -1 döndürür. Oluşturma: orta noktayı hesaplayın, karşılaştırın ve uygun yarıyı çağırın. Yinelemeli biçim, üretim ortamında O(1) alan kullanımı nedeniyle yinelemeli biçim tercih edilse de böl ve yönet yapısını açıkça gösterir.

def binary_search(arr, target, lo, hi):
    if lo > hi:          # base case: search space exhausted
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    # Trust both halves return correct results
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    else:
        return binary_search(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1))   # 3
print(binary_search(arr, 4, 0, len(arr) - 1))   # -1

Özyineleme mi Yineleme mi Ne Zaman Kullanılmalı

Özyineleme, problem doğal olarak aynı türden daha küçük alt problemlere ayrıldığında başarılıdır (ağaçlar, böl ve yönet, geri izleme). Şu durumlarda yineleme tercih edilir: özyineleme derinliği büyükse (Python'da varsayılan olarak yaklaşık 1000 olan sınır nedeniyle yığın taşması riski varsa), özyinelemeli ve yinelemeli sürümler eşit derecede açıksa veya problem basit bir döngüyse (factorial, önbellekleme olmadan Fibonacci).

İyi bir pratik kural şudur: Bir özyineleme ağacı çizmek doğal geliyorsa özyineleme kullanın. Ağaç düz bir çizgiden ibaretse (kuyruk özyinelemesi), yinelemeye dönüştürün.

import sys

# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit())  # 1000

# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
    total = 0
    for x in lst:
        total += x
    return total

big = list(range(2000))
print(sum_list_iter(big))  # 1999000 — no stack overflow

Hızlı Denetim

Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık konularını ne kadar anladığınızı sınayın.

Ders Özeti

Bu derste şunları öğrendiniz: üç adımlı çerçeve Temel Durum (bilinen en basit yanıt), Güven (alt problemin çözüldüğünü varsayma) ve Oluşturma'dan (mevcut öğeyi güvenilen sonuçla birleştirme) oluşur; temel durumları önce yazmalı ve tüm çağrı ağaçlarını zihninizde izlemekten kaçınmalısınız; ayrıca özyineleme derinliği yığın taşması riski oluşturduğunda veya özyinelemeli ve yinelemeli biçimler eşit derecede açık olduğunda yinelemeyi kullanmalısınız. Sırada çağrı yığınını ayrıntılı olarak görselleştireceğiz.

Sıkça Sorulan Sorular

“Özyineleme Çerçevesi: Temel Durum, Güven, Oluşturma” dersi ücretsiz mi?

Evet — “Özyineleme Çerçevesi: Temel Durum, Güven, Oluşturma” 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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.

“Özyineleme Çerçevesi: Temel Durum, Güven, Oluşturma” dersinde ne öğreneceğim?

Her çağrıyı izlemek zorunda kalmadan faktöriyel, üs alma ve basamakların toplamı için doğru özyinelemeli çözümler yazmak üzere üç adımlı yöntemi uygulayın. Coding 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.

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

Önceden deneyim gerekmez. CoddyKit'te Coding 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 1. dersidir.

“Özyineleme Çerçevesi: Temel Durum, Güven, Oluşturma” 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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding 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

  1. Özyineleme Çerçevesi: Temel Durum, Güven, Oluşturma
  2. Çağrı Yığınını Görselleştirme
  3. Özyinelemeli ve Yinelemeli Yaklaşımların Ödünleşimleri
  4. Not Alma: Özyinelemeli Sonuçları Önbelleğe Alma
← Coding Interview Prep Sayfasına Dön