هذا المقال يتطلب مستوى: مبتدئ
بعد المقال ده هتعرف بالظبط ليه دالة بتنادي نفسها ممكن توقّع البرنامج برسالة 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