انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

الاستدعاء الذاتي Recursion :

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

n! = n * (n-1) * (n-2) * (n-3) ... * 1

for example 5! (factorial of 5) would be:

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

ملاحظة : يجب أن تمتلك دالة الاستدعاء الذاتي على خطوتين أساسيتين :

1-     وجود شرط توقف معرف بشكل صحيح مثل :

If  (x<=1)    return 1 

         بدون هذه الخطوة يستمر الاستدعاء إلى مالا نهاية .

2-     وجود خطوة الاستدعاء الذاتي التي يجب أن تعرف بشكل صحيح بحيث تؤدي إلى حالة توقف مثل :

  Return  x*factorial(x-1)

 لذلك البرنامج الفرعي الذي يعتمد أسلوب الاستدعاء الذاتي لإيجاد المفكوك هو :

int factorial(int x)  

     if  (x<=1)

       return 1;

    else

       return   x*factorial(x-1);

}

تمثيل عملية الاستدعاء الذاتي في الذاكرة :

كل خطوة من خطوات الاستدعاء الذاتي التي تم تأجيلها تخزن في جزء من الذاكرة يسمى المكدس Stack , مثلا لو أردنا حساب مفكوك العدد  5 سيكون هنالك أربعة خطوات مؤجلة في المكدس سوف تسترجع  ذاتياً من أعلى إلى أسفل عند الوصول إلى شرط التوقف  كالتالي :

1- Factorial(5)= 5*Factorial(4)

2- Factorial(4)=4* Factorial(3)

3- Factorial(3)=3* Factorial(2)

4- Factorial(2)=2* Factorial(1)

5- Factorial(1)=1       <-------   تحقق شرط التوقف

الخطوات الأربعة المؤجلة تخزن في المكدس كالتالي :

                         Stack

                                                     الاسترجاع من أعلى إلى أسفل

مثال : اكتب برنامج يحسب الدالة :

Y=2x+4x+6x+………….+nx

بحيث تقرأ المتغيرات في الدالة الرئيسية ويتم حساب قيمة الدالة في دالة فرعية تعتمد أسلوب الاستدعاء الذاتي ؟

#include<iostream.h>

int series(int x, int n)

{

  if (n<=2)

    return 2*x;

 else

    return  n*x+series(x , n-2);

}

void main( )

{

    int  n,x;

    cout<<”Enter n as even integer\n”;

    cin>>n;

     cout<<”enter x as integer\n”;

    cin>>x;

    cout<<”Y=”<<series(x,n);

}

   H.W: أكتب برنامج يحسب قيمة     بحيث تقرأ المتغيرات في الدالة الرئيسية وعملية الحساب تتم في دالة فرعية تعتمد أسلوب الاستدعاء الذاتي ؟