شرح Memoisation وRecursion وحلقات for في بايثون باستخدام مثال فيبوناتشي

في البرمجة، لا توجد طريقة واحدة صحيحة لحل كل مشكلة. أحياناً يكون الحل التكراري باستخدام الحلقات هو الأنسب، وأحياناً يكون الاستدعاء الذاتي أكثر وضوحاً، وفي حالات أخرى يمكن لتقنية memoisation أن تمنحنا أداءً أفضل بكثير. لفهم هذه الفروقات عملياً، سنستخدم مثالاً شهيراً في علوم الحاسوب: متتالية فيبوناتشي.

متتالية فيبوناتشي تبدأ عادة بالشكل التالي: 0, 1, 1, 2, 3, 5, 8… وكل عدد فيها يساوي مجموع العددين السابقين له. على سبيل المثال:

• 0 + 1 = 1
• 1 + 1 = 2
• 1 + 2 = 3
• 2 + 3 = 5

يمكنك تجربة الأمثلة الواردة هنا في Jupyter أو Google Colab أو أي محرر شيفرات أو بيئة تطوير تدعم لغة Python.

تنفيذ متتالية فيبوناتشي باستخدام حلقة for في بايثون

الطريقة الأولى هي الاعتماد على التكرار باستخدام حلقة for. هذه المقاربة مناسبة عندما نريد حلاً مباشراً وواضحاً مع استهلاك منخفض للذاكرة.

الفكرة بسيطة: نبدأ بالقيمتين الأوليين في المتتالية، ثم نكرّر العملية لإنتاج القيمة التالية في كل دورة.

def fibonacci_for(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fibonacci_for(10))

لماذا تُعد هذه الطريقة فعّالة؟

• تعقيد الزمن غالباً هو O(N) لأننا نكرّر الحساب N مرة تقريباً.
• تعقيد المساحة هو O(1) لأننا نحتفظ بعدد ثابت من المتغيرات فقط.
• سهلة الفهم والتتبع مقارنة ببعض الأساليب الأخرى.

مع ذلك، قد تختلف الكفاءة العملية بحسب حجم الأعداد نفسها، لأن العمليات على أعداد كبيرة جداً في بايثون تصبح أكثر كلفة مع ازدياد عدد الخانات.

قياس الأداء باستخدام %timeit

عند تجربة الأداء داخل بيئة مثل Jupyter، يمكن استخدام الأداة %timeit لقياس زمن التنفيذ بشكل أكثر موثوقية من القياس اليدوي.

%timeit fibonacci_for(10)

تنفيذ فيبوناتشي باستخدام Recursion في بايثون

الاستدعاء الذاتي أو recursion هو أسلوب تعتمد فيه الدالة على استدعاء نفسها لحل أجزاء أصغر من المشكلة. هذا الأسلوب أنيق من الناحية النظرية، لكنه قد يصبح مكلفاً عند غياب التحسينات المناسبة.

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

print(fibonacci_recursive(10))

في هذا المثال، كل استدعاء للدالة يولّد استدعاءين جديدين تقريباً، ما يؤدي إلى تكوين شجرة استدعاءات تتضخم بسرعة كبيرة مع زيادة قيمة n.

الحالة الأساسية في الاستدعاء الذاتي

نجاح الدالة التكرارية يعتمد على وجود حالة أساسية واضحة توقف سلسلة الاستدعاءات. في فيبوناتشي تكون الحالات الأساسية عادة:

• Fibonacci(0) = 0
• Fibonacci(1) = 1

ومن ثم:

Fibonacci(2) = Fibonacci(1) + Fibonacci(0) = 1 + 0 = 1

تحليل التعقيد

• تعقيد المساحة: O(N) بسبب مكدس الاستدعاءات call stack.
• تعقيد الزمن: يُقدَّر غالباً بـ O(2^N) في الصيغة التقليدية، لأن الدالة تعيد حساب القيم نفسها مرات كثيرة.

هذا يعني أن الأسلوب التكراري المباشر ليس مناسباً للحسابات الكبيرة، حتى لو كان سهل التعبير من ناحية رياضية.

