العودية

١دالة تستدعي نفسها

العودية Recursion: أن تحل الدالة المسألة باستدعاء نفسها على نسخة أصغر من المسألة نفسها. مثل الدمى الروسية: تفتح الدمية فتجد دمية أصغر، حتى تصل إلى أصغر دمية لا تُفتح.

def factorial(n):    if n == 0:              # حالة التوقف        return 1    return n * factorial(n - 1)   # الخطوة العودية print(factorial(5))

٢تتبّع الاستدعاءات

كل استدعاء ينتظر نتيجة الاستدعاء الأصغر. اضغط «التالي» وراقب n وهي تنقص حتى 0، ثم النتائج وهي تعود صعودًا:

def factorial(n):    if n == 0:        return 1    return n * factorial(n - 1) print(factorial(3))

يحفظ بايثون الاستدعاءات المنتظرة في مكدس الاستدعاءات Call Stack: آخر استدعاء يُحل أولًا، كما في المكدس الذي عرفته في الدرس 2.

٣أمثلة أخرى

def total(a):    """مجموع عناصر القائمة بالعودية"""    if len(a) == 0:        return 0    return a[0] + total(a[1:]) def power(x, n):    if n == 0:        return 1    return x * power(x, n - 1) def count_down(n):    if n == 0:        print("انطلق!")        return    print(n)    count_down(n - 1) print(total([4, 7, 1, 8]))print(power(2, 10))count_down(3)

٤بلا حالة توقف: انهيار

def forever(n):    return forever(n + 1)    # لا توجد حالة توقف forever(1)

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

٥العودية أم الحلقة؟

كل حل عودي يمكن كتابته بحلقة، والعكس. فمتى نختار العودية؟

# المضروب بحلقة: الناتج نفسه بلا مكدس استدعاءاتdef factorial_loop(n):    result = 1    for k in range(2, n + 1):        result *= k    return result print(factorial_loop(5))