Recursion للمبتدئ: ليه دالة بتنادي نفسها بتوقّع البرنامج بـ Stack Overflow

المستوى المطلوب: مبتدئ. الشرح مبني على مثال يومي بسيط أول، وبعدين التعريف العلمي الدقيق، مع كود تقدر تنسخه وتجرّبه على طول.

لو دالة بتنادي نفسها ونسيت تحطّ لها شرط وقوف، البرنامج بيقع بخطأ اسمه 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

دي مش هتوقف عند صفر، هتكمل لأرقام سالبة وتفضل تنادي نفسها لحد ما بايثون يقطعها بالخطأ ده.

الرقم المهم: حد الـ 1000 في بايثون

بايثون مش بيستنّى الذاكرة كلها تخلص. عنده حدّ أمان افتراضي للعمق بحوالي 1000 إطار. تقدر تشوفه بنفسك:

import sys
print(sys.getrecursionlimit())   # 1000

في JavaScript مفيش رقم ثابت، بس لمّا تعدّي حدّ المحرّك (عادة بين 10 آلاف و15 ألف إطار في V8) بيطلع لك:

function countdown(n) {
  console.log(n);
  countdown(n - 1);
}
countdown(5);
// RangeError: Maximum call stack size exceeded

سيناريو واقعي

افرض عندك شجرة تعليقات أو قائمة مترابطة فيها 50 ألف عقدة، وكتبت دالة بتمشي عليها بالـ recursion. النسخة دي شغّالة تمام على بيانات الاختبار الصغيرة، بس أول ما تيجي على الـ 50 ألف عقدة الحقيقية، هتعدّي حدّ الـ 1000 وتقع بـ RecursionError. المشكلة مش في البيانات، المشكلة إن العمق أكبر من مساحة الـ stack.

الـ trade-off: متى recursion ومتى loop

الـ Recursion بتكسب: كود أنضف وأقصر للمسائل اللي طبيعتها متشعّبة زي الشجرة والتقسيم والحلّ والتنقّل في المجلدات. بتخسر: كل إطار بياكل من الـ stack، وفي تكلفة بسيطة لكل نداء دالة. الحلقة العادية بتكسب: ذاكرة أقل وأمان من الـ overflow. بتخسر: أحيانًا كود أقل وضوحًا في المسائل الشجرية.

متى لا تستخدم الـ Recursion

متستخدمهاش لو العمق ممكن يكبر ويطلع بلا حدود معروفة، زي المرور على قائمة مترابطة طويلة أو شجرة عميقة جدًا. في الحالات دي حوّلها لحلقة while أو استخدم stack صريح. وخلّي في بالك إن بايثون ومعظم محرّكات JavaScript مابتعملش tail-call optimization، يعني متعتمدش إن الـ recursion الذيلية هتنجّيك من الـ overflow.

الخطوة التالية

افتح أقرب دالة recursive عندك، واسأل نفسك سؤال واحد: هل في حالة بتوصل لشرط الوقوف أكيد؟ جرّبها على أكبر إدخال متوقع. لو طلعت RecursionError، حوّلها لحلقة عادية بـ stack صريح، وجرّب تاني. لو لسه بتقع، ابعتلي عمق البيانات اللي عندك.

المصادر

• توثيق Python الرسمي: sys.setrecursionlimit و sys.getrecursionlimit — docs.python.org/3/library/sys.html
• MDN Web Docs: Call stack و RangeError Maximum call stack size exceeded — developer.mozilla.org
• Wikipedia: Call stack و Stack overflow — en.wikipedia.org/wiki/Call_stack
• V8 و ECMAScript: حدود حجم الـ call stack في محرّك JavaScript — v8.dev