الاستدعاء الذاتي (Recursion) في C: شرح وأمثلة على الدوال الاستدعائية

الاستدعاء الذاتي (Recursion) في C

الاستدعاء الذاتي (Recursion) هو العملية التي تقوم من خلالها الدالة باستدعاء نفسها. تسمح لغة C بكتابة مثل هذه الدوال التي تستدعي نفسها لحل المشكلات المعقدة عن طريق تقسيمها إلى مشكلات بسيطة. هذه الدوال تُعرف باسم الدوال الاستدعائية.

ما هي الدالة الاستدعائية في C؟

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

الصيغة العامة

هكذا يبدو شكل الدالة الاستدعائية بشكل عام:

void recursive_function(){
   recursion();   // الدالة تستدعي نفسها
}

int main(){
   recursive_function();
}

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

لماذا نستخدم الاستدعاء الذاتي في C؟

يُستخدم الاستدعاء الذاتي لأداء مهام معقدة مثل استعراض هياكل الأشجار والمخططات البيانية. من أشهر الحلول البرمجية الاستدعائية هي حساب العامل المضروب (Factorial)، البحث الثنائي، استعراض الأشجار، مسألة أبراج هانوي، وغيرها.

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

العامل المضروب باستخدام الاستدعاء الذاتي

الدوال الاستدعائية مفيدة جدًا لحل العديد من المسائل الرياضية مثل حساب العامل المضروب (Factorial)، توليد سلسلة فيبوناتشي، وغيرها.

أشهر مثال على الاستدعاء الذاتي هو حساب العامل المضروب. رياضيًا، العامل المضروب يُعرَّف كالتالي:

n! = n X (n-1)!

نرى هنا أننا نستخدم العامل المضروب نفسه لتعريف العامل المضروب، ولذلك يُعتبر هذا حالة مثالية لكتابة دالة استدعائية.

دعونا نوسع التعريف لحساب العامل المضروب لـ 5:

5! = 5 X 4!
   5 X 4 X 3!
   5 X 4 X 3 X 2!
   5 X 4 X 3 X 2 X 1!
   5 X 4 X 3 X 2 X 1
   = 120

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

مثال: دالة غير استدعائية لحساب العامل المضروب

البرنامج التالي يُظهر كيف يمكننا استخدام دالة غير استدعائية لحساب العامل المضروب:

#include <stdio.h>

// الإعلان عن الدالة
int factorial(int);

int main(){
   int a = 5;
   int f = factorial(a);
   
   printf("a: %d \n", a);
   printf("Factorial of a: %d", f);
}

int factorial(int x){
   int i;
   int f = 1;
   
   for (i = 5; i >= 1; i--){
      f *= i;
   }
   return f;
}

الإخراج

a: 5 
Factorial of a: 120

مثال: دالة استدعائية لحساب العامل المضروب

دعونا نكتب الآن دالة استدعائية لحساب العامل المضروب لعدد معين:

#include <stdio.h>

// الإعلان عن الدالة
int factorial(int i){

   if(i <= 1){
      return 1;
   }
   return i * factorial(i - 1);
}

int main(){
   int a = 5;
   int f = factorial(a);
   
   printf("a: %d \n", a);
   printf("Factorial of a: %d", f);
   return 0;
}

الإخراج

a: 5 
Factorial of a: 120

عندما تقوم دالة main() باستدعاء دالة factorial() وتمرير المتغير “a”، يتم تخزين قيمته في المتغير “i”. تقوم دالة factorial() باستدعاء نفسها بشكل متكرر.

في كل استدعاء، يتم ضرب قيمة “i” بقيمتها السابقة بعد تقليلها بمقدار 1، حتى تصل إلى 1. عندما تصل إلى 1، يتم إرجاع حاصل ضرب جميع القيم بين القيمة الأولية للوسيطة و1 إلى الدالة main().

البحث الثنائي باستخدام الاستدعاء الذاتي

البحث الثنائي هو خوارزمية بحث تعمل على قائمة مرتبة. في كل خطوة من الخوارزمية، يتم تقسيم القائمة إلى قسمين ويُبحث عن العنصر في نصف واحد منها.

#include <stdio.h>

int bSearch(int array[], int start, int end, int element){
   
   if (end >= start){
      
      int mid = start + (end - start ) / 2;
      
      if (array[mid] == element)
         return mid;
      
      if (array[mid] > element)
         return bSearch(array, start, mid-1, element);
         
      return bSearch(array, mid+1, end, element);
   }
   return -1;
}

int main(void){
   int array[] = {5, 12, 23, 45, 49, 67, 71, 77, 82};
   int n = 9;
   int element = 67;
   int index = bSearch(array, 0, n-1, element);
   
   if(index == -1 ){
      printf("Element not found in the array ");
   }
   else{
      printf("Element found at index: %d", index);
   }
   return 0;
}

الإخراج

Element found at index: 5

الخاتمة

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