Persediaan Temu Duga Pengaturcaraan · Pelajaran

Menggambarkan Tindanan Panggilan

Gunakan modul sys Python dan jejak cetakan untuk memerhati bingkai tindanan yang berkembang dan mengecut, serta memahami risiko limpahan tindanan dalam rekursi mendalam.

Pelajaran 2 daripada 413 langkah

Menggambarkan Tindanan Panggilan ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Apakah Tindanan Panggilan?

Setiap panggilan fungsi dalam Python mencipta bingkai tindanan pada tindanan panggilan. Bingkai itu menyimpan pemboleh ubah setempat fungsi, alamat pemulangan (tempat pelaksanaan disambung selepas fungsi kembali), dan penuding arahan semasa. Apabila fungsi kembali, bingkainya dikeluarkan dan kawalan diserahkan kembali kepada pemanggil. Tindanan panggilan berkembang ke bawah pada setiap panggilan dan mengecil pada setiap pemulangan.

Memahami tindanan panggilan penting untuk penyahpepijatan kod rekursif, menganggar penggunaan memori, dan mengelakkan ralat limpahan tindanan dalam rekursi mendalam.

import traceback

def outer():
    inner()

def inner():
    # Print the current call stack
    traceback.print_stack()

outer()
# Shows: module -> outer -> inner

Memerhatikan Bingkai Tindanan dengan sys

Modul sys Python menyediakan alat untuk memeriksa tindanan panggilan semasa masa jalan. sys._getframe(n) mengembalikan bingkai tindanan yang berada n aras di atas fungsi semasa. Setiap bingkai mempunyai kamus f_locals yang mengandungi pemboleh ubah setempat serta f_code.co_name untuk nama fungsi. Menyisipkan cetakan penyahpepijatan di dalam fungsi rekursif mendedahkan cara bingkai terkumpul dan dileraikan.

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)

Menjejak factorial pada Tindanan Panggilan

Jejaki factorial(4) pada tindanan panggilan. Panggilan terkumpul: factorial(4) memanggil factorial(3), yang memanggil factorial(2), yang memanggil factorial(1), yang memanggil factorial(0). Pada kes asas, tindanan mempunyai 5 bingkai. Pemulangan mengurai tindanan: 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. Kedalaman sama dengan n+1 dan kerumitan ruang ialah 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)

Limpahan Tindanan: Had Rekursi Python

Python menjana RecursionError apabila tindanan panggilan melebihi hadnya (lalai ~1000 bingkai). Ini melindungi sistem daripada rekursi tanpa penghujung yang menggunakan semua memori. Bagi masalah dengan saiz masukan n = 10^4 atau lebih, penyelesaian rekursif dengan kedalaman O(n) akan ranap tanpa menaikkan had. Padanan beriterasinya menggunakan ruang tindanan O(1) kerana hanya menggunakan satu bingkai untuk fungsi pembungkus.

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!')

Meningkatkan Had Rekursi

Anda boleh meningkatkan had rekursi Python dengan sys.setrecursionlimit(n), tetapi ini hanyalah penyelesaian sementara. Had lalai wujud kerana setiap bingkai tindanan menggunakan memori (biasanya beberapa ratus bait dalam CPython). Menetapkan had kepada 10^6 dan kemudian memanggil rekursi sedalam 10^5 boleh memperuntukkan ratusan megabait ruang tindanan. Pembaikan yang betul biasanya ialah menukar penyelesaian kepada bentuk beriterasi atau menggunakan memoisation untuk mengurangkan 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())

Tindanan Panggilan untuk Rekursi Bersama

Rekursi bersama berlaku apabila fungsi A memanggil fungsi B dan fungsi B memanggil fungsi A. Tindanan panggilan berselang-seli antara bingkai A dan B. Corak ini muncul dalam penentuan nombor genap atau ganjil serta simulasi mesin keadaan. Corak ini betul selagi kedalaman tindanan kekal terhad — tetapi kedalamannya boleh menjadi lebih sukar untuk dinilai berbanding rekursi linear yang mudah.

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))  # False

Panggilan Ekor dan Sebab Python Tidak Mengoptimumkannya

Panggilan ekor ialah panggilan rekursif yang menjadi operasi terakhir sebelum pemulangan — tiada pengiraan dilakukan selepasnya. Dalam bahasa seperti Haskell atau Scheme, panggilan ekor dioptimumkan menjadi gelung (pengoptimuman panggilan ekor, TCO), lalu memberikan ruang tindanan O(1). Python sengaja tidak melaksanakan TCO. Seperti yang dijelaskan oleh Guido van Rossum, mengekalkan jejak tindanan penuh untuk penyahpepijatan lebih bernilai daripada penjimatan ruang. Oleh itu, dalam Python, kod rekursif ekor masih menggunakan ruang tindanan 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))  # 3628800

