مستوى المقال: مبتدئ

لو دالة بتنادي نفسها بتلخبطك ودماغك بتقول "ده هيدخل loop لانهائي"، المقال ده هيخليك تفهم recursion في 10 دقائق وتعرف امتى تستخدمه فعلاً وامتى متستخدمهوش.

Recursion: لما الدالة بتنادي نفسها بأمان

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

أول مرة المبتدئ يشوف دالة فيها سطر بيستدعي اسمها، الدماغ بتقفل. السؤال البديهي: "ده مش هيفضل ينادي نفسه للأبد؟". الإجابة: لا، طول ما فيه قاعدة وقوف. القاعدة دي اسمها base case. لو غابت بالظبط، آه هتقع في loop. لو موجودة، الكود بيشتغل بطريقة نظيفة جدًا وقصيرة. الفرق بين الكارثة والحل الجميل سطر واحد.

المثال الأبسط: دمى ماتريوشكا

تخيل عندك دمية روسية (ماتريوشكا) جوّاها دمية أصغر، جوّاها دمية أصغر، وهكذا. لو سألتك: "كم عدد الدمى في الصندوق؟"، انت مش هتعدّهم بـ list. هتفتح الدمية، لو لقيت جوّاها دمية، هتسأل نفس السؤال على الدمية الجوّانية وتزود 1. الدمية الفاضية اللي مفيهاش جوّاها حاجة هي اللي بتوقّف العملية.

ده recursion بالظبط: سؤال بيكرر نفسه على نسخة أصغر من المشكلة، لحد ما يوصل لحالة بسيطة معروفة الإجابة. الدمية الفاضية = base case. الدمية اللي جوّاها واحدة تانية = recursive case.

التعريف العلمي بدقة

Recursion هي تقنية في البرمجة بتعتمد على إن الدالة تستدعي نفسها على مدخلات أصغر تدريجيًا. أي recursion صحيح لازم يحقق شرطين:

1. Base case: حالة بتوقف الاستدعاء وترجّع إجابة مباشرة بدون استدعاء جديد.
2. 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 على طول. وبعدين القيم بترجع للوراء وتتضرب: 1 → 1 → 2 → 6 → 24 → 120. كل استدعاء كان مستني الإجابة من الاستدعاء الأصغر منه.

الـ Call Stack: ليه فيه حد للعمق

كل استدعاء recursive بياخد frame في الذاكرة. Python افتراضيًا بيسمح بـ 1000 frame كحد أقصى. جرب الكود ده:

import sys
print(sys.getrecursionlimit())   # 1000 على معظم الإصدارات

factorial(10000)                 # RecursionError

تقدر ترفع الحد بـ sys.setrecursionlimit(20000)، لكن ده مش حل للمشكلة الحقيقية. الـ trade-off واضح: recursion كود نظيف وأقصر بـ 50% تقريبًا، لكنه بياخد ذاكرة O(n) على الـ stack، بينما iteration ذاكرته O(1). على factorial(900) مثلاً، Python بياخد حوالي 0.4MB من الـ stack؛ على factorial(10000) لو رفعت الحد، بيوصل لـ 4MB والاحتمال يقع.

سيناريو واقعي: قراءة شجرة ملفات

لو عندك مجلد فيه مجلدات تانية جوّاه على عمق غير معروف، loop عادي مش هيكفي لأنك مش عارف عدد المستويات قبل ما تشوفها. recursion هي الأداة الطبيعية هنا:

import os

def list_all_files(path):
    for entry in os.listdir(path):
        full = os.path.join(path, entry)
        if os.path.isdir(full):
            list_all_files(full)        # recursive case
        else:
            print(full)                 # base case ضمنيًا

على مجلد فيه 5 مستويات و 200 ملف، الكود ده بيخلص في حوالي 80ms على macOS M1. نفس النتيجة بـ iteration بدون recursion محتاج إنك تبني stack يدويًا (list بتـ append وtـ pop) وبتاخد 25–30 سطر بدل 6 سطور.

Trade-offs بصراحة

• بتكسب: كود أقصر وأقرب للتعريف الرياضي للمشكلة. مثالي للهياكل الشجرية (DOM، JSON متداخل، file system، AST).
• بتخسر: ذاكرة على الـ stack بنسبة O(n) + احتمال stack overflow على مدخلات كبيرة + بطء بسيط (5–15%) في معظم اللغات بسبب function call overhead.
• افتراض: الأرقام دي على CPython 3.12. لغات بتدعم tail call optimization زي Scheme و Scala و Erlang بتلغي تكلفة الذاكرة دي تمامًا في حالة الـ tail recursion. Python و JavaScript V8 مش بيعملوا الـ optimization ده، فالحساب لسه بيتراكم على الـ stack.

Fibonacci: مثال على recursion سيء بدون caching

ركز على الكود ده، شكله بريء بس قنبلة:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(40))   # بياخد ~30 ثانية على Python

المشكلة إن fib(40) بتنادي fib(39) و fib(38)، وfib(39) بتنادي fib(38) وfib(37)، يعني fib(38) بتتحسب مرتين. عند 40 العدد بيوصل لمليار استدعاء. الحل: @functools.lru_cache بيخزّن النتائج فيخلص في مللي ثانية. الدرس: recursion مش غلط، لكن recursion بدون تفكير في التكرار غلط.

متى لا تستخدم recursion

متستخدمهوش لما:

• المشكلة عندها حل iterative بسيط: حساب مجموع list مثلاً. for أسرع وأوضح ومش بياخد stack.
• العمق مجهول وممكن يتعدى 1000: parsing لـ JSON متداخل جاي من user input. استخدم stack يدوي عشان تتجنب stack overflow متعمد من المستخدم.
• نفس الحساب بيتكرر ومفيش memoization: زي Fibonacci بدون caching. الحل memoization أو iteration.
• اللغة مش بتعمل tail call optimization وعندك tail recursion عميقة: حوّلها لـ iteration يدويًا.

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

افتح ملف Python جديد، اكتب فيه دالة sum_list(arr) بطريقتين: واحدة بـ for loop وواحدة بـ recursion. شغّلهم على list فيها 10 آلاف رقم وقيس الزمن بـ time.perf_counter(). لو الـ recursive وقع بـ RecursionError، ده درس عملي على ليه recursion مش حل لكل مشكلة. لو نجح، قارن الزمنين، الفرق هيوضحلك تكلفة function call overhead.

المصادر

• Python Documentation - sys.setrecursionlimit (docs.python.org/3/library/sys.html#sys.setrecursionlimit)
• Sedgewick & Wayne, Computer Science: An Interdisciplinary Approach - فصل Recursion
• MIT OCW 6.001 SICP - Lecture 1B: Procedures and Processes (ocw.mit.edu)
• Real Python - Thinking Recursively in Python (realpython.com/python-thinking-recursively)
• Python Wiki - Tail Call Optimization in Python (wiki.python.org/moin/TailCall)