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

برای درک اینکه بازگشت چیست، باید بفهمید که بازگشت چیست. در واقع، درک این کارکردها هیچ مشکلی ندارد، فقط یک بار باید آن را به خوبی درک کنید. و در مورد برنامه نویسی تمرین کنید. بازگشت نه تنها در برنامه نویسی، بلکه در زندگی واقعی نیز رخ می دهد. یک آینه در دستان خود بگیرید و در مقابل آینه دیگری بایستید. بازتاب انعکاس در بازتاب و غیره منعکس خواهد شد. تعداد بی نهایت انعکاس را خواهید دید که به سمت بی نهایت می روند. می توانید اطلاعات بیشتری درباره بازگشت «واقعی» در مقاله « تقدیم به روز گراندهاگ... » بیابید، بیایید از دنیای واقعی به زندگی روزمره یک برنامه نویس برگردیم. تعریف ساده: توابع بازگشتی در جاوا توابعی هستند که خود را فراخوانی می کنند. بگذارید یک مثال بسیار ساده و بسیار مضر برای شما بزنم:

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

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

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

یک مثال کلاسیک استفاده از یک تابع بازگشتی، محاسبه فاکتوریل یک عدد است. اگر فراموش کردید، بگذارید به شما یادآوری کنم: فاکتوریل یک عدد صحیح مثبت N(که با N نشان داده می شود) حاصل ضرب اعداد از 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. به هر حال، فاکتوریل صفر طبق تعریف برابر با 1 است. بنابراین فاکتوریل را می توان برای هر عدد صحیح مثبت و صفر پیدا کرد (در زبان ریاضیات - برای مجموعه اعداد صحیح غیر منفی یا برای مجموعه اعداد طبیعی و صفر). فکر می کنم متوجه شده اید که می توانید فاکتوریل را با استفاده از حلقه ها برنامه ریزی کنید. در واقع، در اینجا یک روش غیر بازگشتی برای حل این مشکل وجود دارد:

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

بیایید یک چک که عدد مثبت و یک عدد صحیح است و یک بررسی جداگانه برای صفر اضافه کنیم.

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

اکنون کد متد را برای حل این مشکل به صورت بازگشتی می دهم:

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

بیایید به نتایج خروجی برای تماس ها نگاه کنیم:

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

ما مقادیر مورد انتظار را دریافت می کنیم:

1
1
2
6
24
120
720

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

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

دریافت می کنیم: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! در این مورد، استفاده از یک تابع بازگشتی موجه و ایمن است. ما شرایط خروج از بلوک بازگشتی را به وضوح تعریف کرده ایم و مطمئن هستیم که قابل دستیابی است: یک عدد صحیح غیر منفی وارد می کنیم، اگر عدد برابر با صفر یا یک باشد، نتیجه را برمی گردانیم، اگر عدد بزرگتر باشد. ، حاصل را در تابعی از عدد ضرب می کنیم n-1. استفاده از فاکتوریل سه به عنوان مثال:

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

با توجه به احتیاط در استفاده: آسیب پذیری این تابع چیست؟ اگر به یک روش یک عدد منفی به عنوان پارامتر بدهید، آن را بررسی کنید

if (n == 1 || n == 0) {
    return result;
}

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

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

و همه چیز خوب خواهد بود. مزیت یک روش نسبت به روش دیگر چیست؟ به نظر نمی‌رسد تفاوت زیادی وجود داشته باشد، اما در واقع، بسیاری از تماس‌های بازگشتی تأثیر منفی بر عملکرد و مصرف حافظه خواهند داشت: پشته تماس یک منبع تقریباً غیرقابل کنترل است و تحت شرایط مختلف برای فراخوانی یک تابع بازگشتی یکسان است. ممکن است مشکلاتی در ارتباط با این منبع داشته باشیم یا نه. تقریباً تمام مسائل حل شده با استفاده از تکرارها (چرخه هایی مانند for-each) نیز می توانند به صورت بازگشتی حل شوند. مزیت بازگشت خوانایی و سهولت نوشتن است، ما در مورد معایب بالا صحبت کردیم: فرصت "شلیک به پای خود" توهم نیست. هنگام استفاده از به اصطلاح "بازگشت پیچیده" باید حتی بیشتر مراقب باشید: یک تابع تابعی را A()فراخوانی می کند B()که یک تابع را فراخوانی می کند.حل A()چنین مسائلی مستلزم درک کامل نحوه عملکرد بازگشت است. مثالی از چنین کاری: محاسبه مقدار x^n/(n!). فاکتوریل، همانطور که در بالا بحث کردیم، بر روی مجموعه ای از اعداد صحیح غیر منفی تعریف می شود. در نهایت کد راه حل را می دهم. بازگشت پیچیده از دو روش تشکیل می شود:

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

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

if (n == 1) return x;

مرحله بازگشت نیز در آنجا تعریف شده است:

return x * calculate(x, n - 1);

باقی مانده است که یک بررسی برای اعتبار داده های ورودی اضافه کنید:

• هر عددی غیر از صفر برابر با توان صفر است 1. اگر n = 0پس از آن n! = 1. نیاز به برگرداندن 1آن
• صفر به هر توانی برابر با صفر است.
• ما عدم قطعیت نوع را در نظر نمی گیریم 0^0و چنین داده های ورودی را نامعتبر می پذیریم.

با تمام بررسی‌ها، روش‌ها به شکل زیر خواهند بود:

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

خوب، هنگام فراخوانی یک تابع باید به یاد داشته باشید که خطا را دریافت کنید:

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}