Çağrı Yığınını Görselleştirme
Yığın çerçevelerinin büyüyüp küçülmesini gözlemlemek için Python’un sys modülünü ve yazdırma izlemeyi kullanın; derin özyinelemedeki yığın taşması risklerini anlayın.
Çağrı Yığınını Görselleştirme, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. 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.
Çağrı Yığını Nedir
Python'daki her işlev çağrısı, çağrı yığını üzerinde bir yığın çerçevesi oluşturur. Çerçeve, işlevin yerel değişkenlerini, dönüş adresini (işlev döndükten sonra yürütmenin devam edeceği yeri) ve geçerli komut göstergesini saklar. Bir işlev döndüğünde çerçevesi yığından çıkarılır ve denetim çağıran işleve geri verilir. Her çağrıyla çağrı yığını aşağı doğru büyür, her dönüşle küçülür.
Çağrı yığınını anlamak, özyinelemeli kodda hata ayıklamak, bellek kullanımını tahmin etmek ve derin özyinelemede yığın taşması hatalarından kaçınmak için gereklidir.
import traceback
def outer():
inner()
def inner():
# Print the current call stack
traceback.print_stack()
outer()
# Shows: module -> outer -> innersys ile Yığın Çerçevelerini Gözlemleme
Python'ın sys modülü, çalışma zamanında çağrı yığınını incelemek için araçlar sağlar. sys._getframe(n), geçerli işlevin n seviye üzerindeki yığın çerçevesini döndürür. Her çerçevede yerel değişkenleri içeren bir f_locals sözlüğü ve işlev adı için f_code.co_name bulunur. Özyinelemeli bir işlevin içine hata ayıklama çıktıları eklemek, çerçevelerin nasıl biriktiğini ve çözüldüğünü ortaya çıkarır.
import sys
def countdown(n):
depth = 0
frame = sys._getframe(0)
while frame:
depth += 1
frame = frame.f_back
print(' ' * (n * 2) + f'countdown({n}) called, stack depth={depth}')
if n <= 0:
return
countdown(n - 1)
print(' ' * (n * 2) + f'countdown({n}) returning')
countdown(3)Çağrı Yığınında factorial İzini Sürme
factorial(4) çağrısını çağrı yığını üzerinde izleyin. Çağrılar birikir: factorial(4), factorial(3)'ü; factorial(3), factorial(2)'yi; factorial(2), factorial(1)'i; factorial(1) ise factorial(0)'ı çağırır. Temel durumda yığında 5 çerçeve vardır. Dönüşlerle yığın çözülür: factorial(0), 1 döndürür; factorial(1), 1×1=1 döndürür; factorial(2), 2×1=2 döndürür; factorial(3), 3×2=6 döndürür; factorial(4), 4×6=24 döndürür. Derinlik n+1'e eşittir ve alan karmaşıklığı O(n)'dir.
def factorial(n, indent=0):
prefix = ' ' * indent
print(prefix + f'-> factorial({n})')
if n == 0:
print(prefix + '<- returns 1')
return 1
result = n * factorial(n - 1, indent + 1)
print(prefix + f'<- returns {result}')
return result
factorial(4)Yığın Taşması: Python'ın Özyineleme Sınırı
Python, çağrı yığını sınırını aştığında RecursionError oluşturur (varsayılan olarak yaklaşık 1000 çerçeve). Bu, sonsuz özyinelemenin tüm belleği tüketmesini önler. Girdi boyutunun n = 10^4 veya daha fazla olduğu problemlerde, derinliği O(n) olan özyinelemeli bir çözüm sınır artırılmadan çöker. Yinelemeli karşılık yalnızca kapsayıcı işlev için tek bir çerçeve kullandığından O(1) yığın alanına sahiptir.
import sys
print('Recursion limit:', sys.getrecursionlimit())
def deep_recursion(n):
if n == 0:
return 0
return 1 + deep_recursion(n - 1)
# Safe: within limit
try:
print(deep_recursion(900))
except RecursionError:
print('Overflow at 900')
# Overflow
try:
print(deep_recursion(2000))
except RecursionError:
print('RecursionError at 2000 — limit exceeded!')Özyineleme Sınırını Artırma
sys.setrecursionlimit(n) ile Python'ın özyineleme sınırını artırabilirsiniz, ancak bu geçici bir çözümdür. Varsayılan sınırın bulunmasının nedeni, her yığın çerçevesinin bellek kullanmasıdır (CPython'da genellikle birkaç yüz bayt). Sınırı 10^6 olarak ayarlayıp ardından 10^5 derinliğinde bir özyineleme çağırmak, yüzlerce megabaytlık yığın alanı ayırabilir. Genellikle doğru çözüm, yinelemeli bir çözüme dönüştürmek veya derinliği azaltmak için önbellekleme kullanmaktır.
import sys
# Only increase when you are certain of the maximum depth
# and have confirmed it is safe
original = sys.getrecursionlimit()
sys.setrecursionlimit(5000)
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
print(sum_to(3000)) # Works with increased limit
sys.setrecursionlimit(original) # restore
print('Limit restored:', sys.getrecursionlimit())Karşılıklı Özyinelemede Çağrı Yığını
Karşılıklı özyineleme, A işlevinin B işlevini, B işlevinin de A işlevini çağırmasıdır. Çağrı yığını, A ve B'nin çerçeveleri arasında dönüşümlü olarak ilerler. Bu örüntü, çift/tek sayı belirlemede ve durum makinesi benzetimlerinde görülür. Yığın derinliği sınırlı kaldığı sürece doğrudur; ancak derinliği anlamak, basit doğrusal özyinelemeye göre daha zor olabilir.
def is_even(n):
if n == 0:
return True
return is_odd(n - 1)
def is_odd(n):
if n == 0:
return False
return is_even(n - 1)
# Stack alternates: is_even(4)->is_odd(3)->is_even(2)->is_odd(1)->is_even(0)
print(is_even(4)) # True
print(is_odd(5)) # True
print(is_even(7)) # FalseKuyruk Çağrıları ve Python'ın Bunları Neden İyileştirmediği
Kuyruk çağrısı, dönüşten önceki son işlem olan özyinelemeli çağrıdır; bu çağrının ardından başka bir hesaplama yapılmaz. Haskell veya Scheme gibi dillerde kuyruk çağrıları döngülere dönüştürülerek optimize edilir (kuyruk çağrısı optimizasyonu, TCO) ve böylece O(1) yığın alanı sağlanır. Python, TCO'yu bilinçli olarak uygulamaz. Guido van Rossum'un açıkladığı gibi, hata ayıklama için tam yığın izini korumak, bellek tasarrufundan daha değerliydi. Bu nedenle Python'da kuyruk özyinelemesi kullanan kod yine O(n) yığın alanı kullanır.
# Tail-recursive factorial (accumulator pattern)
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, acc * n) # tail call
# In Python, this still uses O(n) stack space (no TCO)
# But it IS semantically tail-recursive
print(factorial_tail(6)) # 720
print(factorial_tail(10)) # 3628800
# Iterative version: same logic, O(1) stack
def factorial_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(factorial_iter(10)) # 3628800Özyineleme Ağaçlarını Yazdırma
Özyineleme ağacını görselleştirmek, yinelenen alt problemlerin nerede ortaya çıktığını belirlemeye yardımcı olur; bunlar önbelleklemenin hedefidir. Ağacı yazdırmanın basit bir yolu, her seviyede 2 boşluk artan bir indent parametresi eklemektir. Her çağrı, girişte bağımsız değişkenlerini ve çıkışta dönüş değerini yazdırır. Bunu Fibonacci(5) için çalıştırmak, üstel dallanmayı ve yinelenen çağrıları açıkça gösterir.
def fib_traced(n, indent=0):
prefix = ' ' * indent
print(prefix + f'fib({n})')
if n <= 1:
print(prefix + f'=> {n}')
return n
result = fib_traced(n-1, indent+1) + fib_traced(n-2, indent+1)
print(prefix + f'=> {result}')
return result
fib_traced(4)
# Shows the branching tree with duplicated sub-problemsYığın Derinliği = Alan Karmaşıklığı
Her özyinelemeli işlev için, çağrı yığınının en fazla derinliği yürütme sırasında ulaşılan en büyük özyineleme derinliğine eşittir. Bu derinlik, yardımcı alan karmaşıklığına doğrudan eşittir. Doğrusal özyinelemede (factorial, Fibonacci, dizeyi ters çevirme) derinlik O(n)'dir. Böl ve yönet algoritmalarında (birleştirmeli sıralama, ikili arama) derinlik O(log n)'dir. Ağaç dolaşımlarında derinlik, h ağaç yüksekliği olmak üzere O(h)'dir (dengeli ağaçta O(log n), en kötü durumda O(n)).
# Recursion depth = space complexity
# Linear recursion: O(n) stack
def linear_depth(n):
if n == 0: return 0
return 1 + linear_depth(n - 1) # depth = n
# Logarithmic recursion: O(log n) stack
def log_depth(n):
if n <= 1: return 0
return 1 + log_depth(n // 2) # depth = log2(n)
print('n=32 linear depth:', 32)
print('n=32 log depth:', log_depth(32)) # 5
print('n=1024 log depth:', log_depth(1024)) # 10Özyinelemeyi Açık Bir Yığınla Yinelemeye Dönüştürme
Her özyinelemeli algoritma, çağrı yığınını bir Python listesiyle açıkça yöneterek yinelemeli hâle getirilebilir. Çerçeveleri OS'nin yönetmesine izin vermek yerine, 'görevleri' listeye eklersiniz ve bunları bir döngüde pop edersiniz. Bu yaklaşım Python'ın özyineleme sınırını ortadan kaldırır ve çerçeve başına ek yükü azaltır; karşılığında kod daha karmaşık hâle gelir. Daha önce gördüğümüz açık yığın kullanan yinelemeli DFS, tam olarak bu örüntüyü izler.
# Recursive inorder traversal -> iterative with explicit stack
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
print(inorder_iterative(root)) # [1, 2, 3, 4, 6]Özet: Çağrı Yığını ve Alan
Çağrı yığını, tüm özyinelemenin arkasındaki gizli veri yapısıdır. Derinliği, özyinelemeli algoritmanızın alan karmaşıklığına eşittir. Python bunu yaklaşık 1000 ile sınırlar; bu nedenle özyineleme derinliği O(n) olan algoritmaların ya sınırı artırması (riskli) ya da yinelemeli olarak yeniden yazılması gerekir. Mülakatlarda özyinelemeli kod yazarken çağrı yığını nedeniyle oluşan alan karmaşıklığını her zaman belirtin: 'Bu, özyineleme derinliği için O(n) alan kullanır' veya 'dengeli bir ağaçta gezinme için O(log n) alan kullanır'.
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: her özyinelemeli çağrı, yerel değişkenleri ve dönüş adresini tutan bir yığın çerçevesi oluşturur; en büyük yığın derinliği, özyinelemenin yardımcı alan karmaşıklığına eşittir; ayrıca Python'ın özyineleme sınırı (yaklaşık 1000), derinliği O(n) olan algoritmaları büyük n değerleri için riskli hâle getirir; bunları açık bir yığın kullanarak yinelemeli hâle dönüştürün. Sırada özyinelemeli ve yinelemeli çözümleri karşılaştıracak, her birinin ne zaman kullanılacağını ele alacağız.
Sıkça Sorulan Sorular
“Çağrı Yığınını Görselleştirme” dersi ücretsiz mi?
Evet — “Çağrı Yığınını Görselleştirme” 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.
“Çağrı Yığınını Görselleştirme” dersinde ne öğreneceğim?
Yığın çerçevelerinin büyüyüp küçülmesini gözlemlemek için Python’un sys modülünü ve yazdırma izlemeyi kullanın; derin özyinelemedeki yığın taşması risklerini anlayı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 2. dersidir.
“Çağrı Yığınını Görselleştirme” 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
- Ö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