الـ Recursion للمبتدئ: إزاي الدالة تنادي نفسها من غير ما تعلّق البرنامج

هذا المقال يتطلب مستوى: مبتدئ

بعد المقال ده هتعرف بالظبط ليه دالة بتنادي نفسها ممكن توقّع البرنامج برسالة RecursionError، وإزاي تكتبها صح من غير ما ده يحصل.

الـ Recursion: إزاي الدالة تنادي نفسها من غير ما تعلّق البرنامج

الـ recursion (الاستدعاء الذاتي) معناه إن دالة تنادي نفسها. الفكرة قوية جدًا، بس أول مرة تشوفها بتبان غريبة. ولو نسيت حاجة واحدة، بيقع البرنامج فورًا.

المشكلة باختصار

ناس كتير بتكتب دالة recursive وبتشتغل تمام على أرقام صغيرة، وبعدين تضرب RecursionError: maximum recursion depth exceeded على مدخل أكبر شوية. المشكلة مش في السيرفر ولا في ذاكرة الجهاز. المشكلة إنك نسيت حاجة واحدة أو ظبطتها غلط: شرط التوقف.

مثال بسيط قبل التعريف العلمي: الدمى الروسية

تخيّل دمية روسية (ماتريوشكا). تفتحها تلاقي جواها دمية أصغر. تفتح دي كمان تلاقي أصغر منها. وهكذا لحد ما توصل لأصغر دمية؛ دي مصمتة مفيش جواها حاجة، فبتقف عندها.

«افتح الدمية» هنا زي دالة بتنادي نفسها على الدمية اللي جوّه. وأصغر دمية مصمتة هي «شرط التوقف». لو كل دمية جواها دمية للأبد، مكانش هتقف خالص. ده بالظبط اللي بيحصل في الكود اللي بيضرب RecursionError.

التعريف العلمي: استدعاء ذاتي + شرط توقف

أي دالة recursive صحيحة لازم يكون فيها جزئين:

• شرط التوقف (base case): حالة بسيطة بترجّع نتيجة على طول، من غير ما تنادي نفسها.
• خطوة التقريب (recursive case): بتنادي نفسها على مدخل أصغر، بحيث كل مرة تقرّب من شرط التوقف.

لو خطوة التقريب مش بتقرّب فعلًا من شرط التوقف، الدالة هتفضل تنادي نفسها بلا نهاية. وهنا بيدخل مكدس الاستدعاء.

مكدس الاستدعاء (Call Stack) وليه بيطفح

كل مرة دالة تنادي دالة، اللغة بتحط «إطار» (frame) فيه المتغيرات ومكان الرجوع، فوق رف اسمه مكدس الاستدعاء. تخيّله رصّة مواعين: كل استدعاء بيحط طبق فوق، وكل return بيشيل طبق. الرف ده محدود. لو رصّيت مواعين كتير من غير ما تشيل، بيطفح — وده الـ stack overflow.

في بايثون، الحد الافتراضي للعمق تقدر تشوفه بنفسك:

import sys
print(sys.getrecursionlimit())   # 1000 غالبًا

def factorial(n):
    if n == 1:                    # شرط التوقف
        return 1
    return n * factorial(n - 1)   # خطوة التقريب

print(factorial(5))     # 120
print(factorial(2000))  # RecursionError: maximum recursion depth exceeded

factorial(5) بيرصّ 5 أطباق ويشيلهم، فيرجّع 120. لكن factorial(2000) محتاج قرب 2000 طبق، والحد 1000، فبيطفح المكدس ويقع البرنامج قبل ما يخلّص.

Recursion مقابل الحلقة (Iteration): الـ trade-off

نفس المسألة تتكتب بحلقة بسيطة، من غير مكدس بيكبر:

def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iter(2000))   # يشتغل عادي، من غير RecursionError

الـ trade-off هنا واضح. الـ recursion بيخلّي كود المسائل المتفرّعة (زي المرور على شجرة أو خوارزمية DFS) أوضح وأقصر بكتير: بتكسب وضوح. بتخسر ذاكرة، لأن كل استدعاء بياخد إطار في المكدس، وبتخسر أمان لو العمق كبير بسبب خطر الـ overflow. الحلقة بتستهلك ذاكرة ثابتة تقريبًا (O(1) إطارات) لكنها بتبقى أطول وأصعب قراءة في المسائل الشجرية.

الافتراض هنا إن كلامنا على CPython، اللي مبيعملش تحسين للاستدعاء الطرفي (tail-call optimization). في لغات تانية زي Scheme، الاستدعاء الطرفي ممكن يتحوّل لحلقة تلقائيًا، فالحسبة بتختلف.

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

متستخدمهاش لو العمق ممكن يكبر من غير حدود واضحة: قائمة فيها مليون عنصر بتعالجها عنصر ورا عنصر بشكل خطي، أو شجرة عميقة جدًا. في الحالات دي حوّلها لحلقة، أو استخدم مكدس صريح (list في بايثون) بدل مكدس اللغة نفسها. كمان لو اللغة متعملش TCO والعمق المتوقّع بيعدّي الحد الافتراضي.

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

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

المصادر

• توثيق بايثون الرسمي — sys.setrecursionlimit وgetrecursionlimit: docs.python.org/3/library/sys.html
• توثيق بايثون — استثناء RecursionError: docs.python.org/3/library/exceptions.html
• MDN — تعريف مكدس الاستدعاء (Call stack): developer.mozilla.org
• Recursion (computer science) — Wikipedia: en.wikipedia.org
• Tail call — Wikipedia: en.wikipedia.org