Recursion ve Backtracking Nedir? Recursion Lab ile Call Stack’i Görün

Bir fonksiyonun kendisini çağırması ilk bakışta küçük bir kod hilesi gibi görünür. Oysa recursion; tree traversal, divide-and-conquer, dynamic programming ve backtracking gibi pek çok algoritmik fikrin ortak dilidir. Zorluk çoğu zaman kodu yazmak değil, her çağrının kendi parametrelerini ve dönüş noktasını nasıl koruduğunu zihinde takip etmektir.

Websoftik Academy Recursion Lab, recursive call’ları yalnızca bir çıktı listesi olarak göstermez. Call stack, call tree, return propagation ve backtracking kararlarını aynı deterministik timeline üzerinde görünür kılar. Böylece “fonksiyon yeniden çağrıldı” cümlesi somut bir çalışma modeline dönüşür.

Recursion veya özyineleme, bir problemin daha küçük örneklerini yine aynı fonksiyonla çözme tekniğidir. Sağlam bir recursive çözüm iki parçaya ihtiyaç duyar: doğrudan cevaplanan bir base case ve problemi bu duruma yaklaştıran bir recursive step.

factorial(4) tek bir işlem değildir. Önce 4, 3, 2 ve 1 için ayrı çağrılar açılır; ardından sonuçlar ters yönde 1, 2, 6 ve 24 olarak yayılır. Recursion Lab tam olarak bu iki yönlü akışı gösterir.

Recursion & Backtracking Lab, recursion foundations’tan constraint arena’ya uzanan altı öğrenme modülü sunar. Countdown, factorial, GCD, Fibonacci, binary search ve Tower of Hanoi dahil 12 recursion örneği; powerset, permutation, subset sum, N-Queens ve word search dahil 7 backtracking örneği bulunur.

Her olay kararlı bir call ID taşır. Bu kimlik, call stack’teki frame ile call tree’deki node’un aynı çağrı olduğunu kanıtlar. Aktif kod satırı, parametre, local state, çıktı ve dönüş değeri birlikte ilerlediği için bir paneldeki değişimin diğer paneldeki karşılığını kaybetmezsiniz.

Base case yazmak tek başına sonlanma garantisi değildir. Her çağrının o base case’e doğru ilerlediğini gösteren bir progress measure gerekir. Factorial için bu ölçü azalan n, binary search için küçülen aralık, tree traversal için ziyaret edilecek daha küçük subtree’dir.

Parametre hiç değişmiyorsa veya yanlış yönde değişiyorsa base case erişilebilir olsa bile çağrı zinciri ona ulaşmayabilir. Lab, call ve base-case event’lerini ayırarak sonsuz recursion’a götüren bu mantık hatasını erken fark ettirir.

Her aktif fonksiyon çağrısı için stack üzerinde bir frame tutulur. Frame; parametreleri, local değişkenleri ve alt çağrı döndüğünde devam edilecek noktayı taşır. Yeni çağrı stack’in üstüne eklenir; base case’e ulaşıldığında frame’ler LIFO sırasıyla kapanır.

Lab’in Call Stack Laboratory modülü frame push, continuation ve pop anlarını ayrı adımlara böler. Böylece recursive programın neden “önce aşağı indiğini, sonra yukarı çıktığını” yalnızca metaforla değil state değişimleriyle görürsünüz.

Recursive çağrıdan dönen değer doğrudan en dış çağrıya sıçramaz. Her frame kendi bekleyen ifadesini tamamlar ve sonucu parent frame’e aktarır. Factorial örneğinde factorial(1) değeri 1’dir; üst frame bunu 2 ile, sonraki 3 ile, en dış frame 4 ile çarpar.

Countdown ve count-up örnekleri de output satırının recursive çağrıdan önce veya sonra yerleştirilmesinin sonucu neden ters çevirdiğini gösterir. Kod satırlarının sırası, stack’in unwind aşamasında görünür davranışa dönüşür.

