Coding Interview Prep · บทเรียน

การแสดงภาพสแตกการเรียก

ใช้โมดูล sys ของ Python และการพิมพ์เพื่อติดตามการเติบโตและหดตัวของเฟรมสแตก พร้อมทำความเข้าใจความเสี่ยงสแตกโอเวอร์โฟลว์จากการเรียกซ้ำลึก

การแสดงภาพสแตกการเรียก เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

สแตกการเรียกคืออะไร

การเรียกฟังก์ชันทุกครั้งในไพธอนจะสร้าง เฟรมสแตก บนสแตกการเรียก เฟรมนี้เก็บตัวแปรเฉพาะที่ของฟังก์ชัน ที่อยู่สำหรับส่งคืน (ตำแหน่งที่การทำงานจะดำเนินต่อหลังฟังก์ชันส่งคืน) และตัวชี้คำสั่งปัจจุบัน เมื่อฟังก์ชันส่งคืน เฟรมของฟังก์ชันจะถูกนำออกจากสแตก และการควบคุมจะส่งกลับไปยังผู้เรียก สแตกการเรียกจะขยายลงด้านล่างเมื่อมีการเรียกแต่ละครั้ง และหดลงเมื่อมีการส่งคืนแต่ละครั้ง

การเข้าใจสแตกการเรียกเป็นสิ่งสำคัญสำหรับการแก้จุดบกพร่องของโค้ดแบบเรียกซ้ำ การประเมินการใช้หน่วยความจำ และการหลีกเลี่ยงข้อผิดพลาดสแตกโอเวอร์โฟลว์ในการเรียกซ้ำที่ลึก

import traceback

def outer():
    inner()

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

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

การสังเกตเฟรมสแตกด้วยโมดูลระบบ

โมดูล sys ของไพธอนมีเครื่องมือสำหรับตรวจสอบสแตกการเรียกขณะโปรแกรมทำงาน sys._getframe(n) ส่งคืนเฟรมสแตกที่อยู่เหนือฟังก์ชันปัจจุบันขึ้นไป n ระดับ แต่ละเฟรมมีพจนานุกรม f_locals ของตัวแปรเฉพาะที่ และมี f_code.co_name สำหรับชื่อฟังก์ชัน การแทรกคำสั่งพิมพ์สำหรับแก้จุดบกพร่องไว้ภายในฟังก์ชันแบบเรียกซ้ำจะแสดงให้เห็นว่าเฟรมสะสมและสลายตัวอย่างไร

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)

ติดตาม factorial บนสแตกการเรียก

ติดตาม factorial(4) บนสแตกการเรียก การเรียกจะสะสมขึ้นดังนี้ factorial(4) เรียก factorial(3) เรียก factorial(2) เรียก factorial(1) เรียก factorial(0) เมื่อถึงกรณีฐาน สแตกจะมี 5 เฟรม การส่งคืนจะคลี่กลับดังนี้ factorial(0) ส่งคืน 1; factorial(1) ส่งคืน 1×1=1; factorial(2) ส่งคืน 2×1=2; factorial(3) ส่งคืน 3×2=6; factorial(4) ส่งคืน 4×6=24 ความลึกเท่ากับ n+1 และความซับซ้อนด้านพื้นที่คือ 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)

สแตกโอเวอร์โฟลว์: ขีดจำกัดการเรียกซ้ำของไพธอน

ไพธอนจะแจ้ง RecursionError เมื่อสแตกการเรียกมีจำนวนเฟรมเกินขีดจำกัด (ค่าเริ่มต้นประมาณ 1000 เฟรม) กลไกนี้ช่วยป้องกันไม่ให้การเรียกซ้ำไม่สิ้นสุดใช้หน่วยความจำจนหมด สำหรับปัญหาที่ขนาดข้อมูลเข้าคือ n = 10^4 ขึ้นไป วิธีแก้แบบเรียกซ้ำที่มีความลึก O(n) จะทำงานล้มเหลวหากไม่เพิ่มขีดจำกัด ส่วนวิธีเทียบเท่าแบบวนซ้ำใช้พื้นที่สแตก O(1) เพราะใช้เพียงเฟรมเดียวสำหรับฟังก์ชันภายนอก

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

การเพิ่มขีดจำกัดการเรียกซ้ำ

