استمع إلى المقال

رأينا حتى الآن في دورة تعلم لغة كوتلن، كيف أن الدوال تعتبر كائنات من الدرجة الأولى في لغة كوتلن. وهذا الأمر يرجع في أغلبه، إلى اعتماد لغة كوتلن، نمط البرمجة الوظيفية الذي تكون به الدوال هي الأساس في البرنامج. ومن ضمن أهم الدوال في هذا النمط، هي الدالة التعاوديّة Recursive Function، التي تستخدم مفهوم التعاودية أو العودية Recursion.

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

الدالة التعاوديّة Recursive Function:

هي الدالة التي تطبِّق مفهوم التعاوديّة Recursion، وتقوم باستدعاء نفسها بطريقة متكررة. وأبسط مثال لها، إذا أردنا طباعة النجمة (*) لعدد محدد من المرات، يمكننا استخدام الدالة كالتالي:

fun stars(n: Int) {
    if (n < 1) return
    print("*")
    stars(n - 1)
}

لدى الدالة معامل أسميناه n تستقبل به عدد معين. داخل الدالة، نفحص ما إذا كان العدد المُرسل لها أكبر من 0. إذا لم يكن العدد أكبر من 0، سيتم تنفيذ التعبير return وينتهي عمل الدالة ولن يتم تنفيذ الأسطر بعد كتلة if.

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

عند استدعاء الدالة أعلاه في دالة ()main مثلًا، يجب أن نرسل لها عدد النجمات الذي نريد طباعته:

fun main() {
    stars(5)
}

وستكون نتيجة الطباعة هي:

*****

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

ولفهم هذا الأمر أكثر، دعونا نرى مثال آخر أكثر تعقيدًا من السابق.

مضروب العدد Factorial Function:

من ضمن أشهر الأمثلة للدالة التعاودية، هي استخدامها في المفهوم الرياضي مضروب الأعداد الصحيحة الموجبة. ومضروب العدد الصحيح، هو حساب ضرب كل الأعداد التي تسبق هذا العدد، بداية من العدد 1 وحتى العدد نفسه.  كمثال، مضروب العدد 5 هو: 1 * 2 * 3 * 4 * 5 والذي يساوي 120.

ويمكننا فهم ذلك بالطريقة التالية:

علينا ضرب كل الأعداد الموجبة الأصغر من أو التي تساوي العدد المُراد. وفي حالة العدد 5، يمكن تمثيل ذلك كالتالي:

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

لإيجاد مضروب العدد 5، يتم ضرب العدد 5 في مضروب العدد 1 – 5 أي مضروب العدد 4 والذي لا تُعرف نتيجته بعد. لذلك نوجد مضروب العدد 4 أولًا، والذي بدوره هو ضرب العدد 4 في مضروب العدد 1 – 4 أي مضروب العدد 3. والذي لإيجاده، يجب أن نضربه في مضروب العدد الذي يسبقه، أي 1 – 3 وهو العدد 2. ولإيجاد مضروب العدد 2، يجب أن نضربه في مضروب العدد الذي يسبقه، وهو العدد 1.

بعد إيجاد مضروب العدد 1، والذي دائمًا يساوي 1، سنعود إلى الأعلى. ونستطيع الآن معرفة مضروب العدد 2، لأنه يساوي مضروب العدد 1 في العدد 2، أي 1 * 2 والنتيجة هي 2. وبما أن مضروب العدد 2 أصبح معروفًا، يمكننا إيجاد مضروب العدد 3، والذي يساوي 6 = 2 * 3. ثم مضروب العدد 4، ويساوي 24 = 6 * 4. وأخيرًا، نصل إلى عددنا الأول 5، والذي يمكن إيجاد مضروبه الآن، بما أن مضروبه يعتمد على مضروب العدد 4، ومضروب العدد 4 يساوي 24. إذًا مضروب العدد 5 يساوي: 120 = 24 * 5.

