Özyinelemeli ve Yinelemeli Yaklaşımların Ödünleşimleri
Özyinelemeli faktöriyel ve Fibonacci çözümlerini yinelemeli döngülere dönüştürün; Python’un özyineleme sınırı ve yığın boyutunun yinelemeli yaklaşımı ne zaman tercih edilir kıldığını açıklayın.
Özyinelemeli ve Yinelemeli Yaklaşımların Ödünleşimleri, 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-Yineleme İkiliği
Özyinelemeli olarak yazılabilen her algoritma yinelemeli olarak da yazılabilir; bunun tersi de geçerlidir. Özyinelemeli sürüm çoğu zaman problemin matematiksel tanımını daha yakından yansıtırken yinelemeli sürüm bellek üzerinde açık denetim sağlar ve yığın taşması risklerini önler. Aralarından seçim yapmak; okunabilirlik, derinlik sınırları ve performans gereksinimlerine dayanan pratik bir karardır.
Mülakatlarda her iki sürümü de sunabilmek ve ödünleşimleri açıklayabilmek, konuya hâkimiyetinizin güçlü bir göstergesidir.
Faktöriyel: Özyinelemeli ve Yinelemeli
Faktöriyel, bunun temel örneğidir. Özyinelemeli sürüm, n! = n × (n-1)! matematiksel tanımını doğrudan kodlar. Bekleyen n dönüş değeri nedeniyle O(n) yığın alanı kullanır. Yinelemeli sürüm, 1'den n'ye kadar döngü kullanır ve O(1) alan kullanır. n = 1000 için özyinelemeli sürüm Python'ın varsayılan sınırına ulaşır; yinelemeli sürüm ise keyfi büyüklükteki n değerlerini işleyebilir.
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1) # O(n) stack
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # O(1) stack
return result
print(factorial_rec(10)) # 3628800
print(factorial_iter(10)) # 3628800
# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0) # True (Python handles big ints)Fibonacci: Üstel mi Doğrusal mı
Saf özyinelemeli Fibonacci'nin zaman karmaşıklığı O(2^n)'dir; büyük n değerlerinde son derece yavaştır. Yinelemeli sürüm O(n) zamanda ve O(1) alanda çalışır. Önbellek kullanan özyineleme (gelecek derste) de O(n) zamanda çalışır, ancak önbellek sözlüğü ve O(n) boyutundaki yığın nedeniyle O(n) alan kullanır. Fibonacci için yinelemeli yaklaşım tüm ölçütlerde en iyi seçenektir. n = 50 için saf özyineleme saniyeler sürerken yineleme mikrosaniyeler içinde tamamlanır.
import time
def fib_rec(n):
if n <= 1: return n
return fib_rec(n-1) + fib_rec(n-2) # O(2^n)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time, O(1) space
# Timing comparison for n=35
start = time.time()
fib_rec(35)
print(f'Recursive n=35: {time.time()-start:.3f}s')
start = time.time()
fib_iter(35)
print(f'Iterative n=35: {time.time()-start:.6f}s')
print(fib_iter(100)) # handles large nAğaçta Gezinme: Özyinelemeli ve Yinelemeli
Özyinelemeli ağaçta gezinme, ağaç yapısı özyinelemeyi doğal olarak yansıttığı için genellikle temizdir. Ancak derinliği fazla ve tek yöne çarpık bir ağaçta (temelde bağlı bir liste gibi) özyineleme derinliği ağacın yüksekliğine, yani O(n)'e eşit olur ve yığın taşması riski doğar. Açık bir yığın kullanan yinelemeli sürümde derinlik sınırı yoktur; yığın boyutunun çağrı yığını yerine öbekte büyümesine olanak tanır.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
def preorder_rec(root, result=None):
if result is None: result = []
if root:
result.append(root.val)
preorder_rec(root.left, result)
preorder_rec(root.right, result)
return result
def preorder_iter(root):
if not root: return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_rec(root)) # [1, 2, 4, 5, 3]
print(preorder_iter(root)) # [1, 2, 4, 5, 3]Birleştirmeli Sıralama: Özyinelemeli ve Yinelemeli (Alttan Üste)
Birleştirmeli sıralama doğal olarak özyinelemelidir (böl, özyinelemeli olarak işle, birleştir). Yinelemeli alttan üste birleştirmeli sıralama özyinelemeyi tamamen ortadan kaldırır: 1 boyutundaki alt dizilerle başlar, bitişik çiftleri 2 boyutundaki alt dizilerde birleştirir, ardından 4 boyutuna geçer ve her turda alt dizi boyutunu iki katına çıkarır. Alttan üste birleştirmeli sıralamanın zaman karmaşıklığı O(n log n), alan karmaşıklığı O(n) (birleştirme arabelleği için) ve yığın alanı O(1)'dir.
def merge_sort_iterative(arr):
n = len(arr)
size = 1
while size < n:
for start in range(0, n, 2 * size):
mid = min(start + size, n)
end = min(start + 2 * size, n)
left = arr[start:mid]
right = arr[mid:end]
# Merge
i = j = 0
for k in range(start, end):
if i < len(left) and (j >= len(right) or left[i] <= right[j]):
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
size *= 2
return arr
print(merge_sort_iterative([5, 2, 4, 6, 1, 3])) # [1,2,3,4,5,6]Özyinelemenin Açıkça Daha İyi Olduğu Durumlar
Özyineleme; problemin çağrı grafiğine doğrudan uyan bir ağaç benzeri yapıya sahip olduğu, temel durumların doğal olduğu ve derinliğin sınırlı kaldığı (dengeli ağaçlarda ve böl ve yönet yaklaşımında O(log n)) durumlarda öne çıkar. Örnekler: JSON ayrıştırma, dizinlerde gezinme, oyun ağaçları ve geri izleme problemleri. Bu durumlarda özyinelemeli kod, eşdeğer yinelemeli sürümden daha kısa, daha anlaşılır ve doğruluğunu kanıtlaması daha kolaydır.
# Recursion is clearest for JSON-like nested structures
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse on sub-list
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
print(flatten([])) # []
print(flatten([[1, [2]], [3, [4, [5]]]])) # [1, 2, 3, 4, 5]Yinelemenin Açıkça Daha İyi Olduğu Durumlar
Şu durumlarda yinelemeyi tercih etmelisiniz: derinlik O(n) ve n büyükse (güvenli Python kodunda yaklaşık 500'den fazlaysa), özyinelemeli ve yinelemeli sürümler eşit derecede okunabilirse (Fibonacci, faktöriyel) veya problem, doğal bir alt problem ayrıştırması olmayan, temelde sıralı bir işlemse. Dizileri soldan sağa işleyen basit döngüler — birikimli toplamlar, kayan pencereler, iki işaretçi — her zaman yinelemeli olmalıdır.
# Iterative is clearest for sequential array processing
def running_max(nums):
result = []
curr_max = float('-inf')
for n in nums:
curr_max = max(curr_max, n)
result.append(curr_max)
return result
print(running_max([3, 1, 4, 1, 5, 9, 2, 6])) # [3,3,4,4,5,9,9,9]
# No natural recursion here — iteration is the only sensible choiceDFS Özyinelemesini Yinelemeye Dönüştürme
Sistematik yaklaşım şudur: her özyinelemeli DFS, özyinelemeli çağrının bağımsız değişkenleri açık bir yığına eklenerek yinelemeli hâle getirilebilir. Temel fikir, f(args) özyinelemeli çağrısının args değerlerini yığına ekleyip döngüye girmeye eşdeğer olmasıdır. Son sıralı işleme için (ebeveyn düğümden önce çocukların sonuçlarına ihtiyaç duyduğunuzda) iki geçişli bir yaklaşım veya ziyaret edildi bayrağı gerekebilir.
# Post-order iterative using two stacks
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val=val; self.left=left; self.right=right
def postorder_iter(root):
if not root: return []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left: s1.append(node.left)
if node.right: s1.append(node.right)
return s2[::-1] # reverse gives post-order
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(postorder_iter(root)) # [4, 5, 2, 3, 1]Özyinelemenin Performans Ek Yükü
Python'daki her özyinelemeli çağrının kayda değer bir ek yükü vardır: yeni bir çerçeve oluşturulur (öbekte bellek ayrılır), yerel değişkenler başlatılır ve bir dönüş adresi işaretçisi saklanır. Karşılaştırmalı ölçümler, Python'da işlev çağrısı ek yükünün çağrı başına yaklaşık 100–200 nanosaniye olduğunu gösterir. Özyineleme derinliği 10^6 olduğunda bu, algoritmanın yaptığı işten bağımsız olarak yalnızca ek yük nedeniyle 0,1–0,2 saniyeye ulaşır. Yinelemeli döngüler bu ek yükü tamamen ortadan kaldırır.
import time
def rec_sum(n):
if n == 0: return 0
return n + rec_sum(n - 1)
def iter_sum(n):
total = 0
for i in range(n + 1):
total += i
return total
import sys; sys.setrecursionlimit(10000)
n = 5000
start = time.time()
for _ in range(100): rec_sum(n)
print(f'Recursive sum({n}) x100: {(time.time()-start)*1000:.2f}ms')
start = time.time()
for _ in range(100): iter_sum(n)
print(f'Iterative sum({n}) x100: {(time.time()-start)*1000:.2f}ms')Bir Mülakatta Karar Verme
Bir kodlama mülakatında seçme şansınız varsa şu soruları sorun: 'Özyineleme derinliği O(log n) ile sınırlı mı?' Evetse özyineleme uygundur. 'Özyineleme derinliği O(n) mi?' — yinelemeyi tercih edin veya üretim ortamında bunu yinelemeli hâle getireceğinizi belirtin. 'Problem doğal olarak ağaç biçiminde mi veya böl ve yönet yaklaşımına mı dayanıyor?' — özyinelemeye yönelin. 'Problem sıralı bir tarama mı?' — yinelemeyi kullanın.
Gerekçenizi her zaman açıkça belirtin: 'Burada özyineleme kullanacağım; çünkü dengeli bir BST için derinlik O(log n) ve O(log n) yığın alanı kabul edilebilir.'
Özet: Ödünleşim Tablosu
Ödünleşimleri özetlersek: özyinelemeli kod genellikle daha kısadır ve problemin yapısını yansıtır; ancak O(derinlik) yığın alanı kullanır ve işlev çağrısı ek yüküne sahiptir. Yinelemeli kod daha uzundur; buna karşılık O(1) yığın alanı kullanır ve özyineleme sınırlarını aşmaz. Önbelleğe alınmış özyineleme (sonraki ders) orta yolu sunar: özyinelemenin açıklığını korurken gereksiz yeniden hesaplamayı ortadan kaldırır. Çözümünüzü analiz ederken çağrı yığını alanı da dâhil olmak üzere alan karmaşıklığını her zaman açıkça belirtin.
rows = [
('Factorial', 'O(n) / O(1)', 'O(n) / O(1)', 'Same time; iter wins on space'),
('Fibonacci', 'O(2^n) / O(n)', 'O(n) / O(1)', 'Iter massively wins'),
('Binary search','O(log n) / O(log n)', 'O(log n) / O(1)', 'Iter wins on space'),
('Tree DFS', 'O(n) / O(h)', 'O(n) / O(h)', 'Equal; rec cleaner'),
('Merge sort', 'O(n log n) / O(log n)', 'O(n log n) / O(1)', 'BU-iter wins on stack'),
]
for name, rec, it, note in rows:
print(f'{name:<15} rec={rec:<22} iter={it:<22} {note}')Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: derinlik O(log n) olduğunda veya problem doğal olarak ağaç biçiminde olduğunda özyineleme; derinlik O(n) olduğunda veya problem sıralı olduğunda yineleme tercih edilir, naif özyinelemeli Fibonacci'nin zaman karmaşıklığı O(2^n)'dir — yinelemeli sürümün zaman karmaşıklığı O(n), alan karmaşıklığı O(1)'dir ve her özyinelemeli DFS, öbekte açık bir yığın yönetilerek yinelemeli hâle getirilebilir. Sırada, gereksiz özyinelemeli çağrıları ortadan kaldırmak için anımsamayı uygulayacağız.
Sıkça Sorulan Sorular
“Özyinelemeli ve Yinelemeli Yaklaşımların Ödünleşimleri” dersi ücretsiz mi?
Evet — “Özyinelemeli ve Yinelemeli Yaklaşımların Ödünleşimleri” 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.
“Özyinelemeli ve Yinelemeli Yaklaşımların Ödünleşimleri” dersinde ne öğreneceğim?
Özyinelemeli faktöriyel ve Fibonacci çözümlerini yinelemeli döngülere dönüştürün; Python’un özyineleme sınırı ve yığın boyutunun yinelemeli yaklaşımı ne zaman tercih edilir kıldığını açıklayı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.
“Özyinelemeli ve Yinelemeli Yaklaşımların Ödünleşimleri” 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
- Özyineleme Çerçevesi: Temel Durum, Güven, Oluşturma
- Çağrı Yığınını Görselleştirme
- Özyinelemeli ve Yinelemeli Yaklaşımların Ödünleşimleri
- Not Alma: Özyinelemeli Sonuçları Önbelleğe Alma