คุณสามารถเพิ่มขีดจำกัดการเรียกซ้ำของไพธอนได้ด้วย sys.setrecursionlimit(n) แต่นี่เป็นเพียงวิธีแก้ชั่วคราว ขีดจำกัดเริ่มต้นมีอยู่เพราะแต่ละเฟรมสแตกใช้หน่วยความจำ (โดยทั่วไปหลายร้อยไบต์ในซีไพธอน) การตั้งขีดจำกัดเป็น 10^6 แล้วเรียกการเรียกซ้ำที่ลึก 10^5 ระดับอาจจัดสรรพื้นที่สแตกหลายร้อยเมกะไบต์ วิธีแก้ที่ถูกต้องโดยทั่วไปคือเปลี่ยนเป็นวิธีแบบวนซ้ำ หรือใช้การจดจำผลลัพธ์เพื่อลดความลึก

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())

สแตกการเรียกสำหรับการเรียกซึ่งกันและกัน

การเรียกซึ่งกันและกันคือกรณีที่ฟังก์ชัน A เรียกฟังก์ชัน B และฟังก์ชัน B เรียกฟังก์ชัน A สแตกการเรียกจะสลับไปมาระหว่างเฟรมของ A และ B รูปแบบนี้ปรากฏในการตรวจสอบว่าเป็นเลขคู่หรือคี่ และการจำลองเครื่องสถานะ รูปแบบนี้ถูกต้องตราบใดที่ความลึกของสแตกยังมีขอบเขตจำกัด แต่การวิเคราะห์ความลึกอาจทำได้ยากกว่าการเรียกซ้ำแบบเส้นตรงทั่วไป

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

การเรียกแบบหางและเหตุผลที่ไพธอนไม่ปรับให้เหมาะสม

การเรียกซ้ำแบบหางคือการเรียกซ้ำที่เป็นการดำเนินการสุดท้ายก่อนส่งคืน โดยไม่มีการคำนวณใดตามหลัง ในภาษาอย่างแฮสเคลล์หรือสคีม การเรียกแบบหางจะถูกปรับให้เป็นลูป (การปรับการเรียกแบบหางให้เหมาะสม หรือ TCO) ทำให้ใช้พื้นที่สแตก O(1) ไพธอนจงใจไม่ใช้ TCO ดังที่ กีโด ฟาน รอสซัม อธิบายไว้ การเก็บร่องรอยสแตกทั้งหมดไว้เพื่อแก้จุดบกพร่องมีคุณค่ามากกว่าการประหยัดพื้นที่ ดังนั้นในไพธอน โค้ดแบบเรียกซ้ำหางก็ยังใช้พื้นที่สแตก 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

การพิมพ์ต้นไม้การเรียกซ้ำ

การแสดงต้นไม้การเรียกซ้ำให้เห็นภาพช่วยระบุว่าปัญหาย่อยใดเกิดซ้ำ ซึ่งเป็นเป้าหมายของการจดจำผลลัพธ์ วิธีง่าย ๆ ในการพิมพ์ต้นไม้คือเพิ่มพารามิเตอร์ indent ที่เพิ่มขึ้นครั้งละ 2 ช่องว่างในแต่ละระดับ เมื่อเข้าสู่ฟังก์ชัน แต่ละการเรียกจะพิมพ์อาร์กิวเมนต์ของตน และเมื่อออกจากฟังก์ชันจะพิมพ์ค่าที่ส่งคืน การทำเช่นนี้กับฟีโบนักชี(5) แสดงให้เห็นการแตกแขนงแบบเอ็กซ์โพเนนเชียลและการเรียกซ้ำที่เกิดขึ้นซ้ำอย่างชัดเจน

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

ความลึกของสแตก = ความซับซ้อนด้านพื้นที่

