Belajar Data Structure - Rekursi & Stack Frame

#Pendahuluan

Setelah di episode 3 kita memahami array, dynamic array, string, dan pattern seperti sliding window serta two-pointer, pada episode ini kita mempelajari rekursi — teknik pemrograman di mana fungsi memanggil dirinya sendiri. Rekursi bukan hanya trik keren — ia adalah fondasi dari tree traversal, divide-and-conquer, dan backtracking yang akan kita gunakan berulang kali sepanjang series ini.

Banyak programmer pemula merasa takut dengan rekursi karena terasa "circular" — bagaimana fungsi bisa memanggil dirinya sendiri tanpa infinite loop? Kunci pemahamannya ada di stack frame — setiap panggilan rekursif membuat frame baru di call stack, dan base case memastikan rekursi berhenti. Memahami stack frame adalah memahami "stacks in action" — dan ini akan membantu kalian saat belajar stack secara formal di episode 6.

#Base Case & Recursive Case

#Base Case

Base case adalah kondisi berhenti dari rekursi — titik di mana fungsi mengembalikan nilai tanpa memanggil dirinya sendiri lagi. Tanpa base case yang benar, rekursi akan berjalan tanpa hingga (infinite recursion) dan menyebabkan stack overflow.

#Recursive Case

Recursive case adalah bagian di mana fungsi memanggil dirinya sendiri dengan input yang lebih kecil, mendekati base case. Setiap panggilan harus membawa input lebih dekat ke base case.

Rekursi factorial

def factorial(n):
    # Base case
    if n <= 1:
        return 1
    # Recursive case
    return n * factorial(n - 1)

Faktorial dari 5 bekerja seperti ini:

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

#Fibonacci: Rekursi yang Inefisien

Rekursi Fibonacci (naive)

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Versi ini memiliki kompleksitas O(2^n) — sangat lambat untuk n besar karena banyak subproblem yang dihitung berulang kali. Ini motivasi untuk teknik memoization dan dynamic programming yang akan dibahas di series algoritma.

#Call Stack Internal

#Bagaimana Rekursi Bekerja di Balik Layar

Setiap kali fungsi dipanggil — baik secara rekursif maupun biasa — komputer membuat stack frame di call stack. Frame ini berisi:

• Parameter fungsi
• Variabel lokal
• Alamat return (ke mana harus kembali setelah fungsi selesai)

Ketika base case tercapai, frame-frame ini dilepas satu per satu (unwinding) dan nilai dikembalikan ke pemanggil.

#Visualisasi di PythonTutor

Buka PythonTutor (pythontutor.com) dan tempel kode berikut:

Rekursi untuk divisualisasikan

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)
 
result = power(2, 4)
print(result)

Perhatikan bagaimana PythonTutor menampilkan empat frame power di call stack saat eksekusi mencapai power(2, 0). Setelah base case tercapai, frame-frame ini dilepas satu per satu.

#Menghitung Jumlah Frame

Untuk input n yang berbeda, jumlah stack frame berbeda:

Setiap frame memakan memori. Jika rekursi terlalu dalam (ribuan frame), Python akan menghasilkan RecursionError: maximum recursion depth exceeded.

#Tail Recursion

#Apa Itu Tail Recursion?

Tail recursion terjadi ketika panggilan rekursif adalah operasi terakhir dalam fungsi — tidak ada operasi lain setelahnya. Beberapa bahasa (Scheme, Haskell) bisa mengoptimasi tail recursion agar tidak menambah frame baru (tail call optimization), tetapi Python tidak mendukung ini.

Tail recursion vs non-tail

def factorial_tail(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)
 
def factorial_normal(n):
    if n <= 1:
        return 1
    return n * factorial_normal(n - 1)

Dalam factorial_normal, ada operasi perkalian setelah panggilan rekursif — frame harus tetap ada untuk menunggu hasilnya. Dalam factorial_tail, panggilan rekursif adalah operasi terakhir.

#Python Tidak Optimasi Tail Recursion

Meskipun Python tidak mengoptimasi tail recursion, memahami konsep ini tetap penting karena:

• Banyak bahasa lain (Go, C) mendukung tail call optimization
• Konsep ini membantu kalian menulis kode yang lebih efisien
• Memahami mengapa stack frame diperlukan atau tidak

#Rekursi dan Koneksi ke DS

#Tree Traversal

Tree traversal — in-order, pre-order, post-order, level-order — semuanya berbasis rekursi. Setiap node diakses dengan memanggil fungsi rekursif untuk subtree kiri dan kanan. Tanpa rekursi, tree traversal akan jauh lebih kompleks untuk ditulis.

#Divide-and-Conquer

Divide-and-conquer memecah masalah menjadi sub-masalah yang lebih kecil, menyelesaikan masing-masing secara rekursif, lalu menggabungkan hasilnya. Binary search, merge sort, dan quicksort adalah contoh klasik.

#Backtracking

Backtracking menggunakan rekursi untuk menjelajahi semua kemungkinan solusi, mundur (backtrack) saat menemui jalan buntu. N-queen, maze solving, dan sudoku solver menggunakan teknik ini.

#Praktik: Visualisasikan Rekursi

Rekursi dengan tracing

def fibonacci_trace(n, depth=0):
    indent = "  " * depth
    print(f"{indent}fibonacci({n}) dipanggil")
 
    if n <= 1:
        print(f"{indent}  -> return {n}")
        return n
 
    left = fibonacci_trace(n - 1, depth + 1)
    right = fibonacci_trace(n - 2, depth + 1)
    result = left + right
    print(f"{indent}  -> return {result}")
    return result
 
fibonacci_trace(4)

Jalankan kode ini dan perhatikan pola tree yang terbentuk — ini adalah visualisasi dari tree rekursif Fibonacci. Setiap panggilan adalah node, dan recursive call adalah children.

#Penutup

Inti yang harus dibawa pulang:

• Rekursi = fungsi memanggil dirinya sendiri; base case adalah kondisi berhenti.
• Setiap panggilan rekursif membuat stack frame baru di call stack.
• Tail recursion = panggilan rekursif sebagai operasi terakhir (Python tidak optimasi).
• Rekursi adalah fondasi untuk tree traversal, divide-and-conquer, dan backtracking.
• Gunakan PythonTutor untuk memvisualisasikan stack frame dan memahami alur eksekusi.

Di episode 5 selanjutnya kita akan memasuki Fase 2: Struktur Linear dengan membahas linked list — singly, doubly, circular; operasi insert, delete, reverse, dan cycle detection. Linked list adalah kebalikan dari array: tidak ada random access, tetapi insert di head sangat cepat. Pastikan kalian sudah paham rekursi karena reverse linked list bisa dilakukan secara rekursif!