المستوى المطلوب: مبتدئ. الشرح مبني على مثال يومي بسيط أول، وبعدين التعريف العلمي الدقيق، مع كود تقدر تنسخه وتجرّبه على طول.
لو دالة بتنادي نفسها ونسيت تحطّ لها شرط وقوف، البرنامج بيقع بخطأ اسمه Stack Overflow. هنا هتفهم بالظبط ليه بيحصل ده، وإزاي تكتب recursion آمنة من أول مرة من غير ما السيرفر يقع.
المشكلة باختصار
الـ Recursion معناها إن الدالة تنادي نفسها لحل نسخة أصغر من نفس المشكلة. الفكرة قوية وبتبسّط كود كتير، بس فيها فخ واحد بيوقّع المبتدئين كلهم: لو منسيش شرط الوقوف، الدالة هتفضل تنادي نفسها للأبد لحد ما الذاكرة تخلص والبرنامج يقع.
مثال من الحياة: طابور بيسأل عن الساعة
تخيّل عشرة ناس واقفين في طابور، كل واحد بصّه قدام. أنت في آخر الطابور وعايز تعرف الساعة كام. أنت مش شايف ساعة، فبتسأل اللي قدامك: كام الساعة؟ هو كمان مش شايف، فبيسأل اللي قدامه، وهكذا.
أول واحد في الطابور عنده ساعة في إيده. ده بيردّ بالوقت، والرد بيرجع واحد واحد لحد ما يوصلك. الراجل اللي عنده الساعة ده هو شرط الوقوف. لكن لو محدش في الطابور عنده ساعة، السؤال هيفضل ماشي للأمام للأبد ومحدش هيرجّع إجابة. ده بالظبط اللي بيحصل في الـ recursion من غير شرط وقوف.
التعريف العلمي: الـ Call Stack وإطارات الاستدعاء
دلوقتي الكلام بدقة. كل ما دالة بتتنادى، الكمبيوتر بيحجز لها مساحة صغيرة في الذاكرة اسمها Stack Frame (إطار الاستدعاء)، وفيها المتغيرات المحلية وعنوان الرجوع. الإطارات دي بتتراصّ فوق بعضها في مكان اسمه Call Stack (مكدّس الاستدعاء).
في كل استدعاء بيتحطّ إطار جديد فوق. ولمّا الدالة تخلّص وترجّع قيمة، إطارها بيتشال والتحكّم بيرجع للي تحته. لو الـ recursion عندها شرط وقوف صحيح، الإطارات بتكبر شوية وبعدين بترجع تتفكّ بالترتيب. لو مفيش شرط وقوف، الإطارات بتفضل تتراكم لحد ما مساحة الـ stack تخلص، فيطلع لك خطأ Stack Overflow.
الكود: نسخة صح ونسخة بتقع
دي recursion سليمة بتحسب مضروب رقم. لاحظ السطر اللي فيه شرط الوقوف:
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120
كل استدعاء بيقرّب من صفر، فالـ stack بيكبر 5 إطارات بس وبعدين يرجع يتفكّ. تمام. دلوقتي شوف النسخة اللي ناسية شرط الوقوف:
def countdown(n):
print(n)
countdown(n - 1) # no stop condition
countdown(5)
# RecursionError: maximum recursion depth exceeded