สำหรับฟังก์ชันแบบเรียกซ้ำทุกฟังก์ชัน ความลึกสูงสุดของสแตกการเรียกจะเท่ากับความลึกสูงสุดของการเรียกซ้ำ ณ จุดใดจุดหนึ่งระหว่างการทำงาน ความลึกนี้เท่ากับความซับซ้อนด้านพื้นที่เสริมโดยตรง สำหรับการเรียกซ้ำแบบเส้นตรง (factorial, ฟีโบนักชี, การกลับลำดับสตริง) ความลึกคือ O(n) สำหรับอัลกอริทึมแบบแบ่งแล้วพิชิต (การเรียงลำดับแบบผสาน การค้นหาแบบทวิภาค) ความลึกคือ O(log n) สำหรับการท่องต้นไม้ ความลึกคือ O(h) โดย h คือ height ของต้นไม้ (O(log n) ในกรณีสมดุล และ 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

เปลี่ยนการเรียกซ้ำเป็นการวนซ้ำด้วยสแตกที่จัดการเอง

อัลกอริทึมแบบเรียกซ้ำทุกแบบสามารถเปลี่ยนเป็นแบบวนซ้ำได้ด้วยการจัดการสแตกการเรียกเองโดยใช้รายการของไพธอน แทนที่จะให้ OS จัดการเฟรม คุณจะใส่งานลงในรายการแล้วนำออกด้วย pop ภายในลูป วิธีนี้ยกเลิกขีดจำกัดการเรียกซ้ำของไพธอนและลดค่าใช้จ่ายส่วนเกินต่อเฟรม แต่ต้องแลกกับโค้ดที่ซับซ้อนขึ้น การทำ DFS แบบวนซ้ำโดยใช้สแตกที่จัดการเองซึ่งเราเห็นก่อนหน้านี้ใช้รูปแบบนี้อย่างตรงไปตรงมา

# 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]

สรุป: สแตกการเรียกและพื้นที่

สแตกการเรียกคือโครงสร้างข้อมูลเบื้องหลังการเรียกซ้ำทั้งหมด ความลึกของสแตกเท่ากับความซับซ้อนด้านพื้นที่ของอัลกอริทึมแบบเรียกซ้ำของคุณ ไพธอนจำกัดความลึกไว้ที่ประมาณ 1000 ดังนั้นอัลกอริทึมที่มีความลึกการเรียกซ้ำ O(n) จึงต้องเพิ่มขีดจำกัด (ซึ่งมีความเสี่ยง) หรือเขียนใหม่เป็นแบบวนซ้ำ เมื่อเขียนโค้ดแบบเรียกซ้ำในการสัมภาษณ์ ให้ระบุความซับซ้อนด้านพื้นที่ที่เกิดจากสแตกการเรียกเสมอ เช่น “วิธีนี้ใช้พื้นที่ O(n) สำหรับความลึกของการเรียกซ้ำ” หรือ “ใช้พื้นที่ O(log n) สำหรับการท่องต้นไม้สมดุล”

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้

ทบทวนบทเรียน

ในบทเรียนนี้ คุณได้เรียนรู้ว่า การเรียกซ้ำแต่ละครั้งสร้างเฟรมสแตกที่เก็บตัวแปรเฉพาะที่และที่อยู่สำหรับส่งคืน, ความลึกสูงสุดของสแตกเท่ากับความซับซ้อนด้านพื้นที่เสริมของการเรียกซ้ำ และ ขีดจำกัดการเรียกซ้ำของไพธอน (ประมาณ 1000) ทำให้อัลกอริทึมที่มีความลึก O(n) เสี่ยงเมื่อ n มีค่ามาก — ให้เปลี่ยนเป็นแบบวนซ้ำโดยใช้สแตกที่จัดการเอง บทถัดไป เราจะเปรียบเทียบวิธีแก้แบบเรียกซ้ำและแบบวนซ้ำ และพูดคุยว่าเมื่อใดควรใช้แต่ละแบบ

คำถามที่พบบ่อย

บทเรียน “การแสดงภาพสแตกการเรียก” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “การแสดงภาพสแตกการเรียก” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “การแสดงภาพสแตกการเรียก”

ใช้โมดูล sys ของ Python และการพิมพ์เพื่อติดตามการเติบโตและหดตัวของเฟรมสแตก พร้อมทำความเข้าใจความเสี่ยงสแตกโอเวอร์โฟลว์จากการเรียกซ้ำลึก คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน

บทเรียน “การแสดงภาพสแตกการเรียก” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม

ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

กรอบการเรียกซ้ำ: กรณีฐาน ความเชื่อมั่น การสร้าง
การแสดงภาพสแตกการเรียก
การแลกเปลี่ยนระหว่างแบบเรียกซ้ำกับแบบวนซ้ำ
การจดจำผลลัพธ์: แคชผลลัพธ์จากการเรียกซ้ำ

← กลับไปที่ Coding Interview Prep