%timeit fibonacci_recursive(10)

تحسين الاستدعاء الذاتي باستخدام Memoisation

تقنية memoisation تعني تخزين نتائج الاستدعاءات السابقة، ثم إعادة استخدامها عند طلب المدخلات نفسها مرة أخرى. بهذه الطريقة نتجنب الحسابات المكررة التي تجعل الاستدعاء الذاتي البسيط بطيئاً جداً.

يمكن تطبيق هذه الفكرة باستخدام قاموس dictionary أو مصفوفة، أو حتى عبر أدوات جاهزة في بايثون مثل lru_cache.

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(10))

في هذا النهج، عندما نحسب مثلاً قيمة fibonacci_memo(8) مرة واحدة، فلن نحتاج لإعادة حسابها لاحقاً إذا طُلبت من جديد أثناء نفس العملية.

لماذا يغيّر memoisation الأداء بشكل كبير؟

• يمنع تكرار الحسابات لنفس المدخلات.
• يجعل الاستدعاء الذاتي عملياً في مسائل كثيرة.
• يفيد خصوصاً عندما تتكرر الحالات الفرعية بشكل كبير.

عملياً، في حالة فيبوناتشي، يمكن أن ينخفض التعقيد الزمني إلى O(N) لأن كل قيمة تُحسب مرة واحدة فقط، بينما يصبح تعقيد المساحة O(N) بسبب التخزين المؤقت ومكدس الاستدعاءات.

%timeit fibonacci_memo(10)

مقارنة بين حلقة for وrecursion وmemoisation

أي طريقة أفضل؟

لا توجد إجابة واحدة تناسب كل السيناريوهات. الاختيار يعتمد على طبيعة المشكلة ومتطلبات الأداء والوضوح:

1. إذا كنت تريد أبسط حل عملي وأقل استهلاكاً للذاكرة، فغالباً ستكون حلقة for هي الخيار الأفضل.
2. إذا كنت تشرح فكرة رياضية أو تبني حلاً يعتمد طبيعياً على التقسيم إلى مسائل أصغر، فقد يكون recursion أكثر تعبيراً.
3. إذا كانت المشكلة تحتوي على حالات فرعية متكررة، فإن memoisation يمنحك توازناً ممتازاً بين وضوح الاستدعاء الذاتي وتحسين الأداء.

ومن المهم أيضاً معرفة أن بعض اللغات البرمجية تدعم تحسين tail call optimization، ما يقلل عبء الاستدعاء الذاتي. لكن لغة Python لا تعتمد هذا التحسين بالشكل الذي يجعل الاستدعاء الذاتي بديلاً مباشراً للحلقات في جميع الحالات.

نصائح عملية عند تطبيق هذه الأساليب في بايثون

• استخدم الحلقات عندما تكون الأولوية للأداء والبساطة.
• تجنب الاستدعاء الذاتي التقليدي في القيم الكبيرة دون تخزين مؤقت.
• فكّر في استخدام functools.lru_cache إذا أردت تطبيق memoisation بطريقة نظيفة ومختصرة.
• اختبر الأداء باستخدام %timeit بدلاً من الاعتماد على الانطباع فقط.
• حلّل التعقيد الزمني والمساحي قبل اعتماد أي نهج في مشروع حقيقي.

الخلاصة التقنية

مثال فيبوناتشي يكشف بوضوح كيف يمكن لنفس المشكلة أن تُحل بطرق متعددة تختلف جذرياً في الأداء والبنية. من الناحية العملية، تظل حلقة for الخيار الأكثر كفاءة وبساطة في بايثون لهذا النوع من المسائل، بينما يُعد recursion مفيداً لفهم منطق الحل وليس دائماً لتنفيذه كما هو. أما memoisation فهي تقنية ذكية تعالج نقطة ضعف الاستدعاء الذاتي عبر إعادة استخدام النتائج، وتُعد خياراً ممتازاً عندما تتكرر المسائل الفرعية بكثرة.