مفهوم الـ Recursive Function
Recursion: تعني العودة إلى نفس المكان, أي تكرار نفس الشيئ.
Recursive Function: تعني دالة تفعل return لنفسها. أي تعيد إستدعاء نفسها بنفسها.
طريقة تعريف Recursive Function
عليك إعتماد الخطوات التالية عند تعريف أي دالة تستدعي نفسها:
وضع نوع الدالة
intأو أي نوع لا يقبل الفاصلة مثل النوعlong.وضع باراميتر نوعه
int, لأنه سيكون بمثابة عداد لتكرار عملية استدعاء الدالة.وضع شرط يحدد كم مرة ستقوم الدالة باستدعاء نفسها, أي كم مرة ستفعل
returnلنفسها.بما أن الدالة نوعها في الأساس
int, علينا أن نجعلها ترجع أي قيمة نوعهاintعندما تنتهي من تكرار نفسها إلى الدالة الأساسيةmain().
أي يجب أن نفعلreturnلأي قيمة نوعهاint( مثل 0 ) حتى لا يظهر أخطاء في الكود.يجب على الأقل أن تحتوي على 2
return.
إذا جعلت الدالة تستدعي نفسها كثيراً قد يؤدي ذلك إلى مشكلة في ذاكرة الجهاز, لأن الدالة كلما استدعت نفسها ستحتل مساحة معينة في ذاكرة الجهاز, وبالتالي إذا استدعت نفسها كثيراً (ألف مرة على سبيل المثال), قد تجعل ذاكرة جهازك تمتلئ و تجعل نظامك بطيئاً جداً حتى يتوقف كلياً عن العمل.
هناك الكثير من المخترقين الذين سرقوا ملايين الدوالارات من خلال هجماتهم الإلكترونية التي كانت تعتمد على إبطاء عمل سيرفرات البنوك.
الأخطاء المنطقية التي قد تواجه المبرمج عند تعريف Recursive Function
الآن سنكتب دالة بسيطة تستدعي نفسها لإعطاءك فكرة عامة حول شكل الـ Recursive Function و جعلك تعرف طبيعة المشكلة التي قد تحدث في حال لم تجعل الدالة تتوقف عن استدعاء نفسها و بالتالي معرفة أهمية وضع شرط عند كتابة Recursive Function.
إنتبه: إذا قمت بتجربة هذا الكود سيظهر لك خطأ أثناء التشغيل لأن الدالة هنا ستظل تستدعي نفسها دون أن تتوقف.
و كان يجب أن نجعل الدالة ترجع قيمة نوعها int إلى مكان الإستدعاء عندما تنتهي من التنفيذ لأن نوعها int و لكننا لم نرجع أي قيمة.
public class Recursion {
/* ------------------------------- هنا قمنا بتعريف الدالة ------------------------------ */
public static int RecursiveFunction ()
{
return RecursiveFunction();
}
/* --------------------------- من هنا يبدأ البرنامج بالتنفيذ --------------------------- */
public static void main (String[] args)
{
RecursiveFunction();
}
}
عند تشغيل البرنامج, سيتم تنفيذ الأوامر الموجودة في الدالة
main()في البداية, و بالتالي سيتم إستدعاء الدالةRecursiveFunction().عند إستدعاء الدالة
RecursiveFunction()ستظل تفعلreturnإلى نفسها بدون توقف, أي أنها في كل مرة تتنفذ سترجع إلى نفسها و تتنفذ من جديد.في الواقع, هنا كأننا قلنا لها أن ترجع و تنفذ نفسها كلما نفذت نفسها!
إذاً ستبقى الدالة
RecursiveFunction()ترجع إلى نفسها و تنفذ نفسها بدل أن ترجع إلى الدالةmain()إلى اللانهاية كما في الصورة في التالية.
الخطأ الأول: لم نضع شرط في الدالة
RecursiveFunction()لكي نجعلها تتوقف بعد استدعائها لنفسها عدة مرات.الخطأ الثاني: الدالة
RecursiveFunction()لم ترجع قيمة إلى الدالةmain()حيث تم إستدعاءها.
تمارين شاملة حول التعامل مع الباراميترات
تعريف دوال تستدعي نفسها في الخوارزميات - التمرين الأول
أكتب دالة تستدعي نفسها, إسمها CountFromTo, تعطيها أي عددين صحيحين فتقوم بطباعة جميع الأعداد الصحيحة الموجودة إبتداءاً من العدد الأول وصولاً إلى العدد الثاني.
فعلياً, سنجعل هذين العددين يحددان كم مرة ستقوم الدالة باستدعاء نفسها.
في البرنامج, قم باستدعاء الدالة CountFromTo لتجربتها.
إذا قمنا باستدعاء الدالة CountFromTo() و أعطيناها القيم 1 و 3, ستطبع لنا جميع الأعداد من 1 إلى 3 كالتالي.
public class Recursion {
/* ------------------------------- هنا قمنا بتعريف الدالة ------------------------------ */
public static int CountFromTo ( int start, int end ) {
if ( start <= end )
{
System.out.print("counter = " +start+ "\n");
return CountFromTo( start + 1, end );
}
return 0;
}
/* --------------------------- من هنا يبدأ البرنامج بالتنفيذ --------------------------- */
public static void main (String[] args) {
CountFromTo(1, 3);
}
}
public static int CountFromTo ( int start, int end ) {
if ( start <= end )
{
System.out.print("counter = " +start+ "\n");
return CountFromTo( start + 1, end );
}
return 0;
}
هنا أنشأنا الدالة CountFromTo() و حددنا أن نوعها int و وضعنا لها باراميترين start و end, هذان المتغيران يحددان كم مرة ستقوم الدالة باستدعاء نفسها.
    المتغير start يحدد من أي عدد ستبدأ عملية إستدعاء الدالة لنفسها, فعلياً سنستخدمه كعداد أيضاً حيث أننا سنضيف عليه 1 كلما استدعت الدالة CountFromTo() نفسها.
    المتغير end يحدد عند أي عدد ستتوقف الدالة عن إستدعاء نفسها من جديد.
إذاً, عند إستدعاء هذه الدالة يجب أن نمرر لها عددين من النوع int.
في السطر 7 إلى السطر 11, وضعنا شرط لمقارنة قيمة المتغيرين start و end.
    في هذا الشرط قلنا أنه إذا كانت قيمة المتغير start أصغر أو تساوي قيمة المتغير end سيحدث التالي:
أولاً سيتم عرض قيمة المتغير
start.بعدها سيتم إستدعاء
CountFromTo()من جديد ( أي ستفعلreturnلنفسها ) مع زيادة قيمة العدادstartواحداً.إذاً في كل مرة تقوم الدالة
CountFromTo()باستدعاء نفسها ستأخذ ( قيمة العدادstartالسابقة زائد 1 ) و قيمة المتغيرendالثابتة كـ Arguments.عندما تصبح قيمة المتغير
startأكبر من قيمة المتغيرendستتوقف الدالةCountFromTo()عن إستدعاء نفسها.
في السطر 13, قلنا أنه بعد تتوقف الدالة CountFromTo() عن إستدعاء نفسها, سيتم إرجاع القيمة 0 إلى الدالة main() حيث تم إستدعاءها من الأساس.
ملاحظة: لو لم نضع الأمر return 0; في نهاية الدالة, كان سيظهر لك خطأ في البرنامج و السبب أن نوع الدالة في الأساس int, إذاً يجب أن ترجع أي قيمة نوعها int إلى المكان الذي تم استدعائها منه حتى لا يحدث خطأ.
public static void main (String[] args) {
CountFromTo(1, 3);
}
هنا قمنا باستدعاء الدالة CountFromTo() و مررنا لها القيمتين 1 و 3, بالتالي سيتم طباعة جميع الأعداد الصحيحة من 1 إلى 3.
إذاً أول قيمة للعداد start ستكون 1, و آخر قيمة ستكون 4, لأنها عندما تصبح أكبر من قيمة المتغير end ستتوقف عن استدعاء نفسها.
تعريف دوال تستدعي نفسها في الخوارزميات - التمرين الثاني
أكتب دالة تستدعي نفسها, إسمها CountRecursively, تعطيها عدد صحيح أكبر من 0, فتقوم بطباعة جميع الأعداد الصحيحة الموجودة من هذا العدد وصولاً إلى 1 بشكل تنازلي.
في البرنامج, قم باستدعاء الدالة CountRecursively لتجربتها.
public class Recursion {
/* ------------------------------- هنا قمنا بتعريف الدالة ------------------------------ */
public static int CountRecursively ( int counter ) {
if ( counter != 0 )
{
System.out.print("counter = " +counter+ "\n");
return CountRecursively( counter - 1 );
}
return 0;
}
/* --------------------------- من هنا يبدأ البرنامج بالتنفيذ --------------------------- */
public static void main (String[] args) {
CountRecursively(3);
}
}
public static int CountRecursively ( int counter ) {
if ( counter != 0 )
{
System.out.print("counter = " +counter+ "\n");
return CountRecursively( counter - 1 );
}
return 0;
}
هنا أنشأنا الدالة countRecursively() و حددنا أن نوعها int و وضعنا لها الباراميتر counter و نوعه int أيضاً.
إذاً, عند إستدعاء هذه الدالة يجب أن نمرر لها أي عدد من النوع int.
المتغير counter سيمثل العداد الذي يحدد كم مرة ستقوم الدالة باستدعاء نفسها حيث أنه سيتم إنقاص 1 من قيمته كلما استدعت الدالة نفسها.
الشرط الموضوع فيها يعني أنه إذا لم تكن قيمة المتغير counter تساوي 0, سيتم عرض قيمة المتغير counter, ثم إستدعاء الدالة من جديد مع إنقاص 1 من قيمة المتغير counter.
إذاً هذه الدالة تستمر في إستدعاء نفسها طالما أن قيمة المتغير counter لا تساوي 0 بعد.
في الأخير و بعد أن تتوقف الدالة عن إستدعاء نفسها, سيتم إرجاع القيمة 0 إلى الدالة main() حيث تم إستدعاءها من الأساس.
ملاحظة: لو لم نضع الأمر return 0; في نهاية الدالة, كان سيظهر لك خطأ في البرنامج و السبب أن نوع الدالة في الأساس int, إذاً يجب أن ترجع أي قيمة نوعها int إلى المكان الذي تم استدعائها منه حتى لا يحدث خطأ.
public static void main (String[] args) {
CountRecursively(3);
}
هنا قمنا باستدعاء الدالة CountRecursively() و مررنا لها القيمة 3.
إذاً أول قيمة للعداد counter ستكون 3, و آخر قيمة له ستكون 0.
تعريف دوال تستدعي نفسها في الخوارزميات - التمرين الثالث
أكتب دالة تستدعي نفسها إسمها Factorial, تعطيها عدد صحيح, فترجع الـ Factorial لهذا العدد.
في البرنامج, قم باستدعاء الدالة Factorial لتجربتها.
قيمة الـ Factorial لأي عدد صحيح تساوي ضرب جميع الأعداد الصحيحة من 1 إلى هذه العدد.
مع الإشارة إلى أننا شرحنا مبدأ الـ Factorial في دروس سابقة.
لنفترض أننا أعطينا الدالة Factorial القيمة " 4 " عند إستدعائها.
public class Recursion {
/* ------------------------------- هنا قمنا بتعريف الدالة ------------------------------ */
public static int Factorial (int n) {
if ( n > 0 )
{
return n * Factorial( n - 1 );
}
return 1;
}
/* --------------------------- من هنا يبدأ البرنامج بالتنفيذ --------------------------- */
public static void main (String[] args) {
System.out.print(Factorial(4) +"\n");
}
}
يمكن التلاعب بالشرط الموضوع في الدالة Factorial() و الحصول على نفس النتيجة.
فمثلاً يمكنك تبديل الشرط if ( n > 0 ) بالشرط if ( n != 0 ) أو if ( n > 1 ).