إطار الاستدعاء الذاتي: الحالة الأساسية والثقة والبناء
طبّق الطريقة ذات الخطوات الثلاث لكتابة حلول ذاتية صحيحة للعاملي والأسّ ومجموع الأرقام دون تتبع كل استدعاء
إطار الاستدعاء الذاتي: الحالة الأساسية والثقة والبناء درس مجاني في DSA Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في DSA Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
لماذا تبدو الاستدعاءات التكرارية صعبة
يحاول معظم المبتدئين تتبّع كل استدعاء تكراري ذهنيًا، وهو ما يصبح مرهقًا بسرعة حتى في استدعاء تكراري بعمق خمسة مستويات. أما الأسلوب الاحترافي فيعتمد على إطار من ثلاث خطوات — الحالة الأساسية، والثقة، والبناء — الذي يتيح لكم كتابة دوال تكرارية صحيحة من دون محاكاة شجرة الاستدعاءات بأكملها ذهنيًا.
يُسمّى هذا الإطار أحيانًا قفزة الثقة: إذ تثقون بأن دالتكم تعمل مع مدخلات أصغر، وتستخدمون هذا الافتراض لبناء الحل للمدخلات الأكبر.
الخطوة 1: تعريف الحالة الأساسية
الحالة الأساسية هي أبسط إدخال تكون إجابته معروفة من دون حاجة إلى مزيد من الاستدعاء الذاتي. يجب أن تحتوي كل دالة استدعاء ذاتي على حالة أساسية واحدة على الأقل؛ وإلا فستستمر الدالة في استدعاء نفسها إلى ما لا نهاية (مما يؤدي إلى تجاوز سعة المكدس). ومن أمثلة الحالات الأساسية الجيدة: قائمة فارغة، أو عنصر واحد، أو n == 0، أو n == 1، أو أن تختزل المسألة إلى هوية بسيطة.
اكتب الحالة الأساسية أولًا، قبل أي منطق للاستدعاء الذاتي. حدّدها بطرح السؤال الآتي: «ما أصغر نسخة من هذه المسألة يمكنني حلها فورًا؟»
# Base cases for common problems
def factorial(n):
if n == 0: # base case: 0! = 1
return 1
# ... recursive step below
def sum_list(lst):
if not lst: # base case: sum of empty list is 0
return 0
# ...
def height(node):
if node is None: # base case: height of null node is 0
return 0
# ...
print('Base cases identified')الخطوة 2: الثقة بالاستدعاء الذاتي
خطوة الثقة هي قفزة إيمانية: افترض أن دالتك تعمل بصورة صحيحة مسبقًا مع أي إدخال أصغر تمامًا من الإدخال الحالي. لا تحتاج إلى إثبات ذلك لكل إدخال أصغر في هذه اللحظة؛ فالبرهان الاستقرائي يضمنه. ما عليك سوى استدعاء دالتك على المسألة الفرعية الأصغر والثقة بأنها ستعيد النتيجة الصحيحة.
يتجاوز المبتدئون هذه الخطوة عادةً، ويحاولون بدلًا من ذلك محاكاة التنفيذ ذهنيًا. قاوم هذا الميل؛ فبمجرد استيعاب هذا الإطار، يمكن تطبيقه على استدعاء ذاتي عميق كيفما كان.
# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11 (we TRUST this, don't trace it)
# Build: 3 + 11 = 14
# So:
def sum_list(lst):
if not lst:
return 0
# Trust that sum_list(lst[1:]) returns sum of the rest
return lst[0] + sum_list(lst[1:])
print(sum_list([3, 1, 4, 1, 5])) # 14الخطوة 3: بناء الحل
تجمع خطوة البناء نتيجة المسألة الفرعية الموثوق بها مع إسهام العنصر الحالي لإنتاج إجابة الإدخال الكامل. وغالبًا ما تكون هذه الخطوة سطرًا واحدًا: تطبيق عملية على العنصر الحالي ونتيجة الاستدعاء الذاتي. ومن عمليات البناء الشائعة: الإضافة إلى المجموع، أو إدراج عنصر في بداية القائمة، أو زيادة العداد، أو دمج نتيجتين فرعيتين.
def factorial(n):
if n == 0:
return 1
# Trust: factorial(n-1) gives (n-1)!
# Build: n * (n-1)! = n!
return n * factorial(n - 1)
def power(base, exp):
if exp == 0:
return 1
# Trust: power(base, exp-1) gives base^(exp-1)
# Build: base * base^(exp-1) = base^exp
return base * power(base, exp - 1)
print(factorial(6)) # 720
print(power(2, 10)) # 1024تطبيق الإطار على مجموع الأرقام
المسألة: احسب مجموع أرقام عدد صحيح غير سالب. الحالة الأساسية: n == 0 ← المجموع يساوي 0 (أو n < 10 ← يساوي n نفسه). الثقة: تعيد sumDigits(n // 10) مجموع جميع الأرقام باستثناء الرقم الأخير. البناء: أضف الرقم الأخير n % 10 إلى النتيجة الموثوق بها. ينتج الإطار الحل في ثلاث خطوات تصريحية.
def sumDigits(n):
if n < 10:
return n # base case: single digit
# Trust: sumDigits(n // 10) gives sum of all digits except last
# Build: add the last digit
return n % 10 + sumDigits(n // 10)
print(sumDigits(0)) # 0
print(sumDigits(7)) # 7
print(sumDigits(123)) # 6
print(sumDigits(9999)) # 36فيبوناتشي: مسألتان فرعيتان
تتطلب فيبوناتشي استدعاءين ذاتيين: fib(n-1) وfib(n-2). طبّق الإطار: الحالتان الأساسيتان هما fib(0) = 0 وfib(1) = 1. الثقة: يعيد الاستدعاءان الأصغر قيم فيبوناتشي الصحيحة. البناء: أعد مجموعهما. هذا التنفيذ الساذج تعقيده الزمني O(2^n) — وسنصلح ذلك في درس التخزين المؤقت للنتائج.
def fib(n):
if n <= 1:
return n # base cases: fib(0)=0, fib(1)=1
# Trust both smaller sub-problems
return fib(n - 1) + fib(n - 2)
for i in range(8):
print(f'fib({i}) = {fib(i)}') # 0,1,1,2,3,5,8,13عكس سلسلة نصية بالاستدعاء الذاتي
المسألة: اعكس سلسلة نصية باستخدام الاستدعاء الذاتي. الحالة الأساسية: سلسلة فارغة أو محرف واحد — فهي معكوسة أصلًا. الثقة: تعيد reverse(s[1:]) معكوس كل ما يأتي بعد المحرف الأول. البناء: ألحِق المحرف الأول في نهاية اللاحقة المعكوسة. يمنحك الإطار حلًا من ثلاثة أسطر.
def reverse_str(s):
if len(s) <= 1:
return s # base case
# Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
# Build: append first character at end
return reverse_str(s[1:]) + s[0]
print(reverse_str('')) # ''
print(reverse_str('a')) # 'a'
print(reverse_str('hello')) # 'olleh'
print(reverse_str('racecar')) # 'racecar'عدّ التكرارات بالاستدعاء الذاتي
المسألة: احسب عدد مرات ظهور قيمة مستهدفة في قائمة باستخدام الاستدعاء الذاتي. الحالة الأساسية: قائمة فارغة — العدد يساوي 0. الثقة: يعيد count(lst[1:], target) العدد في ذيل القائمة. البناء: أضف 1 إذا تطابق العنصر الأول مع القيمة المستهدفة، وإلا فأضف 0. تتقدم كل خطوة استدعاء ذاتي نحو الحالة الأساسية عبر تقليل حجم القائمة بمقدار 1.
def count_occurrences(lst, target):
if not lst:
return 0
# Trust: count in rest of list is handled recursively
# Build: add 1 if first element matches, else 0
return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)
print(count_occurrences([1, 2, 3, 2, 4, 2], 2)) # 3
print(count_occurrences([], 5)) # 0
print(count_occurrences([7, 7, 7], 7)) # 3التحقق مما إذا كانت القائمة مرتبة
المسألة: تحقّق مما إذا كانت القائمة مرتبة ترتيبًا تصاعديًا باستخدام الاستدعاء الذاتي. الحالة الأساسية: قائمة تحتوي على 0 أو 1 من العناصر تكون مرتبة دائمًا. الثقة: تخبرك is_sorted(lst[1:]) بما إذا كان ذيل القائمة مرتبًا. البناء: تكون القائمة مرتبة إذا كان العنصر الأول <= العنصر الثاني وكان الذيل مرتبًا أيضًا. هذا مثال واضح تستخدم فيه خطوة البناء AND منطقيًا بين شرطين.
def is_sorted(lst):
if len(lst) <= 1:
return True
# Trust: is_sorted(lst[1:]) tells us if tail is sorted
# Build: head <= second element AND tail is sorted
return lst[0] <= lst[1] and is_sorted(lst[1:])
print(is_sorted([])) # True
print(is_sorted([1])) # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # Falseالبحث الثنائي بالاستدعاء الذاتي (مراجعة)
يُعبَّر عن البحث الثنائي باستخدام الاستدعاء الذاتي عبر الإطار كما يلي: الحالة الأساسية: lo > hi ← لم يُعثر على العنصر (أعد -1). الثقة: يعثر الاستدعاء الذاتي على الهدف في النصف الصحيح، أو يعيد -1. البناء: احسب mid، ثم قارن واستدعِ النصف المناسب. يوضح الشكل القائم على الاستدعاء الذاتي بنية التقسيم والغزو بوضوح، رغم تفضيل الشكل التكراري في بيئة الإنتاج لاستخدامه مساحة O(1).
def binary_search(arr, target, lo, hi):
if lo > hi: # base case: search space exhausted
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
# Trust both halves return correct results
if arr[mid] < target:
return binary_search(arr, target, mid + 1, hi)
else:
return binary_search(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1)) # 3
print(binary_search(arr, 4, 0, len(arr) - 1)) # -1متى تستخدم الاستدعاء الذاتي بدلًا من التكرار
يبرع الاستدعاء الذاتي عندما تتحلل المسألة طبيعيًا إلى مسائل فرعية أصغر من النوع نفسه، مثل الأشجار، والتقسيم والغزو، والتراجع. ويُفضَّل التكرار عندما: يكون عمق الاستدعاء الذاتي كبيرًا (مما يعرّض البرنامج لتجاوز سعة المكدس في Python، التي يكون حدها الافتراضي نحو 1000)، أو تكون النسختان القائمة على الاستدعاء الذاتي والتكرار واضحتين بالقدر نفسه، أو تكون المسألة مجرد حلقة بسيطة (مثل المضروب أو فيبوناتشي من دون تخزين مؤقت للنتائج).
قاعدة تقريبية جيدة: إذا كان رسم شجرة الاستدعاءات الذاتية يبدو طبيعيًا، فاستخدم الاستدعاء الذاتي. أما إذا كانت الشجرة خطًا مستقيمًا (استدعاء ذاتي ذيلي)، فحوّله إلى تكرار.
import sys
# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit()) # 1000
# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
total = 0
for x in lst:
total += x
return total
big = list(range(2000))
print(sum_list_iter(big)) # 1999000 — no stack overflowاختبار سريع
اختبر مدى فهمك لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.
مراجعة الدرس
تعلّمت في هذا الدرس أن الإطار المؤلف من ثلاث خطوات هو الحالة الأساسية (أبسط إجابة معروفة)، والثقة (افتراض حل المسألة الفرعية)، والبناء (دمج العنصر الحالي مع النتيجة الموثوق بها)، وأن تكتب الحالات الأساسية أولًا وتتجنب تتبّع أشجار الاستدعاءات الكاملة ذهنيًا، وأن تستخدم التكرار عندما يعرّض عمق الاستدعاء الذاتي البرنامج لتجاوز سعة المكدس، أو عندما تكون الصيغة القائمة على الاستدعاء الذاتي والصيغة التكرارية واضحتين بالقدر نفسه. بعد ذلك سنصوّر مكدس الاستدعاءات بالتفصيل.
الأسئلة الشائعة
هل درس «إطار الاستدعاء الذاتي: الحالة الأساسية والثقة والبناء» مجاني؟
نعم — نص درس «إطار الاستدعاء الذاتي: الحالة الأساسية والثقة والبناء» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة DSA Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «إطار الاستدعاء الذاتي: الحالة الأساسية والثقة والبناء»؟
طبّق الطريقة ذات الخطوات الثلاث لكتابة حلول ذاتية صحيحة للعاملي والأسّ ومجموع الأرقام دون تتبع كل استدعاء تتمرن على DSA Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ DSA Interview Prep؟
لا تُشترط خبرة سابقة. DSA Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «إطار الاستدعاء الذاتي: الحالة الأساسية والثقة والبناء»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس DSA Interview Prep هذا؟
نعم. كل درس في DSA Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- إطار الاستدعاء الذاتي: الحالة الأساسية والثقة والبناء
- تصوير مكدس الاستدعاء
- مفاضلات الاستدعاء الذاتي والتكرار
- التخزين المؤقت: حفظ نتائج الاستدعاء الذاتي