السنه الى فاتت واحنا فى سنه اولى كان فى مجموعه من ال sessions دكتور عمر عثمان كان بيديهلنا بهدف تطوير مستوانا وتدريبنا اكتر ...... فى session منهم كان فى كلمه دكتور عمر كان عامل جنبها emotion لسه فاكره لحد دلوقتى وهى كلمه Recursion ...... ماخضناش اوى فيها السنه الى فاتت .... و السنادى الحمد لله توسعنا فيها شويه لما خدنا ال trees فى ال Data Structure شفنا اد ايه ال Recursion مهمه فى انك بدل ماتكتب كود مكون من N linesممكن من خلال ال Recursion تكتب كود صغير جدا
فانا ان شاء الله هاتكلم عن الموضوع دا بس عشان هو طويل جدا فقررت انه يتجزء على كذا مرة .
يعنى ايه Recursion ؟؟؟؟؟!!!!
كلمة Recursion بالعربى معناها معاودة
وفى البرمجة Recursion عبارة عن تكرارfunction عن طريق ان ال function دى بتنادى نفسها اكتر من مرة لحد ماحاجه معينه تتحقق فتوقفها
بتقول بتنادى نفسها اكتر من مرة !!!!! طب امتى هاتقف ؟؟
ال Recursion هيا function زى اىfunction بتيجى عند وقت معين وتخلص وتنتهى .
طب ليه بنستخدم ال Recursion؟؟؟؟
ليها فوائد كتير جدا هنبقى نتطرقلها فى مقالات تانية ... لكن الحاجة اللى ممكن نلمسها دلوقتى تقليل عدد اسطر الكود
طب سؤال!!!!!هل الكود الى بنعمله بال Recursion ماينفعش اعمله من غير Recursion ?? لا طبعا ينفع احنا اتفقنا ان ال Recursion عبارة عن function زيها زى اى function يعنى نقدر نعمل الكود بال Recursion ومن غيرها برضه ينفع
اى recursive function بتتكون من جزئين مهمين اوى
اول جزء حاجة اسمها anchor case او termination condition طبعا مفهومه من اسمها ان ده الحاله الى هتخلى ال function بتاعتنا تخلص وتنتهى يعنى عند condition معين ال function بتعمل terminate و الconditon ده احنا الى بنحطه على اساس الكود بيعمل ايه.
تانى جزء فى ال recursive functin حاجة اسمها inductive case
ودى معنااها بكل البساطه انها هى الجزء الى بيحصل قبل مالفانكشن بتاعتنا توصل للanchor case .
طب ماتيجو ناخد مثال نوضح بيه الكلام الى عمالين نقوله ده
عندنا مثال مشهور جدا وهو حساب number factorial اللى بيرمزله بالعلامة "!"
للى مايعرفش ال factorial ...
ال factorial لرقم يعنى عدد الطرق اللى نقدر نرتب بيها عدد من الاشياء"Objects" فى خط مستقيم "line" ... وطبعا مفيش عدد سالب من ال "Objects" يعنى مينفعش اقول عندى -5 حاجات مثلا .... وبالتالى factorial رقم سالب غير معرف "undefined" مش 1
طب نيجى للحالات الخاصة :
factorial ال 1 بيساوى 1 ... لأن احنا عندنا طريقة واحدة نرتب بيها حاجة واحدة
factorial ال 0 بيساوى 1 برضه .... لان احنا لو معندناش حاجة علشان نرتبها .... يبقى احنا مقدمناش غير طريقة واحدة للترتيب وهى اننا منعملش حاجة :D
وممكن نحسب ال factorial بحاصل ضرب كل الارقام من 1 لحد الرقم نفسه يعنى مثلا لو عايزين نجيب مضروب 5 يبقى يساوى
5*4*3*2*1
يعنى نلاحظ من كدة ايه ؟؟؟؟؟نلاحظ ان مضروب الرقم لو كان مثلا n-----> n*(n-1)*(n-2)*(n-3).......*3*2*1
طب خلينا نتفق ان
factorial n <= 1 is 1
طيب دلوقتى احنا قلنا ان مضروب الرقم هيساوى حاصل ضرب الارقام من 1 لغايه الرقم نفسه يعنى اذا...
1! = 1
2! = 1*2 = 2
3! = 1*2*3=6
4! = 1*2*3*4=24
5! = 1*2*3*4*5=120
..............................................and so on
طب دلوقتى عايزين نركز شويه عشان انتو الى هاتكتبو القانون دلوقتى مش انا
دلوقتى احنا قلنا ان
5! = 5*4*3*2*1
طب لو ركزنا شويه كدة وجينا بعد ال 5 لاقينا 4*3*2*1 طب دا معناها ايه ؟؟؟؟؟
مش دى معناها 4! ؟؟؟؟؟ اه صح دى معناها 4! طب معلش هارخم شويه واقولكم ركزو اكترلو جينا بعد ال 4 هانلاقى ايه ؟؟؟
هانلاقى ان 3*2*1 دى سهله بقى انتو عرفتوها دى مضروب3 وهكذا طب نفهم من كدةا يه؟؟؟؟؟ نفهم ان مضروب الرقم = الرقم نفسه مضروب فى مضروب الى قبليه يعنى 5!=5*4! وهكذا .....
طب نيجى بقى نكتب القاعدة بتاعتنا عشان نرتب افكارنا..........
fact(N)=1 IF (N=1)
Fact(N)=N*Fact(N-1)=N*(N-1)*Fact(n-2).....*3*2*1 IF (N>1)
طب دلوقتى لما جينا وقلنا لو ال الرقم يساوى 1 يبقى ال factorial = 1
لكن لما لاقينا ان الرقم الى عندنا اكبر من 1 مش هانعرف ال function هترجع ايه
هى هترجع حاصل ضرب الرقم فى مضروب الى قبليه طب هاييجى الرقم الجديد هايساوى الرقم (القديم - 1) زى ماتفقنا طب لو الرقم الجديد بتاعنا اكبر من 1 هايرجع برضه الرقم مضروب فى factorialالى قبليه وهكذا لغايه ميلاقى ان الرقم اصبح 1 وبعدين يرجع حاصل ضربهم كلهم
قى المرة الجاية ان شاء الله هانعرف ازاى الحكايه دى بتم يعنى التخزين بتاع القيم وحاصل الضرب بيتخزن فين وكدة ........ لكن الى عايزين نعرفه دلوقتى ..... فوق فى السطرين الى فاتو انا قلت حاجة مهمة اول مايلاقى الرقم بقى 1 البرنامج بيخرج
دى معناها ايه ؟؟؟؟
دى الحاجة الى كنا اتكلمنا عليها فى الاول الى اسمها anchor case طيب فاضل حاجة تانيه الى انت بتقول عليها بتتكون منها ال recursion قصدكم ال inductive Or base case
طب كويس مركزين اهو طيب احنا اتفقنا ان inductive Or base caseهيا ايه ؟؟؟
الجزء الى بيحصل قبل مالفانكشن بتاعتنا توصل للanchor case طيب ايه الى بيحصل قبل مالفانكشن بتاعتنا تخلص ؟؟؟
صح هو الجزء بتاع ان احنا نحسب
Fact(N)=N*Fact(N-1)=N*(N-1)*Fact(n-2).....*3*2*1 IF (N>1)
طيب يبقى كدة احنا عرفنا يعنى ايه recursionوايه مكوناتها وفهمناهم خدنا مثال عليها نيجى بقى للcode
دا كود بيعمل فنكشن بتحسب factorial بدون recursion
int Factorial(int Number)
{
int Sum = 1;
for (int i = Number ; i > 1 ; i --)
Sum *= i;
return Sum;
}
وده كود بال recursion
int Factorial(int Number)
{
if(Number <= 1) // anchor case
return 1;
else
return ( Number * Factorial (Number - 1); // inductive OR recursive case
}
احنا ممكن لحد دلوقتى منحسش بقيمة ال Recursion وقد ايه هى نعمة من عند ربنا لاننا لسه فى البداية ولسه مش حسينا فوائدها
ملحوظة : هناااا نسخة PDF للمقال