Rekursi di Jawa

Untuk memahami apa itu rekursi, anda perlu memahami apa itu rekursi. Sebenarnya, tidak ada yang sukar untuk memahami fungsi tersebut; anda hanya perlu memahaminya dengan baik sekali. Dan berlatih ketika datang ke pengaturcaraan. Rekursi dalam Java - 1

Rekursi berlaku bukan sahaja dalam pengaturcaraan, tetapi juga dalam kehidupan sebenar. Ambil cermin di tangan anda dan berdiri di hadapan cermin lain. Pantulan pantulan akan terpantul dalam pantulan dan seterusnya. Anda akan melihat bilangan pantulan yang tidak terhingga menuju ke infiniti. Anda boleh mendapatkan lebih banyak tentang rekursi "sebenar" dalam artikel " Dedicated to Groundhog Day... " Mari kita kembali dari dunia nyata kepada kehidupan seharian seorang pengaturcara. Takrifan mudah: Fungsi rekursif dalam java ialah fungsi yang memanggil diri mereka sendiri. Izinkan saya memberi anda contoh yang sangat mudah dan sangat berbahaya:

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

Mengapa ia berbahaya? Saya cadangkan anda menyemaknya sendiri! Jika anda memutuskan untuk melakukan pengembaraan ini (dan kemungkinan besar anda akan melakukannya, anda pengaturcara!), tulis dalam komen apakah ralat yang akan dilemparkan oleh JVM =) Contoh ini, dan banyak lagi, menunjukkan bahawa penggunaan rekursi di Jawa mesti didekati dengan teliti . Anda perlu memahami di mana, bila dan mengapa pendekatan sedemikian untuk menyelesaikan masalah adalah wajar, dan pastikan fungsi anda tidak menjadikan pelaksanaan program menjadi "Hari Groundhog". Terdapat dua definisi yang lebih penting untuk memahami rekursi:

Asas rekursif - syarat untuk keluar dari blok panggilan rekursif - penyelesaian asas kepada masalah, dalam keadaan apabila tidak perlu memanggil rekursi.
Langkah rekursi ialah apabila fungsi memanggil dirinya sendiri apabila menukar parameter.

Contoh klasik menggunakan fungsi rekursif ialah mengira faktorial nombor. Sekiranya anda terlupa, izinkan saya mengingatkan anda: faktorial integer positif N(ditandakan sebagai N!) ialah hasil darab nombor daripada 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. By the way, faktorial sifar mengikut definisi adalah sama dengan 1. Jadi faktorial boleh didapati untuk mana-mana integer positif dan sifar (dalam bahasa matematik - untuk set integer bukan negatif atau untuk set nombor asli dan sifar). Saya rasa anda faham bahawa anda boleh memprogramkan faktorial menggunakan gelung. Sebenarnya, berikut ialah kaedah bukan rekursif untuk menyelesaikan masalah ini:

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

Mari tambah semakan bahawa nombor itu positif dan integer, dan semakan berasingan untuk sifar.

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;
}

Sekarang saya akan memberikan kod kaedah untuk menyelesaikan masalah ini secara rekursif:

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

Mari lihat hasil output untuk panggilan:

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));

Kami mendapat nilai yang dijangkakan:

Mari tambahkan output yang bagus dan hitung faktorial untuk nombor yang lebih besar:

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) + "!");

Kami mendapat: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! Dalam kes ini, penggunaan fungsi rekursif adalah wajar dan selamat. Kami telah mentakrifkan dengan jelas syarat untuk keluar dari blok rekursif, dan kami yakin ia boleh dicapai: kami memasukkan nombor integer bukan negatif, jika nombor itu sama dengan sifar atau satu, kami mengembalikan hasilnya, jika nombor itu lebih besar , kita darabkan hasil dengan fungsi nombor n-1. Menggunakan faktorial tiga sebagai contoh:

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

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

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

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

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

Mengenai penggunaan berhati-hati: apakah kelemahan fungsi ini? Jika anda memberikan kaedah nombor negatif sebagai parameter, maka semak

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

tidak masuk akal dan kita akan berakhir dalam kitaran yang tidak berkesudahan memanggil diri kita sendiri. Ia bernilai menambah cek untuk tidak negatif:

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

Dan semuanya akan baik-baik saja.

Apakah kelebihan satu kaedah berbanding kaedah yang lain? Nampaknya tidak terdapat perbezaan yang besar, tetapi sebenarnya, banyak panggilan rekursif akan memberi kesan negatif terhadap prestasi dan penggunaan memori: timbunan panggilan ialah sumber yang hampir tidak terkawal dan di bawah keadaan yang berbeza untuk memanggil fungsi rekursif yang sama, kita mungkin atau mungkin tidak mendapat masalah yang berkaitan dengan sumber ini. Hampir semua masalah yang diselesaikan menggunakan lelaran (kitaran seperti for-each) juga boleh diselesaikan secara rekursif. Kelebihan rekursi adalah kebolehbacaan dan kemudahan menulis, kami bercakap tentang kelemahan di atas: peluang untuk "menembak diri anda di kaki" bukanlah ilusi. Anda perlu lebih berhati-hati apabila menggunakan apa yang dipanggil "rekursi kompleks": Fungsi A()akan memanggil fungsi B()yang memanggil fungsi A(). Menyelesaikan masalah sedemikian memerlukan pemahaman penuh tentang cara rekursi berfungsi. Contoh tugas sedemikian: mengira nilai x^n/(n!). Faktorial, seperti yang kita bincangkan di atas, ditakrifkan pada set integer bukan negatif. Akhirnya, saya akan memberikan kod penyelesaian. Rekursi kompleks akan terdiri daripada dua kaedah:

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);
}

Untuk memasukkan rekursi, kaedah digunakan calculate, yang memanggil kaedah power, yang seterusnya memanggil kaedah calculate. Kami mentakrifkan asas rekursi dalam kaedah kuasa:

if (n == 1) return x;

Langkah rekursi juga ditakrifkan di sana:

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

Yang tinggal hanyalah menambah semakan untuk kesahihan data input:

Sebarang nombor selain daripada sifar adalah sama dengan kuasa sifar 1. Jika n = 0, maka n! = 1. Perlu mengembalikannya 1.
Sifar kepada mana-mana kuasa adalah sama dengan sifar.
Kami tidak akan menganggap ketidakpastian jenis 0^0dan akan menerima data input tersebut sebagai tidak sah.

Dengan semua semakan, kaedah akan kelihatan seperti ini:

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);
}

Nah, apabila memanggil fungsi anda perlu ingat untuk menangkap ralat:

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

Komen

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION