جاوا

جلسه ۵۳: درک یک مسئله بازگشتی در جاوا

class ExampleClass {

    private static void printNum(int n) {
        // Base case
        if (n == 0) {
            return;
        }
        // Recursive case
        printNum(n-1);
        System.out.print(n + " ");
    }

    public static void main( String args[] ) {
        // Recursive method called here
        printNum(6);   
    }
}

توضیح کد

اگر متد را همانطور که نوشته شده بخوانیم ، ممکن است انتظار داشته باشیم که خروجی ۶ ، ۵ ، ۴ ، ۳ ، ۲ ، ۱ باشد. آیا به نظر نمی رسد که این متد ابتدا ۶ را چاپ می کند و سپس خروجی به تدریج کاهش می یابد؟ متأسفانه ، این درست نیست. قبل از اینکه بتوانیم به پایان متد برسیم ، باید فراخوانی بازگشتی را ارزیابی کنیم. قطعه کد زیر نحوه اجرای کد را نشان می دهد.
printNum(6)
    printNum(5)
        printNum(4)
            printNum(3)
                printNum(2)
                    printNum(1)
                        printNum(0)
                        System.out.print(1)
                    System.out.print(2)
                System.out.print(3)
            System.out.print(4)
        System.out.print(5)
    System.out.print(6)
همانطور که بعد از اجرای کد مشاهده کردید ، خروجی ۱ ، ۲ ، ۳ ، ۴ ، ۵ ، ۶ به دست آمد. جالب است ، موافقید؟ این نکته مهمی است که باید تشخیص دهید: همیشه خروجی حاصل از یک متد بازگشتی همانطور که در ترتیب کد دیده می شود ، ظاهر نمی شود.

نحوه محاسبه خروجی

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

تجسم از طریق پشته

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

پیگیری متغیرها

این کار هنگام نوشتن متدهای بازگشتی بسیار مهم است. هرچه متد پیچیده تر می شود ، ذخیره همه چیز در ذهن شما و پیگیری کلیه متغیرها و فراخوانی های متد دشوارتر می شود ، خصوصاً به این دلیل که همانطور که از مثال بالا دیدیم ، ما مجبوریم بازگشت را با ترتیبی متفاوت انجام دهیم.

ترسیم درخت بازگشتی

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

تمرین

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

درک مسئله

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

مثال

به نظر شما خروجی کد زیر چیست؟ قبل از اجرای کد ، نتیجه را حدس بزنید و سپس به نتیجه نگاه کنید.
class ExampleClass {

    private static void printNum(int n) {
        // Base case
        if (n == 0) {
            return;
        }
        // Recursive case
        printNum(n-1);
        System.out.print(n + " ");
    }

    public static void main( String args[] ) {
        // Recursive method called here
        printNum(6);   
    }
}

توضیح کد

اگر متد را همانطور که نوشته شده بخوانیم ، ممکن است انتظار داشته باشیم که خروجی ۶ ، ۵ ، ۴ ، ۳ ، ۲ ، ۱ باشد. آیا به نظر نمی رسد که این متد ابتدا ۶ را چاپ می کند و سپس خروجی به تدریج کاهش می یابد؟ متأسفانه ، این درست نیست. قبل از اینکه بتوانیم به پایان متد برسیم ، باید فراخوانی بازگشتی را ارزیابی کنیم. قطعه کد زیر نحوه اجرای کد را نشان می دهد.
printNum(6)
    printNum(5)
        printNum(4)
            printNum(3)
                printNum(2)
                    printNum(1)
                        printNum(0)
                        System.out.print(1)
                    System.out.print(2)
                System.out.print(3)
            System.out.print(4)
        System.out.print(5)
    System.out.print(6)
همانطور که بعد از اجرای کد مشاهده کردید ، خروجی ۱ ، ۲ ، ۳ ، ۴ ، ۵ ، ۶ به دست آمد. جالب است ، موافقید؟ این نکته مهمی است که باید تشخیص دهید: همیشه خروجی حاصل از یک متد بازگشتی همانطور که در ترتیب کد دیده می شود ، ظاهر نمی شود.

نحوه محاسبه خروجی

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

تجسم از طریق پشته

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

پیگیری متغیرها

این کار هنگام نوشتن متدهای بازگشتی بسیار مهم است. هرچه متد پیچیده تر می شود ، ذخیره همه چیز در ذهن شما و پیگیری کلیه متغیرها و فراخوانی های متد دشوارتر می شود ، خصوصاً به این دلیل که همانطور که از مثال بالا دیدیم ، ما مجبوریم بازگشت را با ترتیبی متفاوت انجام دهیم.

ترسیم درخت بازگشتی

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

تمرین

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

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

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

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

دکمه بازگشت به بالا