ولأن العدد المُراد إيجاد مضروبه من الممكن أن يكون أي عدد صحيح موجب، نرمز له بالحرف n. لذلك يمكننا أن نقول، أن مضروب العدد n هو:

factorial(n) = n * factorial(n - 1)

إيجاد مضروب العدد عبر دالة تعاودية في كوتلن:

ويمكننا تمثيل كل ذلك في شفرة كوتلن عبر دالة تعاودية، كالتالي:

fun factorial(n: Long): Long {
    if (n <= 1) return 1
    return n * factorial(n - 1)
}

تستقبل الدالة العدد المُراد إيجاد مضروبه عبر معاملها n. ثم عبر كتلة if يتم فحص ما إذا كان العدد مازال أكبر من أو يساوي 1 في كل مرة يتم استدعاؤها.

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

وعند استدعاء الدالة وإرسال أي عدد:

fun main() {
    val fact1 = factorial(5)
    val fact2 = factorial(17)

    println(fact1)
    println(fact2)
}

ستكون نتيجة الطباعة هي مضروب العدد الذي تم إرساله للدالة:

factorial(5) = 120
factorial(17) = 355687428096000

نلاحظ أنه سيتم تكرار استدعاء الدالة بعدد مساوي للعدد n. أي في حالة العدد 5 استدعاء الدالة 5 مرات، وللعدد 17 هناك 17 استدعاء سيتم قبل إعادة النتيجة النهائية الخاصة به.

وبما أن كل استدعاء ينتظر نتيجة من استدعاء آخر للدالة كما رأينا أعلاه، إذًا لابد من أن يتم الاحتفاظ بكل استدعاء في الذاكرة. وهذا سيكون مكلفًا جدًا  فيما يخص مساحة الذاكرة المتوفرة للبرنامج في الـ JVM (إذا كان برنامجنا موجه للـ JVM). لأن كل دالة بما فيها المعاملات الخاصة بها، سيتم حجز مكان لها في ما يعرف بـ مكدس الاستدعاءات call stack أو مكدس التنفيذ execution stack.

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

مكدس الاستدعاءات Call Stack:

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

كيف تفهم الآلة التي يعمل بها برنامجنا (وهي هنا الـ JVM) ترتيب تنفيذ هذه الدوال؟ كيف يتم التبديل بينها؟ وكيف يتم التعرف على انتهاء عمل البرنامج؟

للإجابة على هذه الأسئلة، نحتاج إلى التعرف على نوع خاص من أنواع هياكل البيانات، والذي يعرف بـ مكدس الاستدعاءات call stack.

تستخدم الـ JVM مفهوم المكدس هذا، لفهم الدالة التي يجب استدعاؤها في هذه اللحظة والوصول إلى المعلومات المتعلقة بها. يتكون مكدس الاستدعاءات من إطارات مكدسة stack frames يُخزن بها معلومات عن الدوال التي لم يتم إنهاؤها بعد. تتضمن المعلومات المخزنة في الإطار: عنوان address الدالة في الذاكرة والمعاملات Parameters والمتغيرات Variables التي تم إعلانها داخل الدالة والعمليات الحسابية التي تجري داخلها وبعض البيانات الأخرى.

