السلام عليكــم ورحمـة الله وبركاتــه ،،
جمبعنا نعرف ال Recursion وهى عملية نداء الدالة لنفسها
ولكن للاسف معظم الكتب تتحدث عن الbasic recursion متجاهلة الTail Recursion مع ان الاخر اسرع بكثير
لنبداء لاوضح الفرق بينهم
الrecursion العادى يكون القيمة العائدة من الدالة بهذا الشكل
return value * function(value)
اى على طريقة الفاكتوريال تكون على هذا الشكل
return n * fact(n - 1)
ولكن للاسف ان لتلك الطريقة عيوب من حيث السرعة وoverhead من حيث الstack لان الدالة تظل تنسخ نفسها فى المكدس stack الى ان تصل الى شرط معين بحيث تتوقف عن مناداة نفسها وتقوم بالعودة تدريجيا الى الدالة الاصلية لتعود الى الدالة الاصلية ثم الى مستدعى الدالة اساسا
ولكن هناك الTail Recursion وهى افضل من حيث السرعة وهى تكون بشكل اكثر ذكاء وهى على هذا الشكل
return function(some value)
لنعود لمثال الفاكتوريال
int facttail(int n, int a) {
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return a;
else
return facttail(n - 1, n * a);
}االذكاء هنا انك تركت مجال للمترجم ان يقوم بعمل تحسين للكود فالreturn عبارة عن نداء اخر ولا يشوبها قيمة تجبر المترجم على الحفاظ على الدالة السابقة لحين عودة الrecursion
وبهذا تسمح للمترجم ان لا يقوم بصناعة دالة جديدة فى المكدس وبدلا من ذلك يقوم باستخدام نفس الدالة فى المكدس ولكن بالقيم الاخيرة وهذا ما تفعلة معظم المترجمات الحديثة (ان لم يكن كلها ) وبهذا تخلصت من مشاكل وبطى المكدس ومن مشاكل حجز وحذف الدوال من المكدس
اعلم انى لست بارع فى الشرح ولذلك فمعلومات الموضوع من كتاب Mastering Algorithms with C فى الفصل الثالث
ما ارائكم حول الافكار المناسبة لتحويل الدوال من الrecursion العادى الى الtail recursion وما مدى نجاح وسهولة الوصول الى هذا الحل ؟
