Rekursi di Jawa

Untuk memahami apa itu rekursi, Anda perlu memahami apa itu rekursi. Sebenarnya tidak ada yang sulit dalam memahami fungsi-fungsi tersebut, Anda hanya perlu memahaminya dengan baik sekali saja. Dan berlatihlah dalam hal pemrograman. Rekursi di Jawa - 1

Rekursi tidak hanya terjadi dalam pemrograman, tetapi juga dalam kehidupan nyata. Ambil cermin di tangan Anda dan berdirilah di depan cermin lain. Refleksi dari refleksi akan tercermin dalam refleksi dan seterusnya. Anda akan melihat pantulan yang jumlahnya tak terhingga hingga tak terhingga. Anda dapat menemukan lebih banyak tentang rekursi “nyata” di artikel “ Didedikasikan untuk Groundhog Day… ” Mari kita kembali dari dunia nyata ke kehidupan sehari-hari seorang programmer. Definisi sederhana: Fungsi rekursif di java adalah fungsi yang memanggil dirinya sendiri. Izinkan saya memberi Anda contoh yang sangat sederhana dan sangat berbahaya:

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

Mengapa itu berbahaya? Saya sarankan Anda memeriksanya sendiri! Jika Anda memutuskan untuk melakukan petualangan ini (dan kemungkinan besar Anda akan melakukannya, Anda programmer!), tulis di komentar kesalahan apa yang akan ditimbulkan oleh JVM =) Contoh ini, dan banyak lainnya, menunjukkan bahwa penggunaan rekursi di Java harus didekati dengan hati-hati . Anda perlu memahami di mana, kapan, dan mengapa pendekatan pemecahan masalah ini dibenarkan, dan pastikan bahwa fungsi Anda tidak mengubah eksekusi program menjadi "Groundhog Day". Ada dua definisi yang lebih penting untuk memahami rekursi:

Basis rekursi - kondisi untuk keluar dari blok panggilan rekursif - solusi dasar untuk masalah tersebut, dalam kondisi ketika tidak perlu memanggil rekursi.
Langkah rekursi adalah ketika suatu fungsi memanggil dirinya sendiri ketika mengubah parameter.

Contoh klasik penggunaan fungsi rekursif adalah menghitung faktorial suatu bilangan. Jika Anda lupa, izinkan saya mengingatkan Anda: faktorial dari bilangan bulat positif N(dilambangkan dengan N!) adalah hasil kali bilangan dari 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Omong-omong, faktorial dari nol menurut definisi sama dengan 1. Jadi faktorial dapat ditemukan untuk sembarang bilangan bulat positif dan nol (dalam bahasa matematika - untuk himpunan bilangan bulat non-negatif atau untuk himpunan bilangan asli dan nol). Saya rasa Anda memahami bahwa Anda dapat memprogram faktorial menggunakan loop. Sebenarnya, berikut adalah metode non-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 kita tambahkan pemeriksaan bahwa bilangan tersebut positif dan bilangan bulat, dan pemeriksaan terpisah untuk nol.

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 kode metode 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 kita lihat hasil keluaran untuk panggilan tersebut:

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 mendapatkan nilai yang diharapkan:

Mari tambahkan keluaran yang bagus dan hitung faktorial untuk bilangan 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) + "!");

Kita mendapatkan: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! Dalam hal ini, penggunaan fungsi rekursif dibenarkan dan aman. Kami telah mendefinisikan dengan jelas kondisi untuk keluar dari blok rekursif, dan kami yakin hal itu dapat dicapai: kami memasukkan bilangan bulat non-negatif, jika bilangan tersebut sama dengan nol atau satu, kami mengembalikan hasilnya, jika bilangan tersebut lebih besar , kita mengalikan hasilnya dengan fungsi bilangan tersebut 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 kehati-hatian dalam penggunaan: apa kerentanan fungsi ini? Jika Anda memberikan suatu metode angka negatif sebagai parameter, maka centang

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

tidak masuk akal dan kita akan berakhir dalam siklus menyebut diri kita sendiri tanpa akhir. Sebaiknya tambahkan tanda centang untuk non-negatif:

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

Dan semuanya akan baik-baik saja.

Apa kelebihan satu metode dibandingkan metode lainnya? Tampaknya tidak ada perbedaan besar, namun kenyataannya, banyak panggilan rekursif akan berdampak negatif pada kinerja dan konsumsi memori: tumpukan panggilan adalah sumber daya yang hampir tidak dapat dikontrol dan dalam kondisi berbeda untuk memanggil fungsi rekursif yang sama, kami mungkin atau mungkin tidak mendapatkan masalah terkait dengan sumber daya ini. Hampir semua masalah yang diselesaikan dengan menggunakan iterasi (siklus seperti for-each) juga dapat diselesaikan secara rekursif. Keuntungan dari rekursi adalah keterbacaan dan kemudahan penulisan, kita telah membicarakan kerugiannya di atas: kesempatan untuk "menembak diri sendiri" bukanlah ilusi. Anda harus lebih berhati-hati saat menggunakan apa yang disebut “rekursi kompleks”: Suatu fungsi A()akan memanggil fungsi B()yang memanggil suatu fungsi A(). Menyelesaikan masalah seperti itu memerlukan pemahaman penuh tentang cara kerja rekursi. Contoh tugas tersebut: menghitung nilai x^n/(n!). Faktorial, seperti yang telah kita bahas di atas, didefinisikan pada himpunan bilangan bulat non-negatif. Terakhir, saya akan memberikan kode solusinya. Rekursi kompleks akan terdiri dari dua metode:

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 memasuki rekursi, digunakan suatu metode calculate, yang memanggil suatu metode power, yang pada gilirannya memanggil suatu metode calculate. Kami mendefinisikan dasar rekursi dalam metode pangkat:

if (n == 1) return x;

Langkah rekursi juga didefinisikan di sana:

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

Tetap menambahkan pemeriksaan validitas data yang dimasukkan:

Bilangan apa pun selain nol sama dengan pangkat nol 1. Jika n = 0kemudian n! = 1. Perlu mengembalikannya 1.
Nol pangkat apa pun sama dengan nol.
Kami tidak akan mempertimbangkan ketidakpastian jenis 0^0dan akan menerima data masukan tersebut sebagai tidak valid.

Dengan semua pemeriksaan, metodenya akan terlihat 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, saat memanggil suatu fungsi, Anda harus ingat untuk mengetahui kesalahannya:

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

Komentar

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