أهداف التعلم

في نهاية هذا القسم، ينبغي أن تكون قادرًا على:

• تحديد الحالة العَودية والحالة الأساسية في خوارزمية عَودية.
• توضيح كيفية حساب حل عَودي لدالّة العاملي.

حساب العاملي

يُعرّف عاملي عدد صحيح موجب بأنه حاصل ضرب ذلك العدد في جميع الأعداد الصحيحة الموجبة الأصغر منه.

مثال: 5! = 5 * 4 * 3 * 2 * 1

وبصيغة المعادلة العامة لعدد صحيح موجب n: n! = n * (n - 1) * (n - 2) * . . . * 1

تؤدي الصيغة أعلاه لعاملي n إلى صيغة عَودية: n! = n * (n - 1)!

وبالتالي، يعتمد عاملي n على قيمة العاملي عند n - 1. يمكن إيجاد عاملي n بتكرار عاملي n - 1 حتى يصبح (n - 1)! = 1! (نعلم أن 1! = 1). يمكن استخدام هذه النتيجة لبناء الحل الكامل كما هو موضّح في العرض التوضيحي أدناه.

تعريف دالّة عَودية

تُكتب الخوارزميات العَودية في Python كدوال. في الدالّة العَودية، تُنفَّذ إجراءات مختلفة بحسب قيمة المُعامِل المدخل. الشرط الجوهري في الدالّة العَودية أن تستدعي نفسها.

تُسمى القيمة التي تنطبق عليها العَودية الحالة العَودية. في الحالة العَودية، تستدعي الدالّة نفسها بجزء أصغر من المُعامِل المدخل. مثال: في الدالّة العَودية factorial()، المُعامِل الأولي هو عدد صحيح n. في الحالة العَودية للدالّة، الوسيط المُمرَّر إلى factorial() هو n - 1، وهو أصغر من n.

تُسمى قيمة n التي يُعرف حلها الحالة الأساسية. توقف الحالة الأساسية العَودية. يجب أن تتضمن الخوارزمية العَودية حالة أساسية؛ وإلا فقد تؤدي إلى حساب لا نهائي.

لحساب العاملي، تُعرّف دالّة عَودية، factorial()، بمُعامِل إدخال صحيح، n. عندما يكون n > 1، تنطبق الحالة العَودية. تستدعي factorial() نفسها بوسيط أصغر، n - 1. عندما يكون n == 1، يكون الحل معروفًا لأن 1! هو 1؛ وبالتالي، n == 1 هي حالة أساسية.

ملاحظة: يُعرّف 0! بأنه 1؛ وبالتالي، n == 0 هي حالة أساسية ثانية لـ factorial(). عندما يكون n < 1، تُرجَع رسالة خطأ.

def rec_fact(n):
  return n * rec_fact(n - 1)

def rec_fact(n):
  if n < 0:
    print("error")
  elif n == 0:
    return n
  else:
    return n * rec_fact(n - 1)

def rec_fact(n):
  if n < 0:
    print("error")
  elif n == 0:
    return 1
  else:
    return n * rec_fact(n - 1)

def rec_fact(n):
  if n < 0:
    return -1
  else:
    return n * rec_fact(n - 1)