محتويات
ماهي تقنية الاستدعاء الذاتي Recursion
إن الوظائف التكرارية أو الاستدعاء الذاتي هي من أنواع الخوارزميات البرمجية حيث أنها في مصطلحات البرمجة تعرف الوظيفة العودية بأنها هي إجراء يستدعي نفسه بشكل مباشر أو بشكل غير مباشر، ويتم باستخدام الخوارزمية العودية أو الاستدعاء الذاتي، حيث أنه من الممكن أن يتم حل المشكلات بشكل سهل عن طريق الخوارزمية العودية أو الوظيفة التكرارية، وإن المعنى الحرفي لها هو الاستدعاء الذاتي فهي methods نقوم بنداء نفسها بنفسها، وإن لهذه ال method هيكلية خاصة بها وأساسيات.[2]
أمثلة على Recursion
إن للاستدعاء التكراري طرق مختلفة لكتابتها فهناك الطريقة المباشرة والطريقة الغير مباشرة، فسنتطرق إلى أبراج كود هانوي وهو من الأمثلة على الاتصال المباشر وسنتطرق إلى تنفيذه بعدة لغات:
أمثلة على الطريقة المباشرة بلغة++C
#include <bits/stdc++.h>using namespace std;// Assuming n-th disk is bottom disk (count down)void tower(int n, char sourcePole,char destinationPole, char auxiliaryPole){// Base case (termination condition)if(0 == n)return;// Move first n-1 disks from source pole// to auxiliary pole using destination as// temporary poletower(n - 1, sourcePole, auxiliaryPole,destinationPole);// Move the remaining disk from source// pole to destination polecout << "Move the disk "<< n << " from " <<sourcePole <<" to "<< destinationPole << endl;// Move the n-1 disks from auxiliary (now source)// pole to destination pole using source pole as// temporary (auxiliary) poletower(n - 1, auxiliaryPole, destinationPole,sourcePole);}// Driver codeint main(){tower(3, 'S', 'D', 'A');return 0;}// This code is contributed by SHUBHAMSINGH10أمثلة على الطريقة المباشرة بلغة الجافا
// Assuming n-th disk is// bottom disk (count down)class GFG { static void tower(int n, char sourcePole, char destinationPole, char auxiliaryPole){ // Base case (termination condition) if (0 == n) return; // Move first n-1 disks from source pole // to auxiliary pole using destination as // temporary pole tower(n - 1, sourcePole, auxiliaryPole, destinationPole); // Move the remaining disk from source // pole to destination pole System.out.printf("Move the disk %d from %c to %cn", n, sourcePole, destinationPole); // Move the n-1 disks from auxiliary (now source) // pole to destination pole using source pole as // temporary (auxiliary) pole tower(n - 1, auxiliaryPole, destinationPole, sourcePole);}public static void main(String[] args){ tower(3, 'S', 'D', 'A');}}// This code is contributed by Smitha Dinesh Semwal.# Assuming n-th disk is# bottom disk (count down)def tower(n, sourcePole, destinationPole, auxiliaryPole): # Base case (termination condition) if(0 == n): return # Move first n-1 disks # from source pole # to auxiliary pole # using destination as # temporary pole tower(n-1, sourcePole, auxiliaryPole, destinationPole) # Move the remaining # disk from source # pole to destination pole print("Move the disk",sourcePole,"from",sourcePole,"to",destinationPole) # Move the n-1 disks from # auxiliary (now source) # pole to destination pole # using source pole as # temporary (auxiliary) pole tower(n-1, auxiliaryPole, destinationPole,sourcePole)# Driver codeالاستدعاء الذاتي بلغة c
إن العملية التي تستدعي فيها الوظيفة نفسها تعرف باسم الوظيفة العودية وتسمى بالوظيفة المقابلة، ففي لغة ++c نفهم العودية أكثر عن طريق دالة عاملي والتي تتجلى في:[1]
f (n) = n * f (n-1) ، الشرط الأساسي: إذا كان n <= 1 ثم f (n) = 1.
فالغرض من العودية هو تقسيم المشكلة إلى مشاكل أصغر حتى تصل إلى الحالة الأساسية، ويتم عن طريق استدعاء دالة عاملية f(n).
أنواع تقنية الاستدعاء الذاتي
إن الاستدعاء الذاتي يتكون من نوعين ويعتمد إذا كانت الوظيفة تستدعي نفسها من داخل نفسها أو تعمل على استداعاء أكثر من وظيفة، وإن نوعي تقنية الاستدعاء الذاتي هما:
-الاستدعاء الذاتي المباشر
وتصنف إلى أربعة أنواع وتتجلى في:
- استدعاء الذاتي الذيلي Tail Recursion وفيها يتم استداع الدالة لنفسها، ويكون هذا الاستدعاء هو العبارة الأخيرة في الدالة، وبعد أن يتم هذا الاستدعاء لا تؤدي الدالة إلى شيء، وإن هذه الدالة يجب أن تقوم بمعالجة أو تقوم بتنفيذ أي عملية في وقت الاستدعاء.
- الاستدعاء الذاتي الرأسي Head Recursion فعندما تستدعي الدالة نفسها حيث أن هذا الاستدعاء يكون العبارة الأولى في الدالة فإن هذا الاستدعاء يعرف باسم الاستدعاء الذاتي الرأسي، وفيه لا تتواجد أي عبارة أو عملية قبل أن يحصل الاستدعاء، ولا تحتاج الدالة إلى أن تقوم بمعالجة أو تنفيذ أي عملية عند الوقت الذي يتم فيه الاستدعاء، وإن جميع العمليات يتم تنفيذها وقت الارجاع.
- الاستدعاء الذاتي الشجري Tree Recursion وفي هذا الاستدعاء يتم عن طريق استدعاء الدالة لنفسها لأكثر من مرة، فهي على عكس الاستدعاء الذاتي الخطي الذي يتم فيه استدعاء الدالة لنفسها مرة واحدة فقط.
- الاستدعاء الذاتي الخطي Linear Recursion وهي الدالة التي تقوم من خلال إجراء استدعاء واحد فقط لنفسها، ويتم هذا الاستدعاء في كل مرة يتم فيها تشغيل الدالة.
-الاستدعاء الذاتي الغير مباشر
ويتم في الاستدعاء الذاتي الغير مباشر اتصال أكثر من دالة ببعضهم البعض بشكل دائري، فهو استدعاء إحدى الوظائف نفسها بالشكل الغير مباشر من وظيفة أخرى.[3]
مزايا وخصائص الاستدعاء الذاتي
إن خصائص الاستدعاء الذاتي تتجلى في:
- أن الوظيفة التكرارية أو الاستدعاء الذاتي هي وظيفة تقوم على استدعاء نفسها.
- إن سرعة الاستدعاء الذاتي تكون أبطأ بسبب الأعباء المكدسة.
- إن وظيفة الاستدعاء الذاتي يجب أن تحتوي على شروط إنهاء أو حالة أساسية بالإضافة إلى احتوائها لتعبيرات متكررة.
بينما مزايا الاستدعاء الذاتي تتجلى في:
- إنه يجعل البرنامج نظيفاً.
- يعمل على تقصير التعليمات البرمجية المعقدة والمتداخلة.
بينما مساوئ الاستدعاء الذاتي تتجلى في :
- من الصعب أن يتم تصحيح الأخطاء.
- من الصعب أن يتم فهم المنطق.[4]
