تعلم البرمجة مفهوم التعاودية Recursion

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

سنشرح في هذا المقال ما يلي:

• تعريف التعاودية، وكيفية عملها.
• كيف تساعد التعاودية في تبسيط بعض المشاكل الصعبة.

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

رغم قولنا سابقًا إن الحلقات التكرارية loops هي إحدى ركائز البرمجة، إلا أنه يمكننا كتابة برامج كاملة دون استخدام صريح لهذه البنية، بل إن بعض اللغات مثل Scheme لا تحوي بنية حلقة تكرارية صريحةً مثل For وWhile وغيرهما، وإنما تستخدم تقنيةً تسمى التعاودية، وقد تبين أن هذه التقنية قوية للغاية في حل بعض أنواع المشاكل، وهي تعني تطبيق دالة كجزء من تعريف نفس الدالة، ولننظر مثالًا على ذلك أحد الاختصارات التعاودية المشهورة في الكلمات، وهو أحد أساليب التلاعب بالاختصارات يحتوي الاختصار نفسه على كلمة تطابق حروف الاختصار، مثل مشروع GNU مثلًا -وهو أحد أهم المشاريع في البرمجيات مفتوحة المصدر- والذي تشير حروف كلمته إلى "نظام GNU ليس يونكس" أو GNU's Not UNIX، فتكون اختصارًا تعاوديًا لأن كلمة GNU التي في الاختصار هي نفسها كلمة GNU المختصرة كلها، أما معنى الكلمة الحرفي فهو حيوان الثور الإفريقي.

ويجب أن يوجد في الدالة شرط إنهاء، بحيث تتفرع الدالة إلى حل غير تعاودي عند نقطة ما، على عكس مثال GNU الذي ليس فيه هذا الشرط ويظل يتعاود إلى ما لا نهاية، وهو ما نطلق عليه الحلقة اللانهائية infinite loop.

