Kajian Kes: Faktor Pengkomputeran

Kaedah rekursif ialah kaedah yang memanggil dirinya sendiri. Banyak fungsi matematik ditakrifkan menggunakan rekursi. Mari kita mulakan dengan contoh mudah. Faktorial bagi suatu nombor n boleh ditakrifkan secara rekursif seperti berikut:

0! = 1;
n! = n × (n - 1)!; n > 0

Bagaimana anda mencari n! untuk n yang diberikan? Untuk mencari 1! adalah mudah, kerana anda tahu bahawa 0! ialah 1 dan 1! ialah 1 × 0 !. Dengan mengandaikan bahawa anda tahu (n - 1)!, anda boleh mendapatkan n! serta-merta dengan menggunakan n × (n - 1)!. Oleh itu, masalah pengkomputeran n! dikurangkan kepada pengkomputeran (n - 1)!. Apabila mengira (n - 1)!, anda boleh menggunakan idea yang sama secara rekursif sehingga n dikurangkan kepada 0.

Biar faktorial(n) menjadi kaedah pengkomputeran n!. Jika anda memanggil kaedah dengan n = 0, ia segera mengembalikan hasilnya. Kaedah ini mengetahui cara menyelesaikan kes paling mudah, yang dirujuk sebagai kes asas atau keadaan berhenti. Jika anda memanggil kaedah dengan n > 0, ia mengurangkan masalah menjadi submasalah untuk mengira faktorial n - 1. submasalah pada asasnya adalah sama dengan masalah asal, tetapi ia lebih mudah atau lebih kecil. Oleh kerana submasalah mempunyai sifat yang sama seperti masalah asal, anda boleh memanggil kaedah dengan hujah yang berbeza, yang dirujuk sebagai panggilan rekursif.

Algoritma rekursif untuk pengkomputeran faktorial(n) boleh diterangkan secara ringkas seperti berikut:

jika (n == 0)
pulangkan 1;
lain
pulangkan n * faktorial(n - 1);

Panggilan rekursif boleh menghasilkan lebih banyak panggilan rekursif, kerana kaedah ini terus membahagikan submasalah kepada submasalah baharu. Untuk kaedah rekursif untuk ditamatkan, masalah akhirnya mesti dikurangkan kepada kes berhenti, di mana kaedah mengembalikan hasil kepada pemanggilnya. Pemanggil kemudian melakukan pengiraan dan mengembalikan hasilnya kepada pemanggilnya sendiri. Proses ini berterusan sehingga hasilnya diserahkan kembali kepada pemanggil asal. Masalah asal kini boleh diselesaikan dengan mendarab n dengan hasil faktorial(n - 1).

Kod di bawah memberikan atur cara lengkap yang menggesa pengguna memasukkan integer bukan negatif dan memaparkan faktorial untuk nombor tersebut.

Kaedah faktorial (baris 17–22) pada asasnya ialah terjemahan langsung definisi matematik rekursif untuk faktorial ke dalam kod Java. Panggilan kepada faktorial adalah rekursif kerana ia memanggil dirinya sendiri. Parameter yang diserahkan kepada faktorial dikurangkan sehingga mencapai kes asas 0.

Anda melihat cara menulis kaedah rekursif. Bagaimanakah rekursi berfungsi di belakang tabir? Rajah di bawah menggambarkan pelaksanaan panggilan rekursif, bermula dengan n = 4.

Penggunaan ruang tindanan untuk panggilan rekursif ditunjukkan dalam Rajah di bawah.

Lebih mudah dan cekap untuk melaksanakan kaedah faktorial menggunakan gelung. Walau bagaimanapun, kami menggunakan kaedah faktorial rekursif di sini untuk menunjukkan konsep rekursi. Kemudian dalam bab ini, kami akan mengemukakan beberapa masalah yang bersifat rekursif dan sukar untuk diselesaikan tanpa menggunakan rekursif.

Jika rekursi tidak mengurangkan masalah dengan cara yang membolehkannya akhirnya menumpu ke dalam kes asas atau kes asas tidak ditentukan, rekursi tak terhingga boleh berlaku. Sebagai contoh, katakan anda tersilap menulis kaedah faktorial seperti berikut:

faktorial panjang statik awam(int n) {
pulangkan n * faktorial(n - 1);
}

Kaedah berjalan tanpa had dan menyebabkan StackOverflowError.

Contoh yang dibincangkan dalam bahagian ini menunjukkan kaedah rekursif yang memanggil dirinya sendiri. Ini dikenali sebagai rekursi langsung. Anda juga boleh mencipta rekursi tidak langsung. Ini berlaku apabila kaedah A memanggil kaedah B, yang seterusnya memanggil kaedah A. Malah mungkin terdapat beberapa lagi kaedah yang terlibat dalam rekursi. Contohnya, kaedah A memanggil kaedah B, yang memanggil kaedah C, yang memanggil kaedah A.

Atas ialah kandungan terperinci Kajian Kes: Faktor Pengkomputeran. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!