15  الإجراء المتسلسل

ملاحظة

هذا مبحثٌ شيِّق، وقد يكون فيه شيءٌ من الصعوبة، لكنّ فيه أدوات فعَّالة في استعمال المنطق البرمجي لأقصى مدى. لكنها غير مطلوبة لفهم ما يأتي من الأبواب.

الإجراء المتسلسل (Recursive Function): هو إجراء يطلب نفسه؛ بشكل مباشر أو غير مباشر. وحتى يكون مثمرًا: يجب أن تؤول سلسلة الطلبات هذه إلى جملة تُنهي التسلسل.

مثال: المضروب

فمثلا: تعرف الرياضيات مضروب العدد

\[ !n = n(n-1)(n-2)\cdots(1) \]

فهي عملية ضرب لكل عدد مع الذي قبله حتى ينتهي للواحد. ونمثل هنا لمضروب العدد 5:

\[ !5 = (5)(4)(3)(2)(1) = 120 \]

ولك أن تصف نفس العملية هكذا:

\[ !n = n !(n-1) \]

أي أن مضروب العدد هو ضربُ هذا العدد في مضروب العدد الذي قبله. وذلك يتسلسل على النحو التالي:

\[ \begin{align*} !5 &= (5)!(4) \\ &= (5)(4!(3)) \\ &= (5)(4(3!(2))) \\ &= (5)(4(3(2!(1)))) \\ &= (5)(4(3(2(1)))) \\ &= (5)(4)(3)(2)(1) \\ &= 120 \end{align*} \]

إذاً نعرِّف المعادلة في بايثون هكذا:

def factorial(n: int) -> int:
    # Recursive case (تسلسل)
    if n > 0:
        recursive_result = factorial(n - 1)
        return n * recursive_result
    # Terminal case (نهاية)
    return 1

factorial(5)

120

حيث لدينا حالتان:

• عندما تكون n > 0 يتم الطلب الذاتي : recursive_result = factorial(n - 1) إذْ هي جملة متسلسلة تكدِّس طلبات فوق طلبات؛ لكنها تؤول في النهاية إلى الجملة التي تُنهي التسلسل
• return 1 هي الجملة التي تنهي التسلسل

وهنا قطعة نص برمجي نستعملها لتصور تسلسل الطلبات:

def factorial(n: int, depth: int = 0) -> int:

    # Recursive case (تسلسل)
    print(f"{'  ' * depth}Call factorial({n})")
    if n > 0:
        result = n * factorial(n - 1, depth + 1)
        print(f"{'  ' * depth}Return {result} from factorial({n})")
        return result
    
    # Terminal case (نهاية)
    print(f"{'  ' * depth}Return 1 from factorial({n})")
    return 1

factorial(5)

Call factorial(5)
  Call factorial(4)
    Call factorial(3)
      Call factorial(2)
        Call factorial(1)
          Call factorial(0)
          Return 1 from factorial(0)
        Return 1 from factorial(1)
      Return 2 from factorial(2)
    Return 6 from factorial(3)
  Return 24 from factorial(4)
Return 120 from factorial(5)

120

• فكل طلب يُنشأ له ظرف تنفيذ جديد تكون بالنسبة له قيمة n هي المعيَّنة له وقت النداء.
• وهكذا يتم تكديس الطلبات حتى ينتهي التسلسل عند الطلب factorial(0) الذي يؤول لنتيجة مباشرة: return 1 فيخلَّى هذا الظرف من الذاكرة وتعود نتيجته إلى الظرف المباشر الذي استدعاه وهو ظرف factorial(1).
• فتتعين القيمة recursive_result = 1 وينتقل إلى الجملة التي بعدها وهي جملة الرجوع بنتيجة return n * recursive_result وهُما معيَّنان، أي تكون الجملة في واقع الظرف: return 1 * 1.
• وهذه النتيجة تعود للظرف الذي استدعاه وهو factorial(2) … إلخ.

طلب الإجراء المتسلسل يؤدي إلى ظروف متداخلة تؤول إلى ظرف واحد في النهاية.

يستعمل الإجراء المتسلسل وكذلك هياكل البيانات المتسلسلة بشكل كبير في الخوارزميات الفعالة.

يسهل كتابة بعض الخوارزميات باستعمال الإجراء المتسلسل. لكن قد تكون (أحياًنا) أقل أداءً من استعمال الحلقات.