تقنية الاستدعاء الذاتي Recursion

مفهوم الاستدعاء الذاتي Recursion:

يُعرف الاستدعاء الذاتي (Recursion) على أنه تقنية لبرمجة الكمبيوتر تتضمن استخدام إجراء (procedure) أو دالة (function) تستدعي نفسها بطريقة متكررة دون الحاجة لاستخدام الحلقات التكرارية مثل (while و for)، شرط أن يكون هناك حالة إنهاء (Termination Case)، عندها تتم معالجة التكرارات المتتالية وتتم عملية المعالجة من آخر استدعاء إلى أول.

في بعض الأحيان تكون المشكلة البرمجية صعبة أو معقدة للغاية بحيث لا يمكن حلها لأنها كبيرة جدًا، لكن إذا كان من الممكن تقسيم المشكلة البرمجية إلى إصدارات أصغر من المشكلة البرمجية ذاتها، فقد نتمكن من إيجاد طريقة لحل واحدة من هذه الإصدارات الأصغر ومن ثم نكون قادرين على بناء حل للمشكلة البرمجية بأكملها، هذه هي الفكرة وراء الاستدعاء الذاتي (Recursion). تُقسِّم خوارزميات الاستدعاء الذاتي (Recursion algorithms) المشكلة إلى أجزاء أصغر والتي إما أن تعرف الإجابة عليها بالفعل، أو يمكنك حلها عن طريق تطبيق نفس الخوارزمية على كل قطعة، ثم دمج نتائج كل قطعة.

وبشكل عام، تعتبر المشكلات البرمجية التي تعّرف نفسها من نفسها مرشحةً جيدةً لتقنية الاستدعاء الذاتي، على سبيل المثال دالة المضروب والتي يُشار إليها غالبًا ب (!n)، وهي عملية ضرب رقم في جميع الأعداد الصحيحة الموجبة الأصغر منه. على سبيل المثال، (5! = 5 * 4 *3 * 2 * 1). لاحظ أنه يمكن كتابة (!5) على أنها (!5 = 5 * !4) و (!4= 4 * !3). أذن (!n*(n-1)! = n)، حيث (n>0)، أي أن (n) عدد أكبر من صفر.

بعض المفاهيم الأساسية في الاستدعاء الذاتي Recursion:

الحالة الأساسية Base Case: أو حالة توقف الاستدعاءات المتكررة، وغالبا ما تكون الحالة التي نعرف الإجابة عليها، والحالة الأساسية هي ما يمنع استمرار الاستدعاء الذاتي (recursion) بشكل لانهائي. يجب أن تحتوي كل دالة الـ (recursive) على حالة أساسية واحدة على الأقل. وفي بعض الأحيان يكون هناك أكثر من حالة أساسية وإذا لم يُؤخذ بعين الاعتبار جميع الحالات الأساسية فإنه لن تعمل الدالة بشكل الصحيح معظم الوقت، وستتسبب على الأرجح في تعطل برنامجك في العديد من المواقف، وبالتأكيد ليس هذا المطلوب.

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

الحالة العامة The General Case: هي الحالة الأكثر تعقيدًا للمشكلة وليس من السهل الإجابة عليها مباشرةً، والتي تحدث في معظم الأوقات، أو الحالة التي تتكرر فيها الاستدعاء الذاتي ل (method). وفي مثال المضروب، تحدث الحالة العامة عندما يكون (n) أكبر من (1).

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

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

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

تكون الدالة الأخيرة المطلوب استدعاؤها (الأحدث) في الجزء العلوي من المكدس بينما توجد الدالة الأولى المطلوب استدعاؤها (والتي يجب أن تكون الدالة الرئيسية “main”) في أسفل المكدس. عندما يتم استدعاء دالة جديدة (بمعنى أن الدالة الموجودة في الجزء العلوي من المكدس تستدعي دالة أخرى)، حيث يتم دفع إطار الدالة الجديدة إلى المكدس ويصبح هو الإطار النشط. عندما تنتهي إحدى الدوال، ويتم إتلاف إطارها وإزالتها من المكدس، ويعيد التحكم إلى الإطار الموجود أسفله مباشرةً على المكدس (الإطار العلوي الجديد).

كود المضروب باستخدام تقنية الاستدعاء الذاتي:

مزايا وعيوب استخدام تقنية الاستدعاء الذاتي:

المزايا:

• بالنسبة لدالة الاستدعاء الذاتي، ما عليك سوى تحديد الحالة الأساسية والحالة العامة، وبالتالي فإن كود الاستدعاء الذاتي سيكون أبسط وأقصر من كود التكراري (iterative).

• بعض الخوارزميات تستخدم تقنية الاستدعاء الذاتي بطبيعتها، مثل الرسم البياني واجتياز الشجرة.

العيوب :

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

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