Mencetak Pepohon Rekursi

Memvisualisasikan pepohon rekursi membantu mengenal pasti tempat submasalah pendua berlaku (sasaran memoisation). Cara mudah untuk mencetak pepohon itu ialah menambah parameter indent yang meningkat sebanyak 2 ruang pada setiap aras. Setiap panggilan mencetak argumennya ketika masuk dan nilai pemulangannya ketika keluar. Menjalankan cara ini untuk Fibonacci(5) menunjukkan dengan jelas percabangan eksponen dan panggilan 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-problems

Kedalaman Tindanan = Kerumitan Ruang

Bagi sebarang fungsi rekursif, kedalaman maksimum tindanan panggilan sama dengan kedalaman rekursi maksimum pada mana-mana ketika sepanjang pelaksanaan. Kedalaman ini secara langsung menyamai kerumitan ruang tambahan. Bagi rekursi linear (factorial, Fibonacci, rentetan terbalik), kedalamannya ialah O(n). Bagi algoritma bahagi dan takluk (isihan cantum, carian binari), kedalamannya ialah O(log n). Bagi lintasan pepohon, kedalamannya ialah O(h), dengan h ialah height pepohon (O(log n) jika seimbang, O(n) dalam kes 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)) # 10

Menukar Rekursi kepada Iterasi dengan Tindanan Eksplisit

Mana-mana algoritma rekursif boleh dijadikan beriterasi dengan mengurus tindanan panggilan secara eksplisit menggunakan senarai Python. Daripada membiarkan OS mengurus bingkai, anda menolak 'tugasan' ke dalam senarai dan menggunakan pop untuk mengeluarkannya dalam gelung. Cara ini menghapuskan had rekursi Python dan mengurangkan overhed setiap bingkai, tetapi menghasilkan kod yang lebih kompleks. DFS beriterasi menggunakan tindanan eksplisit yang kita lihat sebelum ini mengikut corak ini tepat-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]

Rumusan: Tindanan Panggilan dan Ruang

Tindanan panggilan ialah struktur data tersembunyi di sebalik semua rekursi. Kedalamannya sama dengan kerumitan ruang algoritma rekursif anda. Python mengehadkannya kepada ~1000, jadi algoritma dengan kedalaman rekursi O(n) memerlukan sama ada had yang dinaikkan (berisiko) atau penulisan semula beriterasi. Apabila menulis kod rekursif dalam temu duga, sentiasa nyatakan kerumitan ruang yang disebabkan oleh tindanan panggilan: 'Ini menggunakan ruang O(n) untuk kedalaman rekursi' atau 'O(log n) untuk lintasan pepohon seimbang'.

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Rumusan Pelajaran

Dalam pelajaran ini, anda telah mempelajari: setiap panggilan rekursif mencipta bingkai tindanan yang menyimpan pemboleh ubah setempat dan alamat pemulangan, kedalaman maksimum tindanan sama dengan kerumitan ruang tambahan rekursi, dan had rekursi Python (~1000) menjadikan algoritma dengan kedalaman O(n) berisiko untuk n yang besar — tukarkannya kepada bentuk beriterasi menggunakan tindanan eksplisit. Seterusnya, kita akan membandingkan penyelesaian rekursif dan beriterasi serta membincangkan masa yang sesuai untuk menggunakan setiap satunya.

Percuma untuk bermula

Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 90
Pelajaran: 360

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Menggambarkan Tindanan Panggilan” percuma?

Ya — teks penuh “Menggambarkan Tindanan Panggilan” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Menggambarkan Tindanan Panggilan”?

Gunakan modul sys Python dan jejak cetakan untuk memerhati bingkai tindanan yang berkembang dan mengecut, serta memahami risiko limpahan tindanan dalam rekursi mendalam. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.

Berapa lamakah pelajaran “Menggambarkan Tindanan Panggilan” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?

Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

Rangka Kerja Rekursi: Kes Asas, Kepercayaan, Binaan
Menggambarkan Tindanan Panggilan
Pertukaran Rekursif dan Lelaran
Memoisasi: Menyimpan Keputusan Rekursif

← Kembali ke Persediaan Temu Duga Pengaturcaraan