Memvisualisasikan Tumpukan Pemanggilan
Gunakan modul sys Python dan pelacakan dengan print untuk mengamati frame tumpukan yang bertambah dan berkurang, serta memahami risiko stack overflow dalam rekursi mendalam.
Memvisualisasikan Tumpukan Pemanggilan adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa Itu Tumpukan Panggilan?
Setiap panggilan fungsi dalam Python membuat sebuah bingkai tumpukan pada tumpukan panggilan. Bingkai tersebut menyimpan variabel lokal fungsi, alamat pengembaliannya (tempat eksekusi dilanjutkan setelah fungsi selesai), dan penunjuk instruksi saat ini. Ketika fungsi selesai, bingkainya dikeluarkan dari tumpukan dan kendali dikembalikan kepada pemanggil. Tumpukan panggilan bertambah ke bawah pada setiap panggilan dan menyusut pada setiap pengembalian.
Memahami tumpukan panggilan sangat penting untuk menelusuri kesalahan pada kode rekursif, memperkirakan penggunaan memori, dan menghindari kesalahan luapan tumpukan dalam rekursi yang dalam.
import traceback
def outer():
inner()
def inner():
# Print the current call stack
traceback.print_stack()
outer()
# Shows: module -> outer -> innerMengamati Bingkai Tumpukan dengan sys
Modul sys Python menyediakan alat untuk memeriksa tumpukan panggilan saat program berjalan. sys._getframe(n) mengembalikan bingkai tumpukan yang berada n tingkat di atas fungsi saat ini. Setiap bingkai memiliki kamus f_locals yang berisi variabel lokal dan f_code.co_name untuk nama fungsi. Menyisipkan cetakan penelusuran kesalahan di dalam fungsi rekursif memperlihatkan cara bingkai menumpuk dan terurai.
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)Menelusuri factorial pada Tumpukan Panggilan
Telusuri factorial(4) pada tumpukan panggilan. Panggilan menumpuk: factorial(4) memanggil factorial(3), yang memanggil factorial(2), yang memanggil factorial(1), yang memanggil factorial(0). Pada kasus dasar, tumpukan memiliki 5 bingkai. Pengembalian mengurai tumpukan: factorial(0) mengembalikan 1; factorial(1) mengembalikan 1×1=1; factorial(2) mengembalikan 2×1=2; factorial(3) mengembalikan 3×2=6; factorial(4) mengembalikan 4×6=24. Kedalamannya sama dengan n+1, sedangkan kompleksitas ruangnya adalah O(n).
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)Luapan Tumpukan: Batas Rekursi Python
Python memunculkan RecursionError ketika tumpukan panggilan melampaui batasnya (secara bawaan sekitar 1000 bingkai). Ini melindungi program dari rekursi tak terbatas yang menghabiskan seluruh memori. Untuk masalah dengan ukuran masukan n = 10^4 atau lebih, solusi rekursif dengan kedalaman O(n) akan mengalami kerusakan tanpa menaikkan batas tersebut. Versi iteratifnya memiliki ruang tumpukan O(1) karena hanya menggunakan satu bingkai untuk fungsi pembungkusnya.
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!')Menaikkan Batas Rekursi
Anda dapat menaikkan batas rekursi Python dengan sys.setrecursionlimit(n), tetapi ini hanyalah solusi sementara. Batas bawaan tersebut ada karena setiap bingkai tumpukan menggunakan memori (biasanya beberapa ratus bita pada CPython). Menetapkan batas ke 10^6 lalu memanggil rekursi sedalam 10^5 dapat mengalokasikan ruang tumpukan hingga ratusan megabita. Perbaikan yang benar biasanya adalah mengubahnya menjadi solusi iteratif atau menggunakan memoisisasi untuk mengurangi kedalaman.
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())Tumpukan Panggilan untuk Rekursi Timbal Balik
Rekursi timbal balik terjadi ketika fungsi A memanggil fungsi B dan fungsi B memanggil fungsi A. Tumpukan panggilan bergantian antara bingkai A dan B. Pola ini muncul dalam penentuan bilangan genap atau ganjil dan simulasi mesin keadaan. Pola ini benar selama kedalaman tumpukan tetap terbatas—namun kedalamannya dapat lebih sulit dipahami daripada rekursi linear sederhana.
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)) # FalsePanggilan Ekor dan Alasan Python Tidak Mengoptimalkannya
Panggilan ekor adalah panggilan rekursif yang menjadi operasi terakhir sebelum pengembalian—tidak ada perhitungan setelahnya. Dalam bahasa seperti Haskell atau Scheme, panggilan ekor dioptimalkan menjadi perulangan (optimasi panggilan ekor, TCO), sehingga menghasilkan ruang tumpukan O(1). Python sengaja tidak mengimplementasikan TCO. Seperti yang dijelaskan Guido van Rossum, mempertahankan jejak tumpukan lengkap untuk penelusuran kesalahan lebih berharga daripada penghematan ruang. Jadi, dalam Python, kode rekursif ekor tetap menggunakan ruang tumpukan O(n).
# 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)) # 3628800Mencetak Pohon Rekursi
Memvisualisasikan pohon rekursi membantu mengidentifikasi tempat submasalah duplikat muncul (sasaran memoisisasi). Cara sederhana untuk mencetak pohon tersebut adalah menambahkan parameter indent yang bertambah 2 spasi pada setiap tingkat. Setiap panggilan mencetak argumennya saat masuk dan nilai pengembaliannya saat keluar. Menjalankan cara ini untuk Fibonacci(5) memperlihatkan dengan jelas percabangan eksponensial dan panggilan yang berulang.
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-problemsKedalaman Tumpukan = Kompleksitas Ruang
Untuk setiap fungsi rekursif, kedalaman maksimum tumpukan panggilan sama dengan kedalaman rekursi maksimum pada titik mana pun selama eksekusi. Kedalaman ini secara langsung sama dengan kompleksitas ruang tambahan. Untuk rekursi linear (factorial, Fibonacci, pembalikan string), kedalamannya adalah O(n). Untuk algoritme bagi-dan-taklukkan (pengurutan gabung, pencarian biner), kedalamannya adalah O(log n). Untuk penelusuran pohon, kedalamannya adalah O(h), dengan h sebagai height pohon (O(log n) pada pohon seimbang, O(n) pada kasus terburuk).
# 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)) # 10Mengubah Rekursi Menjadi Iterasi dengan Tumpukan Eksplisit
Algoritme rekursif apa pun dapat diubah menjadi iteratif dengan mengelola tumpukan panggilan secara eksplisit menggunakan daftar Python. Alih-alih membiarkan OS mengelola bingkai, Anda mendorong 'tugas' ke dalam daftar lalu melakukan pop terhadapnya dalam sebuah perulangan. Cara ini menghilangkan batas rekursi Python dan mengurangi beban setiap bingkai, dengan konsekuensi kode menjadi lebih kompleks. DFS iteratif menggunakan tumpukan eksplisit yang kita lihat sebelumnya mengikuti pola ini secara tepat.
# 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]Rangkuman: Tumpukan Panggilan dan Ruang
Tumpukan panggilan adalah struktur data tersembunyi di balik semua rekursi. Kedalamannya sama dengan kompleksitas ruang algoritme rekursif Anda. Python membatasinya pada sekitar 1000, sehingga algoritme dengan kedalaman rekursi O(n) memerlukan peningkatan batas (berisiko) atau penulisan ulang menjadi iteratif. Saat menulis kode rekursif dalam wawancara, selalu nyatakan kompleksitas ruang yang disebabkan oleh tumpukan panggilan: 'Ini menggunakan ruang O(n) untuk kedalaman rekursi' atau 'O(log n) untuk penelusuran pohon seimbang'.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: setiap panggilan rekursif membuat bingkai tumpukan yang menyimpan variabel lokal dan alamat pengembalian, kedalaman maksimum tumpukan sama dengan kompleksitas ruang tambahan dari rekursi, dan batas rekursi Python (sekitar 1000) membuat algoritme dengan kedalaman O(n) berisiko untuk n yang besar—ubah menjadi iteratif menggunakan tumpukan eksplisit. Selanjutnya kita akan membandingkan solusi rekursif dan iteratif serta membahas kapan masing-masing sebaiknya digunakan.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Memvisualisasikan Tumpukan Pemanggilan” gratis?
Ya — teks lengkap “Memvisualisasikan Tumpukan Pemanggilan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Memvisualisasikan Tumpukan Pemanggilan”?
Gunakan modul sys Python dan pelacakan dengan print untuk mengamati frame tumpukan yang bertambah dan berkurang, serta memahami risiko stack overflow dalam rekursi mendalam. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Memvisualisasikan Tumpukan Pemanggilan” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Kerangka Rekursi: Kasus Dasar, Kepercayaan, Pembangunan
- Memvisualisasikan Tumpukan Pemanggilan
- Pertukaran Rekursif dan Iteratif
- Memoization: Menyimpan Hasil Rekursif