مقدمه ای بر تابع های بازگشتی (جاوا)

سلام دوباره.

قراره در مورد توابع بازگشتی حرف بزنیم ، یه مثال حل کنیم و ببینیم که با تابع بازگشتی چجوری میشه یه متن رو برعکس کرد و در آخر مزایا و معایبش رو بررسی کنیم :)

تابع بازگشتی

تابع های بازگشتی یا Recursive functions به تابع هایی میگن که توی خودشون ، خودشونو صدا بزنن.

همونطور که میتونید حدس بزنید این باعث میشه که ما یه حلقه داشته باشیم که تا بینهایت ادامه داره و هیچوقت متوقف نمیشه . در این صورت برنامه ما خطای java.lang.StackOverFlowError رو بهمون میده و میگه که این تابع داره تا بینهایت اجرا میشه. پس وظیفه ما اینه که یه نقطه توقفی توی تابع درست کنیم که در اون شرایط تابع وایسته.

ا Base Case

همه توابع بازگشتی برای اینکه تا بینهایت اجرا نشن نیاز به چیزی دارن به اسم base case . این base case شرایطی هستش که تابع دیگه نیازی به صدا زدن خودش نداره و مقدارش از قبل مشخصه. در واقع base case نقطه انتهایی تابع بازگشتی هست که وقتی تابع به این قسمت میرسه متوقف میشه و دیگه خودشو صدا نمیزنه.

بیاید یه مثال حل کنیم که این موضوع براتون جا بیوفته :

مثال

میخوایم با استفاده از یه تابع بازگشتی ، برنامه ای بنویسیم که یه کلمه بگیره و اونو برعکس کنه.

کدهای تابع بازگشتی ما میتونه این شکلی باشه :

void reverse(String n) {
    if (n.length() == 0) {
        return;
    } else {
        System.out.print( n.charAt(n.length() - 1) );
        reverse( n.substring(0, n.length() - 1) );
    }
}

خب بزارید توضیح بدم اینجا داره چه اتفاقی میوفته. در ورودی تابع یه رشته به اسم n گرفته میشه و بعدش توی شرط چک میشه که طول رشته ما صفر هست یا نه ، اگه صفر نبود else اجرا میشه :

توی else اول از همه یه عملیات پرینت داریم که از متدی به اسم charAt استفاده شده . وقتی از این متد روی یه رشته استفاده میکنیم ، میتونیم داخل پرانتز یه index بدیم تا حرفی که اون index رو داره ، برگردونده بشه. مثلا:

String name = "ali";

name.charAt(2) ----> خروجی = i

حالا توی مثال ما length -1 رو به عنوان index دادیم که در واقع یعنی آخرین حرف. پس آخرین حرف چاپ میشه.

توی خط بعدی خود تابع reverse صدا زده میشه اما بیاید ببینیم به عنوان ورودی بهش چی دادیم :

n.substring( 0 , n.length() -1 )

متد substring برای این استفاده میشه که قسمتی از رشته رو بگیریم . مقدار اول باید بهش index شروع کلمه مورد نظر رو بدید و در مقدار دوم جایی که کلمه مورد نظرتون تموم میشه مثلا:

String text = &quotSalam"
text.substring( 1 , 3 );       // خروجی = al

نکته : خود index 3 حساب نمیشه.

توی مثال ما index شروع رو دادیم 0 و پایان رو هم دادیم length() -1 تا تابع بازگشتی ما اینبار با مقدار جدید دوباره عملیاتشو انجام بده.

این عملیات تا وقتی ادامه داره که شرط if ما درست باشه یعنی n.length == 0 بشه ، اون وقته که تابع دیگه صدا زده نمیشه و ما از تابع reverse خارج میشیم . در واقع در این مثال base case ما میشه وقتی که طول رشته مساوی با صفر هست.

برای مثال n = ali این اتفاق میوفته :

اول وارد تابع میشیم و شرط length == 0 چک میشه و چون طول ما 3 هست میره روی else . توی اینجا اخرین حرف که i هست چاپ میشه بعدش دوباره تابع reverse صدا زده میشه اما اینبار n رو مساوی al قرار میدیم . (چون با استفاده از substring گفتیم که از اولین حرف تا حرف یکی مونده به اخر رو میخوایم)

حالا تابع دوباره شروع به کار میکنه اما با "n = "al . دوباره داخل else میره ، حرف اخر که "l" هست چاپ میشه و تابع یه بار دیگه با "n = "a صدا زده میشه و در اخر بعد اینکه اینکار برای a هم اجرا شد ، دفعه بعدی که تابع صدا زده میشه شرط length == 0 درست میشه و ما دیگه وارد else نمیشیم و تابع تموم میشه.

مزایا و معایب تابع بازگشتی

تابع های بازگشتی میتونن کد های مارو خیلی کمتر کنن ، وقتی شما مسئله ای رو با روش تابع بازگشتی حل میکنید تعداد خط های کد به مراتب کمتری دارید اما مشکل اینجاس که این توابع خوانایی پایینی دارن و برای آدم سخته که با خوندن کد ها بفهمه که چه اتفاقی داره میوفته پس در نتیجه معمولا رفع اشکال توابع بازگشتی کار خیلی آسونی نیست.

همچنین توی تابع بازگشتی RAM بیشتری مصرف میشه و معمولا کد ها کند تر از حالت عادی هستن.