لننظر هنا في مثال بسيط، تُعرَّف فيه دالة المضروب الرياضي factorial function المشار إليها بعلامة التعجب بعد العدد n!‎، على أنها ناتج ضرب جميع الأعداد من الواحد حتى العدد المطلوب -بما في ذلك العدد نفسه-، ومضروب الصفر هو الواحد، فإذا أردنا التعبير عن هذا المثال بطريقة أخرى فسنقول إن مضروب N يساوي (N(N-1، وعليه سيكون:

1! = 1
  2! = 1 x 2 = 2
  3! = 1 x 2 x 3 = 2! x 3 = 6
  N! = 1 x 2 x 3 x .... (N-2) x (N-1) x N = (N-1)! x N

ويمكن التعبير عن ذلك في بايثون كما يلي:

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

يجب أن تنتهي الدالة بما أننا نقلل قيمة N في كل مرة ونتحقق هل تساوي 1 أم لا، لكن ثمة مشكلة بسيطة في هذا التعريف، إذ سيدخل في حلقة لا نهائية إذا استدعيناه برقم سالب، ولحل هذا نضيف اختبارًا للتحقق من أن n أقل من صفر، ويعيد None إذا كان كذلك لأن مضروب العدد السالب غير معرَّف undefined.

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

لنرى الآن كيف يكون هذا عند تنفيذه، لاحظ أن تعليمة الإعادة تعيد * n (نتيجة استدعاء المضروب التالي)، فنحصل على ما يلي:

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1

وتعود بايثون أدراجها لتستبدل القيم كما يلي:

factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

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

التعاودية على القوائم

إحدى الحالات التي تكون التعاودية مفيدةً فيها هي معالجة القوائم Lists، بشرط أن نستطيع التحقق من فراغ القائمة، وتوليد قائمة دون عنصرها الأول، ونفعل هذا في بايثون باستخدام تقنية تسمى التشريح Slicing، لكن كل ما يجب معرفته في هذا الفصل هو أن استخدام فهرس [‎1:‎] يعيد جميع العناصر من العنصر ذي الفهرس 1 حتى نهاية القائمة، لذا نكتب ما يلي لنصل إلى العنصر الأول من قائمة اسمها L:

first = L[0] # استخدم الفهرسة العادية

وللوصول إلى بقية القائمة:

# استخدم التشريح للوصول إلى العناصر 1،2،3 وما بعدها
butfirst = L[1:] 

لنجرب ذلك في محث بايثون، لنتأكد أنه يعمل:

>>> L =[1,2,3,4,5]
>>> print( L[0] )
1
>>> print( L[1:] )
[2,3,4,5]

نعود الآن إلى استخدام التعاودية لطبع القوائم، ولنفرض حالةً نطبع فيها كل عنصر من قائمة سلاسل نصية باستخدام الدالة printList:

def printList(L):
    if L:
        print( L[0] )
        printList(L[1:])

إذا تحققت L -أي كانت true ولم تكن فارغةً- فسنطبع العنصر الأول، ثم نعالج بقية القائمة كما يلي:

# شيفرة وهمية ليست بايثون
PrintList([1,2,3])
   prints [1,2,3][0] => 1
   runs printList([1,2,3][1:]) => printList([2,3])
   => we're now in printList([2,3])
         prints [2,3][0] => 2
         runs printList([2,3][1:]) => printList([3])
         => we are now in printList([3])
               prints [3][0] => 3
               runs printList([3][1:]) => printList([])
               => we are now in printList([])
                     "if L" is false for an empty list, so we return None
         => we are back in printList([3])
               it reaches the end of the function and returns None
   => we are back in printList([2,3])
         it reaches the end of the function and returns None
=> we are back in printList([1,2,3])
   it reaches the end of the function and returns None

لاحظ أن الشرح أعلاه مأخوذ من شرح في نشرة تعليم بايثون البريدية بواسطة Zak Arnston بتاريخ يوليو 2003.

يسهل تنفيذ هذا الأمر لقائمة بسيطة باستخدام حلقة for، لكن ماذا لو كانت القائمة معقدةً وتحتوي قوائم أخرى فيها، فإذا استطعنا التحقق من كون عنصر ما قائمةً باستخدام دالة type()‎ المضمنة وكان قائمة حقًا؛ فسنستدعي printList()‎ تعاوديًا، أما إن لم يكن قائمةً فنطبعه:

def printList(L):
    # لا تفعل شيًا إن كانت فارغة
    if not L: return
    # على العنصر الأول printList إذا كانت قائمة فاستدع
    if type(L[0]) == list:
        printList(L[0])
    else: # لا توجد قوائم لذا نطبع هنا 
        print( L[0] ) # L نعالج بقية عناصر  
    printList( L[1:] )

سيصعب تنفيذ ذلك باستخدام الحلقة التكرارية العادية، ويظهر الفرق مع استخدام التعاودية في تسهيل ذلك التنفيذ، لكن ثمة مشكلة هنا، فالتعاودية على بنى البيانات الكبيرة يستهلك الذاكرة كثيرًا، لذا عند وجود ذاكرة صغيرة أو بنى بيانات كبيرة لمعالجتها، فيجب تفضيل الشيفرة المعتادة للأمان، وبسبب مشكلة الذاكرة تلك واحتمال أن يتعطل المفسر interpreter بسببها فقد وضعت بايثون حدًا لعدد مستويات التعاودية التي تسمح بها، فإذا تجاوزنا ذلك الحد فسيُنهى برنامجنا مع خطأ RecusrionError، والذي نلتقطه باستخدام try/except:

  >>> def f(n): return f(n+1)

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

جافاسكربت ولغة VBScript

تدعم كل من لغة جافاسكربت ولغة VBScript التعاودية، لكن بما أننا ذكرنا كل شيء تقريبًا فسنتركك مع نسخة تعاودية من دالة المضروب للغتين:

<script type="text/vbscript">
Function factorial(N)
   if N < 0 Then
      Factorial = -1   'a negative result is "impossible"
   if N = 0 Then
      Factorial = 1
   Else
      Factorial = N * Factorial(N-1)
   End If
End Function

Document.Write "7! = " & CStr(Factorial(7))
</script>

<script type="text/javascript">
function factorial(n){
   if (n < 0)
      return NaN  // NaN - Not a Number - يعني أنه غير صالح 
   if (n == 0)
      return 1;
   else
      return n * factorial(n-1);
};

document.write("6! = " + factorial(6));
</script>

لننظر الآن في البرمجة الدالية Functional Programming (أو البرمجة الوظيفية) في الفصل التالي.

خاتمة

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

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

ترجمة -بتصرف- للفصل العشرين: Recursion, or doing it to yourself، من كتاب Learn To Program لصاحبه Alan Gauld.

اقرأ أيضًا

• المقال التالي: مقدمة إلى البرمجة الوظيفية Functional Programming
• المقال السابق: برمجة الواجهات الرسومية باستخدام Tkinter
• التعاود recursion والمكدس stack في جافاسكربت
• التعاود recursion في جافا
• مفهوم التعاود (Recursion) والكائنات القابلة للاستدعاء (Callable Objects) في Cpp