مفاضلات الاستدعاء الذاتي والتكرار
حوّل العاملي وFibonacci الذاتيين إلى حلقات تكرارية، واشرح متى يجعل حد الاستدعاء الذاتي وحجم المكدس في Python التكرارَ خيارًا أفضل
مفاضلات الاستدعاء الذاتي والتكرار درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
الازدواجية بين الاستدعاء الذاتي والتكرار
يمكن كتابة كل خوارزمية يمكن صياغتها بالاستدعاء الذاتي بصورة تكرارية أيضًا، والعكس صحيح. وغالبًا ما تعكس النسخة القائمة على الاستدعاء الذاتي التعريف الرياضي للمسألة بصورة أقرب، بينما تمنحك النسخة التكرارية تحكمًا صريحًا في الذاكرة وتتجنب مخاطر تجاوز سعة المكدس. ويُعد الاختيار بينهما قرارًا عمليًا يعتمد على قابلية القراءة، وحدود العمق، ومتطلبات الأداء.
وفي المقابلات، تُعد القدرة على عرض النسختين وشرح المفاضلات بينهما مؤشرًا قويًا على إتقانك.
المضروب: الاستدعاء الذاتي مقابل التكرار
المضروب هو المثال التقليدي على ذلك. فالنسخة القائمة على الاستدعاء الذاتي ترمّز التعريف الرياضي مباشرةً: n! = n × (n-1)!. وتستخدم مساحة مكدس O(n) بسبب قيم الإرجاع المعلّقة وعددها n. أما النسخة التكرارية فتتكرر من 1 إلى n، وتستخدم مساحة O(1). عند n = 1000، تصطدم النسخة القائمة على الاستدعاء الذاتي بالحد الافتراضي في Python؛ بينما تتعامل النسخة التكرارية مع قيم n الكبيرة كيفما كانت.
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1) # O(n) stack
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # O(1) stack
return result
print(factorial_rec(10)) # 3628800
print(factorial_iter(10)) # 3628800
# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0) # True (Python handles big ints)فيبوناتشي: أسي مقابل خطي
يستغرق تنفيذ فيبوناتشي الساذج القائم على الاستدعاء الذاتي زمنًا O(2^n)، وهو بطيء بصورة كارثية عند قيم n الكبيرة. أما النسخة التكرارية فتستغرق زمنًا O(n) وتستخدم مساحة O(1). كما يستغرق الاستدعاء الذاتي مع التخزين المؤقت للنتائج (في الدرس التالي) زمنًا O(n)، لكنه يستخدم مساحة O(n) بسبب قاموس التخزين المؤقت ومكدس O(n). وبالنسبة إلى فيبوناتشي، يكون الأسلوب التكراري أمثل وفق جميع المقاييس. عند n = 50، يستغرق الاستدعاء الذاتي الساذج ثوانٍ، بينما يستغرق التنفيذ التكراري ميكروثوانٍ.
import time
def fib_rec(n):
if n <= 1: return n
return fib_rec(n-1) + fib_rec(n-2) # O(2^n)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time, O(1) space
# Timing comparison for n=35
start = time.time()
fib_rec(35)
print(f'Recursive n=35: {time.time()-start:.3f}s')
start = time.time()
fib_iter(35)
print(f'Iterative n=35: {time.time()-start:.6f}s')
print(fib_iter(100)) # handles large nاجتياز الشجرة: الاستدعاء الذاتي مقابل التكرار
يتميز اجتياز الشجرة باستخدام الاستدعاء الذاتي بالبساطة الطبيعية، لأن بنية الشجرة تحاكي بنية الاستدعاء الذاتي. ولكن في شجرة مائلة بعمق، تشبه في الأساس قائمة مترابطة، يساوي عمق الاستدعاء الذاتي ارتفاع الشجرة = O(n)، مما قد يسبب تجاوز سعة المكدس. أما الإصدار التكراري الذي يستخدم مكدسًا صريحًا، فلا يفرض حدًا على العمق، ويسمح بزيادة حجم المكدس في الكومة بدلًا من مكدس الاستدعاءات.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
def preorder_rec(root, result=None):
if result is None: result = []
if root:
result.append(root.val)
preorder_rec(root.left, result)
preorder_rec(root.right, result)
return result
def preorder_iter(root):
if not root: return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_rec(root)) # [1, 2, 4, 5, 3]
print(preorder_iter(root)) # [1, 2, 4, 5, 3]فرز الدمج: الاستدعاء الذاتي مقابل التكرار من الأسفل إلى الأعلى
يُنفَّذ فرز الدمج طبيعيًا باستخدام الاستدعاء الذاتي: تقسيم، ثم استدعاء ذاتي، ثم دمج. أما فرز الدمج التكراري من الأسفل إلى الأعلى فيتجنب الاستدعاء الذاتي بالكامل: نبدأ بمصفوفات فرعية حجم كل منها 1، ثم ندمج الأزواج المتجاورة في مصفوفات فرعية حجمها 2، ثم حجمها 4، وهكذا، مع مضاعفة حجم المصفوفة الفرعية في كل مرور. يعمل فرز الدمج من الأسفل إلى الأعلى بزمن O(n log n)، ويستخدم مساحة O(n) لمخزن الدمج، ومساحة O(1) لمكدس الاستدعاءات.
def merge_sort_iterative(arr):
n = len(arr)
size = 1
while size < n:
for start in range(0, n, 2 * size):
mid = min(start + size, n)
end = min(start + 2 * size, n)
left = arr[start:mid]
right = arr[mid:end]
# Merge
i = j = 0
for k in range(start, end):
if i < len(left) and (j >= len(right) or left[i] <= right[j]):
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
size *= 2
return arr
print(merge_sort_iterative([5, 2, 4, 6, 1, 3])) # [1,2,3,4,5,6]متى يكون الاستدعاء الذاتي أفضل بوضوح
يبرُز الاستدعاء الذاتي عندما تكون للمشكلة بنية شبيهة بالشجرة تناظر مباشرةً مخطط الاستدعاءات، وعندما تكون حالات الأساس طبيعية، وعندما يكون العمق محدودًا، مثل O(log n) في الأشجار المتوازنة وخوارزميات التقسيم والحل. ومن الأمثلة على ذلك: تحليل JSON، واجتياز الأدلة، وأشجار الألعاب، ومسائل البحث مع التراجع. في هذه الحالات تكون الشيفرة المعتمدة على الاستدعاء الذاتي أقصر وأوضح وأسهل في إثبات صحتها من الإصدار التكراري المكافئ.
# Recursion is clearest for JSON-like nested structures
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse on sub-list
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
print(flatten([])) # []
print(flatten([[1, [2]], [3, [4, [5]]]])) # [1, 2, 3, 4, 5]متى يكون التكرار أفضل بوضوح
يكون التكرار هو الخيار الصحيح عندما: يكون العمق O(n) وتكون قيمة n كبيرة، أي أكبر من نحو 500 في شيفرة Python الآمنة؛ أو عندما تكون النسختان المعتمدة على الاستدعاء الذاتي والتكرار متساويتين في سهولة القراءة، كما في فيبوناتشي والمضروب؛ أو عندما تكون المشكلة تسلسلية بطبيعتها ولا تتضمن تقسيمًا طبيعيًا إلى مسائل فرعية. يجب دائمًا تنفيذ الحلقات البسيطة التي تعالج المصفوفات من اليسار إلى اليمين، مثل المجاميع التراكمية والنوافذ المنزلقة والمؤشرين، باستخدام التكرار.
# Iterative is clearest for sequential array processing
def running_max(nums):
result = []
curr_max = float('-inf')
for n in nums:
curr_max = max(curr_max, n)
result.append(curr_max)
return result
print(running_max([3, 1, 4, 1, 5, 9, 2, 6])) # [3,3,4,4,5,9,9,9]
# No natural recursion here — iteration is the only sensible choiceتحويل الاستدعاء الذاتي في DFS إلى التكرار
النهج المنهجي هو تحويل كل DFS يعتمد على الاستدعاء الذاتي إلى إصدار تكراري عبر دفع معاملات الاستدعاء الذاتي إلى مكدس صريح. والفكرة الأساسية هي أن الاستدعاء الذاتي f(args) يكافئ دفع args ثم تنفيذ حلقة. أما في المعالجة بالترتيب اللاحق، حيث تحتاج إلى نتائج الأبناء قبل معالجة الأب، فقد تحتاج إلى نهج من مرورين أو إلى علامة زيارة.
# Post-order iterative using two stacks
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val=val; self.left=left; self.right=right
def postorder_iter(root):
if not root: return []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left: s1.append(node.left)
if node.right: s1.append(node.right)
return s2[::-1] # reverse gives post-order
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(postorder_iter(root)) # [4, 5, 2, 3, 1]الكلفة الإضافية للاستدعاء الذاتي
ينطوي كل استدعاء ذاتي في Python على كلفة إضافية غير بسيطة: إذ يُنشأ إطار جديد، مما يخصص ذاكرة في الكومة، وتُهيَّأ المتغيرات المحلية، ويُخزَّن مؤشر عنوان العودة. وتُظهر الاختبارات المعيارية أن كلفة استدعاء الدوال في Python تبلغ تقريبًا 100–200 نانوثانية لكل استدعاء. وعند عمق استدعاء ذاتي قدره 10^6، تتراكم هذه الكلفة لتصل إلى 0.1–0.2 ثانية من الكلفة الإضافية الخالصة، بصرف النظر عن عمل الخوارزمية. أما الحلقات التكرارية فتتجنب هذه الكلفة بالكامل.
import time
def rec_sum(n):
if n == 0: return 0
return n + rec_sum(n - 1)
def iter_sum(n):
total = 0
for i in range(n + 1):
total += i
return total
import sys; sys.setrecursionlimit(10000)
n = 5000
start = time.time()
for _ in range(100): rec_sum(n)
print(f'Recursive sum({n}) x100: {(time.time()-start)*1000:.2f}ms')
start = time.time()
for _ in range(100): iter_sum(n)
print(f'Iterative sum({n}) x100: {(time.time()-start)*1000:.2f}ms')اتخاذ القرار في مقابلة تقنية
في مقابلة للبرمجة، إذا كان لديك خيار، فاسأل: «هل عمق الاستدعاء الذاتي محدود بـ O(log n)؟» إذا كانت الإجابة نعم، فالاستدعاء الذاتي مناسب. «هل عمق الاستدعاء الذاتي يساوي O(n)؟» عندها يُفضَّل استخدام التكرار، أو اذكر أنك ستحوّل الحل إلى إصدار تكراري في بيئة الإنتاج. «هل للمشكلة شكل شجري طبيعي أو تعتمد على التقسيم والحل؟» عندها مِل إلى الاستدعاء الذاتي. «هل المشكلة عبارة عن مسح تسلسلي؟» استخدم التكرار.
اذكر دائمًا سبب اختيارك: «سأستخدم الاستدعاء الذاتي هنا لأن العمق يساوي O(log n) في شجرة بحث ثنائية متوازنة BST، ولذلك فإن مساحة المكدس O(log n) مقبولة».
ملخص: جدول المفاضلات
خلاصة المفاضلات: تكون الشيفرة المعتمدة على الاستدعاء الذاتي أقصر غالبًا وتحاكي بنية المشكلة، لكنها تستهلك مساحة مكدس مقدارها O(depth) وتنطوي على كلفة إضافية لاستدعاءات الدوال. أما الشيفرة التكرارية فتكون أطول، لكنها تستخدم مساحة مكدس مقدارها O(1) وتتجنب حدود الاستدعاء الذاتي. ويمثل الاستدعاء الذاتي مع التخزين المؤقت، في الدرس التالي، حلًا وسطًا: إذ يحافظ على وضوح الاستدعاء الذاتي مع التخلص من إعادة الحساب غير الضرورية. كن واضحًا دائمًا بشأن التعقيد المكاني، بما في ذلك مساحة مكدس الاستدعاءات، عند تحليل حلك.
rows = [
('Factorial', 'O(n) / O(1)', 'O(n) / O(1)', 'Same time; iter wins on space'),
('Fibonacci', 'O(2^n) / O(n)', 'O(n) / O(1)', 'Iter massively wins'),
('Binary search','O(log n) / O(log n)', 'O(log n) / O(1)', 'Iter wins on space'),
('Tree DFS', 'O(n) / O(h)', 'O(n) / O(h)', 'Equal; rec cleaner'),
('Merge sort', 'O(n log n) / O(log n)', 'O(n log n) / O(1)', 'BU-iter wins on stack'),
]
for name, rec, it, note in rows:
print(f'{name:<15} rec={rec:<22} iter={it:<22} {note}')تحقق سريع
اختبر مدى فهمك لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.
مراجعة الدرس
تعلمت في هذا الدرس أن: الاستدعاء الذاتي يُفضَّل عندما يكون العمق O(log n) أو عندما تكون المشكلة شجرية بطبيعتها، بينما يُفضَّل التكرار عندما يكون العمق O(n) أو عندما تكون المشكلة تسلسلية، وأن فيبوناتشي باستخدام الاستدعاء الذاتي الساذج يعمل بزمن O(2^n)، بينما يعمل الإصدار التكراري بزمن O(n) ومساحة O(1)، وأن أي DFS يعتمد على الاستدعاء الذاتي يمكن تحويله إلى إصدار تكراري عبر إدارة مكدس صريح في الكومة. في الخطوة التالية سنطبّق التخزين المؤقت للتخلص من الاستدعاءات الذاتية المتكررة.
الأسئلة الشائعة
هل درس «مفاضلات الاستدعاء الذاتي والتكرار» مجاني؟
نعم — نص درس «مفاضلات الاستدعاء الذاتي والتكرار» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «مفاضلات الاستدعاء الذاتي والتكرار»؟
حوّل العاملي وFibonacci الذاتيين إلى حلقات تكرارية، واشرح متى يجعل حد الاستدعاء الذاتي وحجم المكدس في Python التكرارَ خيارًا أفضل تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «مفاضلات الاستدعاء الذاتي والتكرار»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- إطار الاستدعاء الذاتي: الحالة الأساسية والثقة والبناء
- تصوير مكدس الاستدعاء
- مفاضلات الاستدعاء الذاتي والتكرار
- التخزين المؤقت: حفظ نتائج الاستدعاء الذاتي