java, آموزش قدم به قدم جاوا, جاوا

توابع بازگشتی در جاوا (Recursive Function)

توابع بازگشتی در جاوا

در این جلسه تیم کدگیت را با آموزش توابع بازگشتی در جاوا همراهی کنید.پیش نیاز این آموزش شامل موارد زیر است:

  1. آشنایی با if
  2. آشنایی با متد
  3. آشنایی با for

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

توابع بازگشتی یک تکنیک برنامه نویسی هستند که در آن یک متد (تابع) خودش را صدا میزند. البته ممکن است این کار کمی عجیب به نظر برسد!!! یا حتی ممکن است یک اشتباه در نظر گرفته شود(یک متد خودش را صدا بزند!!).اما در هر صورت توابع بازگشتی در برنامه نویسی، یکی از موثرترین تکنیک ها است دقیقا مثل استفاده از بوت استرپ است (بوت استرپ حتما کار کرده اید؟!!!!).

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

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

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

برای محاسبه !1 ابتدا میدانیم !0 برابر با 1 است پس 1*1 میشود یک!! برای محاسبه N! کافیست بدانیم N-1 ! چند است سپس حاصل را در N ضرب میکنیم و جواب را بدست می آوریم. میتوان نتیچه گرفت ما مسئله خود را کوچک کردیم یعنی از N! به (N-1)! یا اصطلاحا یک زیر مسئله (subproblem) ایجاد کردیم. برای محاسبه !(N-1) نیز همین روند یعنی کوچک کردن مسئله را ادامه میدهیم تا به شرط پایه یا صفر برسیم.

اگر دقت کرده باشید ما هر بار مسئله را کوچک و کوچکتر کردیم تا به شرط پایه برسیم. برای محاسبه N! ما مسئله را کوچک میکنیم و به دنبال !(N-1) هستیم. دوباره !(N-1) را کوچکتر میکنیم و به محاسبه !(N-2) میپردازیم. اینقد این کار را ادامه میدهیم تا به صفر برسیم. این که ما یک کار را n بار انجام میدهیم را با توابع بازگشتی میتوان انجام داد(شبیه به حلقه for).

توابع بازگشتی در جاوا

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

     public static long recursivefactorial(int n) {
          if (n == 0) // Base case
              return 1;
          else
              return n * recursivefactorial(n - 1); // Recursive call
     }

در کد بالا ما متدی به نام recursivefactorial نوشتیم که یک ورودی میگیرد و آن هم عددی است که میخواهیم فاکتوریل آن را محاسبه کنیم.

در متد ما یک if وجود دارد که شرط پایه را بررسی میکند و یک else که فاکتوریل را به صورت بازگشتی صدا میزند.

روند محاسبه توابع بازگشتی در جاوا به صورت تصویر زیر است(تصویر زیر تا !1 رفته است)

همانطور که در تصویر توابع بازگشتی در جاوا میبینید ما فرض کردیم !5 را میخواهیم محاسبه کنیم. برای محاسبه نیاز به !4 داریم پس ما همان تابع را روی !4 صدا میزنیم حال برای محاسبه !4 نیاز به !3 فاکتوریل داریم پس همان تابع را روی !3 صدا میزنیم و همین کار را ادامه میدهیم تا به 1 برسیم.

حال که به 1 رسیدیم نوبت به بازگشت مقادیر است. ما مقدار 1 را برمیگردانیم و متدی که !1 را صدا زده بود(یعنی !2) جواب آن را دارد پس !2 را محاسبه و آن را return میکند. متدی که !2 را صدا زده بود(یعنی!3) جواب آن را دارد پس به محاسبه !3 میپردازد و آن را return میکند. این کار را تا جایی انجام میدهیم تا به !5 برسیم.

نوشته های مشابه

1 دیدگاه در “توابع بازگشتی در جاوا (Recursive Function)

  1. ایمان گفت:

    درود بر شرفت خیلی خوب یاد دادی چقدر میگشتم یه اموزش خوب در مورد فاکتوریل و توابع بازگشتی پیدا کنم

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *