تصوير مكدس الاستدعاء
استخدم وحدة sys في Python وتتبع الطباعة لمراقبة نمو إطارات المكدس وانكماشها، وافهم مخاطر تجاوز المكدس في الاستدعاء الذاتي العميق
تصوير مكدس الاستدعاء درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ما مكدس الاستدعاءات؟
ينشئ كل استدعاء دالة في Python إطار مكدس في مكدس الاستدعاءات. ويخزّن الإطار المتغيرات المحلية للدالة، وعنوان العودة (أي الموضع الذي يُستأنف منه التنفيذ بعد عودة الدالة)، ومؤشر التعليمة الحالية. عند عودة الدالة، يُزال إطارها من المكدس وتنتقل السيطرة إلى الدالة المستدعية. ينمو مكدس الاستدعاءات نحو الأسفل مع كل استدعاء، ويتقلص مع كل عودة.
يُعد فهم مكدس الاستدعاءات ضروريًا لتصحيح أخطاء الشيفرة القائمة على الاستدعاء الذاتي، وتقدير استخدام الذاكرة، وتجنب أخطاء تجاوز سعة المكدس في الاستدعاء الذاتي العميق.
import traceback
def outer():
inner()
def inner():
# Print the current call stack
traceback.print_stack()
outer()
# Shows: module -> outer -> innerمراقبة إطارات المكدس باستخدام sys
توفر وحدة sys في Python أدوات لفحص مكدس الاستدعاءات أثناء التشغيل. تعيد 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(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)تجاوز سعة المكدس: حد الاستدعاء الذاتي في Python
تطلق Python الاستثناء 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!')زيادة حد الاستدعاء الذاتي
يمكنك زيادة حد الاستدعاء الذاتي في Python باستخدام sys.setrecursionlimit(n)، لكن ذلك حل مؤقت. وُجد الحد الافتراضي لأن كل إطار مكدس يشغل مساحة من الذاكرة (عادةً عدة مئات من البايتات في CPython). قد يؤدي ضبط الحد على 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الاستدعاءات الذيلية ولماذا لا تُحسّنها Python
الاستدعاء الذِيلي هو استدعاء ذاتي يمثل العملية الأخيرة قبل العودة، فلا تُجرى أي حسابات بعده. في لغات مثل Haskell أو Scheme، تُحسَّن الاستدعاءات الذيلية إلى حلقات (تحسين الاستدعاء الذِيلي، TCO)، مما يمنح مساحة مكدس O(1). لا تطبّق Python تقنية TCO عمدًا. وكما أوضح Guido van Rossum، كان الحفاظ على تتبّع المكدس الكامل لأغراض تصحيح الأخطاء أكثر قيمة من توفير المساحة. لذلك، تظل الشيفرة ذات الاستدعاء الذِيلي في Python تستخدم مساحة مكدس 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 يزداد بمقدار مسافتين في كل مستوى. تطبع كل عملية استدعاء وسائطها عند الدخول، وقيمة إرجاعها عند الخروج. ويُظهر تشغيل ذلك على Fibonacci(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عمق المكدس = التعقيد المكاني
في أي دالة استدعاء ذاتي، يساوي أقصى عمق لمكدس الاستدعاءات أقصى عمق للاستدعاء الذاتي في أي لحظة أثناء التنفيذ. ويساوي هذا العمق مباشرةً التعقيد المكاني الإضافي. في الاستدعاء الذاتي الخطي (مثل المضروب، وفيبوناتشي، وعكس السلسلة النصية)، يكون العمق O(n). وفي خوارزميات التقسيم والغزو (مثل الترتيب بالدمج والبحث الثنائي)، يكون العمق O(log n). أما في اجتياز الأشجار، فيكون العمق O(h)، حيث h هو ارتفاع الشجرة (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تحويل الاستدعاء الذاتي إلى تكرار باستخدام مكدس صريح
يمكن تحويل أي خوارزمية قائمة على الاستدعاء الذاتي إلى خوارزمية تكرارية عبر إدارة مكدس الاستدعاءات صراحةً باستخدام قائمة في Python. فبدلًا من ترك نظام التشغيل يدير الإطارات، تضع «المهام» في القائمة وتزيلها في حلقة. يزيل ذلك حد الاستدعاء الذاتي في Python ويقلل الكلفة الإضافية لكل إطار، لكنه يجعل الشيفرة أكثر تعقيدًا. ويتبع اجتياز 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]ملخص: مكدس الاستدعاءات والمساحة
مكدس الاستدعاءات هو بنية البيانات الخفية التي تقف وراء كل استدعاء ذاتي. ويساوي عمقه التعقيد المكاني لخوارزميتك القائمة على الاستدعاء الذاتي. تضعه Python عند نحو 1000، لذلك تحتاج الخوارزميات ذات عمق الاستدعاء الذاتي O(n) إما إلى زيادة الحد (وهو أمر محفوف بالمخاطر) أو إلى إعادة كتابتها بصورة تكرارية. عند كتابة شيفرة قائمة على الاستدعاء الذاتي في المقابلات، اذكر دائمًا التعقيد المكاني الناتج عن مكدس الاستدعاءات: «تستخدم هذه الخوارزمية مساحة O(n) لعمق الاستدعاء الذاتي» أو «تستخدم O(log n) في اجتياز شجرة متوازنة».
اختبار سريع
اختبر مدى فهمك لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.
مراجعة الدرس
تعلّمت في هذا الدرس أن كل استدعاء ذاتي ينشئ إطار مكدس يحتوي على المتغيرات المحلية وعنوان العودة، وأن أقصى عمق للمكدس يساوي التعقيد المكاني الإضافي للاستدعاء الذاتي، وأن حد الاستدعاء الذاتي في Python (نحو 1000) يجعل الخوارزميات ذات العمق O(n) محفوفة بالمخاطر عند قيم n الكبيرة — لذا حوّلها إلى خوارزميات تكرارية باستخدام مكدس صريح. بعد ذلك سنقارن بين الحلول القائمة على الاستدعاء الذاتي والحلول التكرارية، ونناقش متى يُستخدم كل منها.
الأسئلة الشائعة
هل درس «تصوير مكدس الاستدعاء» مجاني؟
نعم — نص درس «تصوير مكدس الاستدعاء» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «تصوير مكدس الاستدعاء»؟
استخدم وحدة sys في Python وتتبع الطباعة لمراقبة نمو إطارات المكدس وانكماشها، وافهم مخاطر تجاوز المكدس في الاستدعاء الذاتي العميق تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «تصوير مكدس الاستدعاء»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- إطار الاستدعاء الذاتي: الحالة الأساسية والثقة والبناء
- تصوير مكدس الاستدعاء
- مفاضلات الاستدعاء الذاتي والتكرار
- التخزين المؤقت: حفظ نتائج الاستدعاء الذاتي