ما هي تقنية الاستدعاء الذاتي Recursion؟
تسمى العملية التي تستدعي فيها الدالة نفسها بشكل مباشر أو غير مباشر بتقنية الاستدعاء الذاتي وتسمى الدالة المقابلة باسم دالة الاستدعاء الذاتي. باستخدام خوارزمية الاستدعاء الذاتي، يمكن حل بعض المشكلات البرمجية بسهولة تامة، ومن الأمثلة على هذه مشكلات عمليات المسح في أبراج هانوي (TOH)، وعمليات المرور على هياكل البيانات الشجرة، انشاء خوارزمية البحث بالعمق أولاً (DFS)، وما إلى ذلك.
أنواع تقنية الاستدعاء الذاتي:
تتكون تقنية الاستدعاء الذاتي بشكل أساسي من نوعين اعتمادًا على ما إذا كانت الدالة تستدعي نفسها من داخل نفسها أو تستدعي أكثر من دالة بعضها البعض، النوع الأول يسمى تقنية الاستدعاء الذاتي المباشر والنوع الثاني يسمى بتقنية الاستدعاء الذاتي غير المباشرة، بالتالي فإن نوعي تقنية الاستدعاء الذاتي هما:
الاستدعاء الذاتي المباشرة:
يمكن تصنيفها إلى أربعة أنواع:
1. استدعاء الذاتي الذيلي Tail Recursion:
إذا كانت دالة الاستدعاء الذاتي تستدعي نفسها وكان ذلك الاستدعاء العبارة الأخيرة في الدالة، فإنها تُعرف باسم استدعاء الذاتي الذيل، بعد ذلك الاستدعاء لا تؤدي الدالة أي شيء، ويجب أن تقوم الدالة بمعالجة أو تنفيذ أي عملية في وقت الاستدعاء ولا تفعل شيئًا في وقت الإرجاع،
مثال:
#include <iostream>using namespace std;void fun(int n) { if (n > 0) { cout << n << " "; // Last statement in the function fun(n - 1);} } int main() { fun(3); return 0; }المخرجات ستكون: (3 2 1)، دعنا نفهم المثال عن طريق تتبع الدالة بالطريقة التي يتم بها إجراء الاستدعاءات وكيفية إنتاج النواتج:
2. الاستدعاء الذاتي الرأسي Head Recursion:
إذا كانت دالة الاستدعاء الذاتي تستدعي نفسها وكان ذلك الاستدعاء هو العبارة الأولى في الدالة، فإنها تُعرف باسم استدعاء الذاتي الرأس، إذ لا توجد عبارة أو عملية قبل الاستدعاء، ولا يتعين على الدالة معالجة أو تنفيذ أي عملية في وقت الاستدعاء ويتم تنفيذ جميع العمليات في وقت الارجاع.
مثال:
#include <iostream>using namespace std;void fun(int n){if (n > 0) {// First statement in the functionfun(n - 1);cout << " "<< n;}} int main() { fun(3); return 0; } المخرجات ستكون: (1 2 3)، دعنا نفهم المثال عن طريق تتبع الدالة بالطريقة التي يتم بها إجراء الاستدعاءات وكيفية إنتاج النواتج:
3. الاستدعاء الذاتي الشجري Tree Recursion:
لفهم الاستدعاء الذاتي الشجري، دعنا نفهم أولاً الاستدعاء الذاتي الخطي، إذا كانت الدالة الاستدعاء الذاتي تستدعي نفسها لمرة واحدة، فإنها تُعرف باسم الاستدعاء الذاتي الخطي، خلاف ذلك إذا كانت الدالة الاستدعاء الذاتي تستدعي نفسها لأكثر من مرة، فإنها تُعرف باسم الاستدعاء الذاتي الشجري،
مثال:
#include <stdio.h>void fun(int n) { if (n > 0) { printf("%d ", n); fun(n - 1); fun(n - 1); }}int main() { fun(3); return 0; } المخرجات ستكون (3 2 1 1 2 1 1)، وسيكون تعقيد الوقت هو “O(2^n)” في هذا المثال لنفهم المثال عن طريق تتبع الدالة بالطريقة التي يتم بها إجراء الاستدعاءات وكيفية إنتاج النواتج:
4. الاستدعاء الذاتي الخطي Linear Recursion:
دالة الاستدعاء الذاتي الخطية هي دالة تقوم فقط بإجراء استدعاء واحد لنفسها في كل مرة يتم فيها تشغيل الدالة (على عكس تلك التي قد تستدعي نفسها عدة مرات أثناء تنفيذها ).
fun(n) { // some code if(n>0) { fun(n-1); // Calling itself only once in the function } // some code }الاستدعاء الذاتي الغير مباشرة:
في هذا النوع من تقنية الاستدعاء الذاتي، قد يكون هناك أكثر من دالة واحدة وهم يتصلون ببعضهم البعض بطريقة دائرية.
#include <stdio.h> void funB(int n); void funA(int n) { if (n > 0) { printf("%d ", n); // Fun(A) is calling fun(B) funB(n - 1); } } void funB(int n) { if (n > 1) { printf("%d ", n); // Fun(B) is calling fun(A) funA(n / 2); } } int main() { funA(20); return 0; }ستكون المخرجات (20 19 9 8 4 3 1)، ولتتبع الدالة بالطريقة التي يتم بها إجراء الاستدعاءات كما يلي:
