أحتاج لمن يشرح لي Recursion

بسم الله الرحمن الرحيم

الرابط الموجود مفيد وهذه إضافة مني سأل الله أن ينفع بها وأن تسهل على الأعضاء بشكل عام فهم أسلوب المعاودة.

* الشرح :

تعريف دالة المعاودة ( Recursion Function ):

هي عبارة عن دالة مثل أي دالة ( برنامج فرعي يقوم بعملية ما على مدخلات ويعود بناتج معين ) ولكنها تتميز عن بقية الدوال بأنها تستدعي نفسها عدد من المرات حتى يتحقق شرط ما ، ثم تتوقف وتعود بالقيمة .

* ملاحظة :

لابد من وجود شرط( قيمة معينة ) عند تحققه تعود الدالة بالقيمة ، حتى لا تكون الدالة تستدعي نفسها عدد لا نهائي من المرات.

* مثال يوضح المقصود من هذا النوع من الدوال:

دالة المضروب ( أو المعاملي ) هي من أشهر الأمثلة على هذا النوع .

نحن نعرف المضروب بأنه التالي:

N! = N ( n-1)! ( n-2)! …

مثلاً:

مضروب الخمسة هو :

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

*** وعندما نريد كتابة أي نوع من هذه الدوال لا بد أولا أن نفكر متى ستنتهي الدالة من استدعاء نفسها والعودة بالقيمة ؟

*** متى ما أجبنا على هذا السؤال سهل علينا كتابة البرنامج بكل سهولة.

نعود على مثالنا فنجد أن مضروب الصفر هو دائما واحد أي أن ( 0! = 1 )

5! = 5 * 4!

4! = 4 * 3!

3! = 3 * 2!

2! = 2 * 1!

1! = 1 * 0!

0! = 1

أي عندما نكتب البرنامج سنجعل الدالة تكررنفسها إلى أن تصل إلى مضروب الصفر فتعيد لمكان استدعاء الدالة القيمة واحد ثم تتم عملية ضرب القيم ( 5*4*3*2*1 ) ثم العودة بالناتج وهو ( 120 ) وهو ناتج مضروب الخمسة وهذا ما سوف يحصل بالضبط في البرنامج التالي:

/******برنامج المضروب*******/

#include <iostream.h>



int Fact( int N );



int main()
{
	int N;

	cout << "Enter Number : ";
	cin  >> N;

	cout << "\n Fact = " << Fact(N) << "\n\n";

	return  0;
}

int Fact( int N )
{

	if( N == 0 )  
  return 1;
	else
  return N * Fact( N-1 );

}

هذا البرنامج البسيط يقوم بحل المضروب وإليك الشرح:

في بداية البرنامج عرفنا دالة اسمها Fact تعود بعدد صحيح ويمرر لها عدد صحيح.

في الدالة main يطالب المستخدم بإدخال عدد ثم يتم استدعاء الدالة Fact ممرر لها العدد N وتعود بقيمة المضروب ليتم طباعته.

جسم الدالة Fact يحتوي على عبارة if_else الشرطية حيث يقول ( إذا كان العدد الممرر للدالة يساوي الصفر فعد بالقيمة واحد وهذا هو القيمة التي تحدد نهاية استدعاء الدالة كما قلت ( 0! = 1 ) . وإذا كان غير ذلك فقم بضرب العدد الممر للدالة ( N ) بالعدد الناتج من استدعاء الدالة مرة أخرى بالعبارة ( Fact(N-1) ) حيث ستعود الدالة هذه المرة بالقيمة ( 4 * Fact(4-1) ) أي سيتم ضرب ( 5 * 4 * Fact(3) ) ثم يتم استدعاء الدالة مرة أخرى – لأن الشرط مازال غير محقق – فتعود الدالة هذه المرة بالقيمة ( 3 * Fact(3-1) ) أي سيتم ضرب القيمة ( 5 * 4 * 3 * Fact(2) ) ثم يتم استدعاء الدالة مرة أخرى – لأن الشرط مازال غير محقق – فتعود الدالة هذه المرة بالقيمة ( 2 * Fact(2-1) ) أي سيتم ضرب القيمة ( 5 * 4 * 3 * 2 * Fact(1) ) ثم يتم استدعاء الدالة مرة أخرى – لأن الشرط مازال غير محقق – فتعود الدالة هذه المرة بالقيمة واحد ( 1 ) لماذا ؟

لأن Fact(1-1) يؤدي إلى Fact(0) وهنا يكون الشرط متحقق فتعود الدالة بالقيمة واحد ( 1 ) إلى السطر الذي بعد else لأنه تم استدعاء الدالة هناك فتعود بالقيمة ( 1) فيتم عملية الضرب ( 5 * 4 * 3 * 2 * 1 ) ويكون الناتج ( 120 ) وتعود بها الدالة إلى السطر الذي تم استدعائها فيه عند الدالة main لطباعة الناتج.

* مثال أخروهو دالة القوة power حيث تأخذ هذه الدالة وسيطين الأول عدد وليكن ( x ) والثاني أس للعدد وليكن ( n ) ثم تقوم بعملية الرفع لأس والعودة بالناتج كالتالي x ^ n .

هنا لابد أن نبحث عن متى ستوقف الدالة أو بمعنى أصح ما هي القيم التي تنهي عملية الاستدعاء المتكرر ( أسلوب المعاودة ) .

فنجد التالي:

1 – إذا كانت n = 0 فأن x = 1 .

2 – إذا كانت n < 0 فإن 1 / x^n .

3 – إذا كانت n > 0 فإن x * x^n-1 .

ولذلك عندما نكتب الدالة بأسلوب المعاودة ننظر إلى الحالات في الحالة الأولى يكفي أن نكتب التالي

if( n == 0 )

return 1;

أما في الحالة الثانية فيكفي أن نكتب التالي:

else if( n < 0 )

return 1 / Power( X,abs(n) );

و استخدمنا هنا أسلوب المعاودة حيث يتم استدعاء الدالة مرة أخرى متى ما كان العدد المرسل للدالة سالب ( مع ملاحظة أنه في المقام ولذلك نأخذ له القيمة المطلقة لكي يكون عدد موجب – كما في الرياضيات - ).

أما في الحالة الثالثة فيكفي أن تكتب التالي:

else

return X * Power( X,n-1 );

هنا نقوم بضرب العدد المرسل لدالة بالقيمة المعادة من الدالة بعد إنقاص الأس بمقدارواحد وهكذا حتى يصل إلى شرط ينهي الدالة المستدعاة وذلك عنما يتحقق الشرط الأول فتعود بالقيمة واحد التي يتم ضربها بالعدد الممرر للدالة والعودة بالناتج إلى الدالة الرئسية ( main ) وطباعة الناتج.

البرنامج

#include <iostream.h>
#include <math.h>

/************************************/
/*** compute power(X,n) , X^n *******/
/************************************/


double Power( double X, int n );


int main()
{
	double x;
	int n;

	cout << "Enter X = ";
	cin  >> x;
	cout << "Enter n = ";
	cin  >> n;

	cout << "\n\t" << x << "^" << n << " = " << Power( x,n ) << "\n\n";

	return 0;
}


double Power( double X, int n )
{
	if( n == 0 )
  return 1;
	else if( n < 0 )
  return 1 / Power( X,abs(n) );
	else
  return X * Power( X,n-1 );
}

معليش كتبت الأمثلة بلغة السي بلص بلص ولكن لاتخافي بدل كل cout ضعب printf وبدل كل cin ضعي scanf .

وبالتوفيق.

اخي السهم ما شاء الله عليك

بطل وبارع

شكرا أخي عبد الهادي على التشجيع .

وأن شاء الله سأقدم في رمضان أو منتصف شهر رمضان شرح وافي عن الدوال في لغة ++c اذا انتهيت من امتحاناتي على خير.

أرجوا ان BBIS يستفيد من الشرح والمعلومات الي فيها والا انت يأخي عبد الهادي غني عن التعريف ماشاء الله عليك.

بالتوفيق للجميع.