مكدس الاستدعاءات هو نوع خاص من المكدسات Stacks، والتي يتم اتباع قاعدة (Last In First Out (LIFO فيها. أي من يدخل إلى المكدس أخيرًا سيخرج أولًا. بنفس الطريقة التي يمكن أن نضع بها كتب داخل صندوق بحجم كتاب واحد. فعند وضع الكتب فوق بعضها داخل الصندوق، يمكننا إخراج آخر كتاب أدخلناه أولًا، وأول كتاب أدخلناه إلى الصندوق سيكون هو آخر من يخرج:

العمليات التي يمكننا إجراؤها على الـ Stack، هي الدفع push لدفع عنصر جديد في المكدس، والسحب pop لسحب أو حذف عنصر من المكدس. أمّا العنصر الذي تجري عليه هذه العمليات، فهو يعرف بالـ top وهو العنصر الأعلى في المكدس والذي دخل أخيرًا.

ففي الصورة التوضيحية أعلاه، عند إجراء عملية سحب على الكتاب رقم 7، أصبح ال top هو الكتاب رقم 6. وعند انتهاء عملية الدفع للكتاب رقم 8، سيصبح هو ال top. بالتالي لن يعود بالإمكان سحب الكتاب 6 لانه لم يعد ال top.

التعامل مع الدوال في مكدس الاستدعاءات

الصورة التالية، توضح عمل مكدس الاستدعاءات والذي يتم تخزين الدوال به:

يتم دفع push إطار مكدس الذي به معلومات الدالة، إلى أسفل مكدس الاستدعاءات. يتم إضافة إطار مكدس جديد عندما يتم استدعاء دالة جديدة. ويتم إزالة إطار المكدس من مكدس الاستدعاءات إذا تم الانتهاء من تنفيذ الدالة.

لنفهم هذا الكلام النظري، فلنقم بكتابة دوال ونرى كيف ستتعامل معها آلة الـ JVM.

مثال عملي لمكدس الاستدعاءات:

فلنفترض أنه لدينا دالة تطبع مربع العدد الذي نرسله إليها، ثم يتم استدعاء هذه الدالة في الدالة ()main:

fun main(vararg args: String) {

    val n = 4
    square(n)

}

fun square(n: Int) {
    val sqr = n * n
    println(sqr)
}

لدينا في الشفرة أعلاه، ثلاث استدعاءات لثلاث دوال مختلفة: ()main التي يتم استدعاؤها تلقائياً من قبل مترجم كوتلن، وداخلها استدعاء لدالة خاصة بنا وهي ()square. داخل ()square لدينا استدعاء لدالة الطباعة ()println. وهذا يعني، أنه ستتوفر ثلاث إطارات مكدس في مكدس الاستدعاءات:

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

الآن انتهت عملية الـ push لأنه لا وجود لاستدعاءات أخرى. وتبدأ عملية التنفيذ بداية من آخر الواصلين إلى المكدس، وهي دالة ()println. وبعد انتهاء تنفيذ الدالة، يتم عمل pop لها أي سحبها أو حذفها من المكدس. ثم الدالة التي تحتها، ويتم سحبها أيضًا بعد أن ينتهي تنفيذها. وأخيرًا، دالة ()main والتي كانت أول الواصلين، ولكن لأنها تقبع في آخر المكدس، تم تنفيذها أخيرًا. وبما أنه لا يوجد شيء آخر في المكدس، ينتهي تنفيذه بخروج دالة ()main منه.

يعمل أي برنامج كوتلن (إذا تم بناءه ليعمل على الـ JVM) أو أي برنامج لجافا بهذه الطريقة تقريبًا. عندما يكون المكدس فارغًا، ينتهي التنفيذ.

ملحوظة:

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

خطأ تجاوز سعة المكدس Stack Overflow:

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

لتجنب ذلك، يمكننا وضع شرط ينهي استدعاءات الدالة المتكررة لنفسها، كما فعلنا في مثال النجمة في أول فقرة من هذا الدرس. ولكن عند حذف كتلة if من شفرة طباعة النجمة، سيتم طباعة الكثير من النجمات بدون توقف. وفي مرحلةٍ ما، وعندما يمتلئ مكدس الاستدعاءات باستدعاءات دالة ()stars، يتم قذف الاستثناء StackOverflowError وتحطم البرنامج بالكامل.

لمعرفة ما حدث، نحتاج إلى قراءة رسالة تتبع المكدس Stack Trace، التي تُظهرها لنا كوتلن عند حدوث هذا الخطأ الاستثنائي.

تتبع المكدس Stack Trace:

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

كما يظهر في الصورة المتحركة أعلاه، عند تنفيذ الشفرة في برنامج IntelliJ، يتم أولًا طباعة الكثير من النجمات في تبويب Run. وهو نتيجة الاستدعاء المتكرر من قبل دالة ()stars لنفسها ودالة الطباعة ()print. وعند امتلاء مكدس الاستدعاءات بإطارات تحمل معلومات الدالتين، تم رمي الاستثناء وإظهار رسالة تتبع المكدس.

ما يهمنا في الرسالة هو اسم ونوع الاستثناء الذي حدث:

Exception in thread “main” java.lang.StackOverflowError

وأين حدث. هنا سنبحث في الرسالة عن اسم ملفات برنامجنا فقط. مثل اسم الملف الحالي Main.kt:

at functionalProgramming.recursion.MainKt.stars(Main.kt:9)

at functionalProgramming.recursion.MainKt.stars(Main.kt:10)

يظهر في السطرين، مكان الشفرة المتسببة في الخطأ. السطر 9 في ملف Main.kt، وهو السطر الذي به استدعاء دالة الطباعة ()print. والسطر رقم 10، والذي به استدعاء دالة ()stars الخاصة بنا.

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

استبدال التعاودية بحلقات التكرار:

لتجنب حدوث هذا الخطأ، يمكننا أن نستبدل الدوال التعاودية بحلقات التكرار. فمثلًا، في دالة أيجاد مضروب العدد، يتم دائمًا اتباع استدعاء (factorial(n باستدعاء (factorial(n – 1. وهذا يعني، أن أي استدعاء تالي ينقص عن السابق، بمقدار العدد 1.

أي أنه يتم استدعاء الدوال باستخدام النمط:

” n , n-1 , n-2 , n-3 … “

وعند معرفة ذلك، نجد أنه سيكون من الأسهل فعل ذلك باستخدام حلقة for:

fun factorial(n: Long): Long {
    var fact = 1L
    for (i in 1..n)
        fact *= i
    return fact
}

داخل الدالة، لدينا متغير fact قابل للتغيير mutable، قيمته الابتدائية هي العدد 1 (الحرف L لإخبار المترجم أن المتغير هو من النوع Long وليس Int). وداخل حلقة for، لدينا متغير خاص بها وهو الحرف i. ستدور الحلقة بداية من العدد 1 وحتى العدد n، وهو العدد الذي سيأتي للدالة عبر معاملها. ستدور الحلقة، بواقع خطوة أو عدد 1 إلى الأعلى، ليكون الفرق بين كل عدد والذي يسبقه، مقداره 1.

وفي كل دورة للحلقة، سيمثل المتغير i عدد من هذه الأعداد. ففي المرة الأولى، ستكون قيمته 1، والدورة الثانية 2، والثالثة 3، وهكذا حتى الوصول إلى قيمة n. وفي كل دورة للحلقة، يتم أيضًا إسناد قيمة جديدة للمتغير القابل للتغيير fact. بضرب قيمته الحالية في قيمة i الحالية.

ففي المرة الأولى، سيتم ضرب 1 وهي قيمة fact في 1 وهي قيمة i، وهذا يساوي 1 وهي القيمة التي سيتم إسنادها للمتغير fact. وفي الدورة الثانية، أصبحت قيمة i العدد 2 وقيمة fact العدد 1، 2 = 2 * 1، وسيتم إسناد نتيجة عملية الضرب العدد 2، إلى fact. أمّا في الدورة الثالثة، الآن i تساوي 3، و fact تساوي 2. نتيجة ضرب العددين 6 هي التي يتم إسنادها إلى fact. وهكذا إلى أن تنتهي الحلقة من الدوران على كل الأعداد التي تسبق العدد n.

وبعد انتهاء عمل الحلقة، تعيد الدالة قيمة المتغير fact. وعند استدعاء دالة ()factorial هذه المرة أيضًا ستكون النتيجة هي كالسابقة:

fun main() {

    println(factorial(5))
    println(factorial(17))
}

نتيجة الطباعة:

120
355687428096000

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

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

تقنية ذيل التعاودية Tail Recursion:

يمكننا في كوتلن استخدام الدوال التعاودية، وتجنب الوقوع في مشكلة StackoverflowError، باستخدام تقنية tail recursion. والهدف من هذه التقنية، هو تقليل حجم مكدس الاستدعاءات.

وليطبق المترجم هذه التقنية على الدالة التعاودية، يجب أن نسبقها بالكلمة المفتاحية tailrec:

tailrec fun stars(n: Int) {
    print("*")
    stars(n - 1)
}

هذه المرة لن تسبب دالة ()stars مشكلة، بل سيتم طباعة نجمات إلى ما لانهاية حتى تمتلئ ذاكرة الجهاز بها، أو نوقف البرنامج بأنفسنا. وهو ما تظهره الصورة المتحركة التالية:

شروط استخدام tailrec:

لتحسين الدوال التعاودية باستخدام tailrec، يجب أن يكون استدعاء الدالة هو آخر عملية تقوم بها الدالة. أي أن يكون الاستدعاء في ذيل أو آخر سطر في الدالة. فمثلًا، إذا كان لدينا الدالة التالية:

fun sum(n: Long): Long {
    if (n == 0L) return 0
    return n + sum(n - 1)
}

دالة ()sum هي دالة جمع كل الأعداد بداية من العدد n المرسل إليها، وحتى العدد 1. لن تحدث مشكلة عندما نرسل إليها أعداد صغيرة، لأن هناك شرط if سينهي عمل الدالة بمجرد أن تكون قيمة العدد تساوي 0.

ولكن عند إرسال أعداد كبيرة 100000 مثلًا، هنا سيتم رمي الاستثناء StackoverflowError وتحطم البرنامج. لماذا؟ لأنه سيكون هناك مائة ألف استدعاء لدالة ()sum، قبل أن نصل إلى العدد 0 في شرط كتلة If. هذا العدد الضخم من الاستدعاءات سيزيد من حجم المكدس بطريقة خيالية.

إذًا الحل هو تحسين هذه الشفرة باستخدام tailrec:

tailrec fun sum(n: Long): Long {
    if (n == 0L) return 0
    return n + sum(n - 1)
}

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

وهذا حدث لأن آخر سطر في الدالة، هو عملية حسابية تقوم بإضافة n إلى النتيجة العائدة من الاستدعاء (sum(n – 1 وليس استدعاء تعاودي فقط. لنتمكن من تحسين الشفرة عبر tailrec علينا أن نضع استدعاء الدالة، في آخر سطر:

tailrec fun sum(n: Long, accumulator: Long = 0): Long {
    return if (n == 0L) accumulator
     else sum(n - 1, accumulator + n)
}

التحسين الذي قمنا به، هو جعل العملية الحسابية تجري داخل الاستدعاء نفسه. ولفعل ذلك، قمنا بإضافة معامل جديد للدالة أسميناه accumulator. سنستخدم هذا المعامل، في تجميع الأعداد حتى الوصول إلى العدد 0، حينها سيتم إعادة قيمته. ولتجنب أن نرسل قيمة لهذا المعامل عند استدعاء الدالة في دالة ()main، قمنا بوضع قيمة افتراضية له.

الآن ستعمل الدالة مع أي رقم دون حدوث مشكلة أو استثناء:

ولكن نلاحظ، أنه تسببنا في مخالفة هدف من أهداف البرمجة الوظيفية، بجعل المتغير accumulator قابل لتغيير قيمته. ما عدا ذلك، نكون قد استخدمنا الطريقة التعاودية، دون التسبب في أخطاء، بمساعدة من مترجم كوتلن.

هذا الدرس هو جزء من سلسلة تعليم مبادئ البرمجة بلغة كوتلن. لمُتابعة الدروس منذ البداية ومُشاهدة فهرس المحتويات يمكنك الانتقال إلى الدرس الأول من هنا.