مستوى المقال: مبتدئ
لو دالة بتنادي نفسها بتلخبطك ودماغك بتقول "ده هيدخل loop لانهائي"، المقال ده هيخليك تفهم recursion في 10 دقائق وتعرف امتى تستخدمه فعلاً وامتى متستخدمهوش.
Recursion: لما الدالة بتنادي نفسها بأمان
المشكلة باختصار
أول مرة المبتدئ يشوف دالة فيها سطر بيستدعي اسمها، الدماغ بتقفل. السؤال البديهي: "ده مش هيفضل ينادي نفسه للأبد؟". الإجابة: لا، طول ما فيه قاعدة وقوف. القاعدة دي اسمها base case. لو غابت بالظبط، آه هتقع في loop. لو موجودة، الكود بيشتغل بطريقة نظيفة جدًا وقصيرة. الفرق بين الكارثة والحل الجميل سطر واحد.
المثال الأبسط: دمى ماتريوشكا
تخيل عندك دمية روسية (ماتريوشكا) جوّاها دمية أصغر، جوّاها دمية أصغر، وهكذا. لو سألتك: "كم عدد الدمى في الصندوق؟"، انت مش هتعدّهم بـ list. هتفتح الدمية، لو لقيت جوّاها دمية، هتسأل نفس السؤال على الدمية الجوّانية وتزود 1. الدمية الفاضية اللي مفيهاش جوّاها حاجة هي اللي بتوقّف العملية.
ده recursion بالظبط: سؤال بيكرر نفسه على نسخة أصغر من المشكلة، لحد ما يوصل لحالة بسيطة معروفة الإجابة. الدمية الفاضية = base case. الدمية اللي جوّاها واحدة تانية = recursive case.
التعريف العلمي بدقة
Recursion هي تقنية في البرمجة بتعتمد على إن الدالة تستدعي نفسها على مدخلات أصغر تدريجيًا. أي recursion صحيح لازم يحقق شرطين:
- Base case: حالة بتوقف الاستدعاء وترجّع إجابة مباشرة بدون استدعاء جديد.
- Recursive case: حالة بتقسم المشكلة لمشكلة أصغر وبتنادي الدالة على المشكلة الأصغر دي.
كل استدعاء بيتسجّل في هيكل بيانات جوّا الـ runtime اسمه call stack. كل frame في الـ stack بياخد ذاكرة فيها المتغيرات المحلية والـ return address. لو الـ base case غابت، الـ stack بيكبر لحد ما البرنامج يقع بـ StackOverflowError (أو RecursionError في Python).
كود فعلي: factorial في Python
الـ factorial لرقم n هو حاصل ضرب الأرقام من 1 لحد n. مثلاً 5! = 5×4×3×2×1 = 120. الإصدار الـ recursive سطرين:
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5)) # 120اللي بيحصل فعلاً وراء الستار: factorial(5) بتنادي factorial(4)، اللي بتنادي factorial(3)... لحد factorial(0) اللي بترجّع 1 على طول. وبعدين القيم بترجع للوراء وتتضرب: . كل استدعاء كان مستني الإجابة من الاستدعاء الأصغر منه.