Call stack yalnızca o anda aktif olan yolu tutar. Recursion tree ise üretilmiş bütün çağrıları ve aralarındaki parent-child ilişkisini korur. Fibonacci gibi birden fazla recursive branch açan fonksiyonlarda aynı alt problemin tekrar tekrar hesaplandığı bu görünümde belirginleşir.

Lab aktif path’i bütün generated call’lardan ayırır. Bu ayrım, stack space ile toplam çalışma miktarının aynı şey olmadığını anlamanın en kısa yoludur: tree’de çok sayıda node bulunurken aynı anda stack’te yalnızca bir derinlik yolu aktif olabilir.

Birçok recursive algoritma loop ve explicit stack kullanılarak iterative hale getirilebilir. Recursion kontrol akışını dilin call stack’ine bırakırken, iteration state’i açıkça program içinde yönetir. Hangisinin daha iyi olduğu; okunabilirlik, maksimum derinlik ve bellek sınırı gibi koşullara bağlıdır.

Tree DFS’de recursion yapının kendisini doğal biçimde yansıtır. Çok derin veya kullanıcı kontrollü input’larda ise explicit stack, stack overflow riskini yönetmeyi kolaylaştırabilir. Tree temellerini ayrıca Trees & BST Lab rehberinde çalışabilirsiniz.

Tail position, recursive çağrı döndükten sonra yapılacak başka iş kalmaması demektir. Bu yapısal bir özelliktir; otomatik olarak constant stack garantisi vermez. C ve C++ tail-call elimination’ı zorunlu kılmaz, Python ise normal çağrı frame’lerini korur.

Bu nedenle bellek garantisi gerekiyorsa kullandığınız dil ve runtime’ı bilmeden “tail recursion O(1) space’tir” denmemelidir. Lab’in Recursion vs Iteration modülü tail position ile gerçek çalışma zamanı davranışını ayırır.

Backtracking, olası kararları sistematik biçimde deneyen bir state-space search yöntemidir. Bir seçim yapılır, sonuçları araştırılır; seçim geçersiz veya yetersizse state geri alınır ve sıradaki seçenek denenir. Amaç yalnızca recursion kullanmak değil, karar ağacını kontrollü biçimde gezmektir.

Choose state’i değiştirir, explore yeni state’ten devam eder, unchoose ise mutation’ı geri alır. Unchoose unutulursa sibling branch önceki branch’in state’ini miras alır. Lab bu üç olayı ayrı renk ve event türleriyle göstererek en sık backtracking bug’larından birini görünür kılar.

Bir partial solution’ın geçerli tamamlanma üretemeyeceği biliniyorsa o subtree’yi hiç açmamak pruning’dir. Doğru pruning sonucu değiştirmez; yalnızca gereksiz branch’leri eler. Constraint Arena, explore ve reject olaylarını ayırarak hangi koşulun kaç aday çağrıyı engellediğini gösterir.

N-Queens’te her satıra bir queen yerleştirirken aynı sütun ve diagonal çatışmaları anında prune edilir. Subset Sum’da ise her eleman için dahil etme veya etmeme branch’i açılır; hedef ve kalan değerler güvenli sınırlar sağlıyorsa arama erkenden kesilebilir. Word Search de board üzerindeki ziyaret state’inin choose ve unchoose arasında doğru geri alınmasını öğretir.

Complexity yalnızca stack depth’e bakılarak bulunmaz. Tek branch’li factorial Θ(n) çağrı üretirken naive Fibonacci yaklaşık üstel sayıda çağrı üretebilir. Divide-and-conquer algoritmalarında branch sayısı, alt problem boyutu ve her seviyedeki ek iş birlikte değerlendirilir.

Call tree’den recurrence çıkarma ve büyüme sınıflarını doğrulama için Big-O Complexity Lab rehberine; recursive merge sort örneği için Sorting Lab rehberine geçebilirsiniz.

Hazırsanız Recursion Lab’i açın. Diğer interaktif çalışma alanları ve konu rehberleri için Academy Lab kataloğunu inceleyebilirsiniz.