الاستدعاء الذاتي في

نبذة عن الاستدعاء الذاتي

الاستدعاء الذاتي أسلوب لتنفيذ الكود داخل دالة بشكل متكرر، عن طريق استدعاء الدالة لنفسها. وتُعرف الدوال التي تستدعي نفسها باسم الدوال ذاتية الاستدعاء. ويمكن النظر إلى الاستدعاء الذاتي على أنه طريقة أخرى لتنفيذ الحلقات أو التكرار. وكما في الحلقات، يُستخدم تعبير منطقي أو اختبار True/False لتحديد متى يتوقف التنفيذ عبر الاستدعاء الذاتي.

و_بخلاف_ الحلقات، فإن الاستدعاء الذاتي بدون شرط توقف في Python لا يمكن أن يستمر إلى ما لا نهاية. تُوضع القيم المستخدمة في كل استدعاء للدالة في إطار خاص بها على مكدّس مفسّر Python. وإذا استهلك العدد الإجمالي لاستدعاءات الدوال مساحة أكبر مما يتّسع له المكدّس، فسيؤدي ذلك إلى خطأ.

الحلقات مقابل التنفيذ بالاستدعاء الذاتي

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

أما الاستدعاء الذاتي، فبدلًا من تحديث حالة المتغيّرات، يمكنه تمرير قيم محدَّثة مباشرةً كوسائط إلى الاستدعاء (التكرار) التالي للدالة نفسها. وهذا يقلّل الازدحام في جسم الدالة، وقد يوضّح كيف يحدث كل تحديث. لكنه أيضًا تنفيذ أقل كفاءة، إذ يضيف كل استدعاء للدالة نفسها إطارًا آخر إلى المكدّس.

الاستدعاء الذاتي: لماذا ولماذا لا؟

إذا كان هناك خطر التسبّب في خطأ في المكدّس أو تجاوز سعته، فلماذا قد يستخدم أحدهم استراتيجية الاستدعاء الذاتي لحل مشكلة؟ قابلية القراءة، وقابلية التتبّع، والقصد. قد تكون هناك حالات يكون فيها الحل أكثر وضوحًا و/أو أسهل في التفكير والتحليل عندما يُعبَّر عنه بالاستدعاء الذاتي مقارنةً بالحلقات. وقد تكون هناك أيضًا قيود برمجية تتعلق باستخدام البيانات أو تغييرها، وإدارة التعقيد، وتفويض المسؤولية، أو تنظيم أعباء العمل.

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

الحلقات مقابل استراتيجية الاستدعاء الذاتي: قلق إنديرا

تُودَع إعانة الضمان الاجتماعي الشهرية الخاصة بإنديرا تلقائيًا في حسابها البنكي في الأربعاء الثاني من كل شهر. وتقلق إنديرا بشأن تسوية دفتر شيكاتها. فهي تخشى أن تكتب شيكات قبل إيداع أموالها. وتطلب من حفيدتها أديا أن تزوّدها بقائمة بالتواريخ التي ستظهر فيها أموالها في حسابها.

وتكتب أديا، التي بدأت للتو تعلّم البرمجة بلغة Python، برنامجًا بناءً على أفكارها الأولى. تريد أن تُرجع list بتواريخ الإيداع حتى يمكن طباعتها. وتريد كتابة دالة تعمل مع أي سنة. وحرصًا على الحالة التي يتغيّر فيها الجدول الزمني (أو التي يريد فيها أقارب آخرون أن تحسب أديا جداول إيداعاتهم)، تقرّر أن الدالة تحتاج إلى معامل إضافي لـ_يوم الأسبوع_. وأخيرًا، تقرّر أديا أن الدالة تحتاج إلى معامل يحدّد أي يوم من أيام الأسبوع في الشهر: الأول، الثاني، وهكذا. ولتلبية كل هذه المتطلبات، تقرّر استخدام صنف date المستورد من datetime. وبجمع كل ذلك معًا، تتوصّل أديا إلى ما يلي:

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

هذه المحاولة الأولى تعمل، لكن أديا تتساءل إن كان بإمكانها إعادة هيكلة الكود لاستخدام أسطر أقل وحلقات متداخلة أقل. وقد قرأت أيضًا أنه من الجيد تقليل تغيير الحالة، لذا تريد أن ترى إن كان بإمكانها تجنّب تغيير بعض متغيّراتها مثل output وmonth وday_num.

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

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

تسعد أديا لأنه لم تبقَ حلقات متداخلة، ولا حالة معدَّلة، وبسطرين أقل من الكود!

لكنها قلقة قليلًا من أن أسلوب الاستدعاء الذاتي يستخدم خطوات أكثر من أسلوب الحلقات، وبالتالي فهو «أقل أداءً». لكن إعادة كتابة المسألة باستخدام الاستدعاء الذاتي ساعدتها بالتأكيد على التعامل مع الحلقات المتداخلة القبيحة (وهي خطر على الأداء)، والتعديل المفرط للحالة، والالتباس حول المنطق الشرطي المعقّد. كما يبدو الكود أكثر «وضوحًا». وهي واثقة من أنها حين تعود إلى هذا الكود بعد انقطاع، ستتمكّن من قراءته وتذكّر ما يفعله بسهولة أكبر.

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

وحتى في وقت لاحق، عندما تتعلّم عن tuples، قد تفكّر أديا في أساليب «تحسين» إضافية، مثل استخدام list comprehension مع Calendar.itermonthdates، أو حفظ بعض القيم مؤقتًا.

صيغة أخرى للاستدعاء الذاتي: نداء الذيل

نداء الذيل هو عندما تكون العبارة الأخيرة في الدالة مجرّد استدعاء لها لنفسها دون أي شيء آخر. هذا المثال ليس نداء ذيل، لأن الدالة تضيف 1 إلى نتيجة استدعائها لنفسها:

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

سيطبع هذا:

The step is 1
The step is 2
retval is 3 after recursion

لإعادة هيكلته إلى نداء ذيل، اجعل retval معاملًا في print_increment.

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

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

حدود الاستدعاء الذاتي في Python

تستطيع بعض اللغات تحسين نداءات الذيل بحيث يعيد كل استدعاء ذاتي استخدام إطار المكدّس الخاص بالاستدعاء الأول للدالة (تمامًا كما تعيد الحلقة استخدام الإطار نفسه)، بدلًا من إضافة إطار آخر إلى المكدّس. وPython ليست من تلك اللغات. وللحماية من تجاوز سعة المكدّس، لدى Python حدّ للاستدعاء الذاتي قيمته الافتراضية ألف إطار. ويُرفع استثناء RecursionError عندما يكتشف المفسّر أن حدّ الاستدعاء الذاتي قد تجاوزته. ومن الممكن استخدام الطريقة sys.setrecursionlimit لزيادة حدّ الاستدعاء الذاتي، لكن فعل ذلك ينطوي على خطر حدوث خطأ في تجزئة الذاكرة أثناء التنفيذ يؤدي إلى انهيار البرنامج، وربما نظام التشغيل.

مصادر

لتعلّم المزيد عن استخدام الاستدعاء الذاتي في Python يمكنك البدء بـ

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively