جلسه ۴۹: بازگشت و تجسم آن در حافظه در جاوا

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

• تخصیص حافظه به متدها
• مثال – محاسبه فاکتوریل
• • فاکتوریل چیست؟
  • کد
  • حالت پایه
  • حالت بازگشتی
  • تجسم فراخوانی های بازگشتی در پشته

تخصیص حافظه به متدها

وقتی متدی فراخوانی می شود ، وضعیت متد همراه با اطلاعات مربوط به محل فراخوانی ، روی «پشته فراخوانی ها» (call stack) قرار می گیرد. این به اجراکننده برنامه (run-time) نشان می دهد که وقتی متد فعلی به پایان می رسد باید به کجا برگردد و از کدام خط اجرای برنامه را ادامه دهد. هر فراخوانی بازگشتی یک آیتم جدید روی پشته قرار می دهد. هر آیتم روی پشته شامل اطلاعاتی مانند آدرس بازگشت ، متغیرهای آرگومان و متغیرهای محلی مربوط به آن فراخوانی متد است. وقتی متدی خود را فراخوانی می کند ، فراخوانی متد جدید به بالای «پشته فراخوانی ها» اضافه می شود و هنگام پردازش فراخوانی بازگشتی جدید ، اجرای فعلی متد متوقف می شود. وقتی اجرا به حالت پایه رسید ، آیتم های روی پشته ، شروع به بیرون آمدن از پشته می کنند تا اینکه پشته خالی شود.

مثال – محاسبه فاکتوریل

فاکتوریل چیست؟

فاکتوریل حاصل ضرب یک عدد صحیح و تمام اعداد صحیح مثبت کوچکتر از آن است. با علامت ! مشخص می شود. مثلاً !۴ (چهار فاکتوریل خوانده می شود) به صورت زیر محاسبه می شود:

۴! = ۴ X 3 X 2 X 1 = 24

۶! = ۶ X 5 X 4 X 3 X 2 X 1 = 720

کد

class Factorial {
    // Recursive function
    private static int factorial(int n) {
      // Base case
      if (n == 1) {
        return 1;
      }
      // Recursive case
      else {
        return (n * factorial(n-1));
      }
    }

    public static void main( String args[] ) {
        // Calling from main
        int result = factorial(5);
        System.out.println("Factorial of 5 is: " + result);
    }
}

اکنون به طور خلاصه در مورد دو قسمت اصلی یک متد بازگشتی ، حالت پایه و حالت بازگشتی ، که در کد بالا پیاده سازی شده است ، بحث خواهیم کرد.

حالت پایه

ما حالت پایه را در خط ۵ تعریف کرده ایم که در آن بیان می شود وقتی متغیر n برابر ۱ باشد ، متد باید خاتمه یابد و شروع به برداشتن آیتم ها از بالای پشته کند.

حالت بازگشتی

این شبیه فرمولی است که در بالا برای فاکتوریل آورده شده است. به عنوان مثال ، فاکتوریل ۳ به صورت ۱×۲×۳ است. ما عدد صحیح n را در فاکتوریل عدد صحیح قبل از خود یعنی factorial(n-1) ضرب می کنیم و این کار را ادامه می دهیم تا به factorial(1) برسیم.

تجسم فراخوانی های بازگشتی در پشته

تصویر زیر ممکن است به درک شما از عملکرد پشته کمک کند:

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