Memahami rekursi dengan JavaScript

Sesetengah masalah lebih sesuai untuk rekursi. Sebagai contoh, urutan seperti urutan Fibonacci mempunyai definisi rekursif. Setiap nombor dalam urutan adalah jumlah dua nombor pertama dalam urutan. Masalah yang perlu dibina atau dilalui dengan struktur data pokok juga boleh diselesaikan dengan rekursi. Melatih diri anda untuk berfikir secara rekursif akan memberi anda kemahiran yang kuat untuk menyelesaikan masalah tersebut.

Dalam tutorial ini, saya akan menerangkan langkah demi langkah bagaimana beberapa fungsi rekursif berfungsi dan menunjukkan kepada anda beberapa teknik untuk menentukan secara sistematik fungsi rekursif.

Kandungan:

• Apa itu rekursi?
• Rekursi digital
• Senaraikan rekursi
• Bina senarai
• Rekursi ekor
• Meringkaskan

Apa itu rekursi?

Fungsi yang ditakrifkan secara rekursif adalah fungsi yang ditakrifkan oleh versi mudah mereka sendiri. Berikut adalah contoh yang mudah:

 fungsi doa (n) {
    // ...
    jika (n> 0) {
        DOA (N-1);
    }
}

Untuk memahami secara konseptual bagaimana rekursi berfungsi, kita akan melihat contoh yang bebas kod. Katakan anda bertanggungjawab untuk menjawab panggilan dari syarikat. Oleh kerana ini adalah syarikat yang sibuk, telefon anda mempunyai beberapa talian telefon, anda boleh mengendalikan pelbagai panggilan telefon pada masa yang sama. Setiap talian telefon mempunyai butang pada telefon bimbit, yang akan berkelip apabila terdapat panggilan masuk. Hari ini, apabila anda pergi bekerja dan menghidupkan telefon, empat baris kilat pada masa yang sama. Jadi anda mula menjawab semua panggilan.

Anda mengambil baris pertama dan memberitahu mereka: "Tunggu." Seterusnya, anda mengambil baris ketiga dan meletakkannya bersiap sedia, dan sebagainya. Akhirnya, apabila anda menyelesaikan setiap panggilan, anda kembali ke pemanggil sebelumnya, lengkapkan panggilan itu dan hang up.

Setiap panggilan dalam contoh ini adalah serupa dengan panggilan rekursif dalam fungsi. Apabila anda mendapat panggilan, ia dimasukkan ke dalam timbunan panggilan (dalam kod). Jika anda tidak dapat melengkapkan panggilan dengan segera, anda meletakkannya dengan bersedia. Jika panggilan fungsi anda tidak dapat dikira dengan serta -merta, ia akan kekal dalam timbunan panggilan. Apabila anda dapat menjawab panggilan, ia akan dijemput. Apabila kod anda dapat mengira panggilan fungsi, ia keluar dari timbunan. Ingat metafora ini apabila anda melihat contoh kod berikut.

Rekursi digital

Semua fungsi rekursif memerlukan kes asas supaya mereka dapat ditamatkan. Walau bagaimanapun, hanya menambah kes asas ke fungsi kami tidak menghalangnya daripada berjalan tak terhingga. Fungsi ini mesti mempunyai langkah untuk membawa kita lebih dekat kepada keadaan asas. Ini adalah langkah rekursif. Dalam langkah rekursif, masalahnya dikurangkan kepada versi masalah yang lebih kecil.

Katakan anda mempunyai fungsi yang mengadili semua nombor bermula dari n. Ini dipanggil fungsi faktorial, kita menulisnya sebagai 4!, Jika n sama dengan 1.

Dalam setiap langkah, anda akan menolak 1 dari nombor semasa. Apakah keadaan rekursif? Kes rekursif adalah fakta fungsi (4).

16. Adakah 4 sama dengan 1? tidak. Letakkan fakta (3).
17. Adakah 3 sama dengan 1? tidak. Letakkan fakta (2).
18. Adakah 2 sama dengan 1? tidak. Letakkan fakta (1).
19. Adakah 1 sama dengan 1? Ya. Mengembalikan fakta (2) dan pulangan 2.
20. Dapatkan 3 * fakta (2) adalah fakta (4) dan pulangan 24.

Berikut adalah cara lain untuk melihat bagaimana fungsi mengendalikan setiap panggilan:

 <code>fact(4) 4 * fact(3) 4 * ( 3 * fact(2) ) 4 * ( 3 * ( 2 * fact(1) )) 4 * ( 3 * ( 2 * 1 ) ) 4 * ( 3 * 2 ) 4 * 6 24</code>

Dalam kes rekursif, parameter harus berubah dan membawa anda lebih dekat kepada kes asas. Parameter ini harus diuji dalam kes asas. Dalam contoh terdahulu, kerana kita menolak 1 dalam kes rekursif, dalam kes asas kita menguji sama ada parameter adalah sama dengan 0.

cabaran

1. Melaksanakan fungsi jumlah menggunakan gelung dan bukannya rekursif.
2. Buat fungsi yang secara rekursif mengalikan dua nombor. Sebagai contoh, 0;
3. Memudahkan fungsi penapis supaya ia membuang semua item dari senarai. Sebagai contoh, ["a", "b", "d"].

Rekursi ekor

Rekursi ekor adalah satu bentuk rekursi yang membolehkan pengkompil melakukan pengoptimuman panggilan ekor (TCO) untuk mencegah banyak kelemahan prestasi rekursi biasa. Di samping itu, rekursi ekor menyelesaikan masalah kedalaman maksimum panggilan fungsi. Walau bagaimanapun, anda perlu menulis fungsi entah bagaimana untuk menjadikannya berfungsi.

Rekursi ekor sesuai untuk fungsi yang memanggil fungsi rekursif pada akhir fungsi. Sebagai contoh, di sini adalah versi rekursif ekor jumlah () fungsi: keseluruhan nilai pulangan jumlah () adalah keseluruhan nilai pulangan, jadi runtime dengan selamat boleh membuang fungsi luaran dan mengembalikan hanya hasil fungsi dalaman. Namun, ramai orang akan melakukan perjalanan seperti ini:

 fungsi nottailRecursive (n) {
    // ...
    Kembali NottailRecursive (N) 1
}

Anda mungkin berfikir ini menggunakan rekursi ekor kerana fungsi rekursif dipanggil pada akhirnya. Tetapi, ia tidak. Ini kerana JavaScript mesti kembali ke fungsi luaran untuk menambah 1. Salah satu cara yang anda boleh menulis semula adalah untuk lulus 1 ke dalam hujah supaya fungsi dalaman dapat melakukan pengiraan itu.

Tidak semua pelayar kini menyokong pengoptimuman panggilan ekor, tetapi ia berada dalam standard ES, jadi kita dapat melihat lebih banyak sokongan untuknya pada masa akan datang. Tambahan pula, ia biasanya merupakan amalan yang baik kerana ia biasanya mengasingkan perubahan kepada parameter fungsi.

cabaran

Membina semula fungsi rekursif dalam artikel ini ke dalam fungsi rekursif ekor.

Meringkaskan

Terdapat tiga bahagian untuk fungsi rekursif. Yang pertama adalah keadaan asas, iaitu keadaan penamatan. Yang kedua adalah langkah yang membawa kita lebih dekat kepada keadaan asas. Yang ketiga ialah langkah rekursif, di mana fungsi memanggilnya dengan input mudah.

Rekursi adalah seperti lelaran. Mana -mana fungsi yang anda boleh tentukan secara rekursif atau menggunakan gelung. Perkara -perkara lain yang perlu dipertimbangkan semasa menggunakan rekursi termasuk senarai bersarang rekursif dan panggilan rekursif yang dioptimumkan.

Anda boleh refactor fungsi rekursif ke dalam fungsi rekursif ekor, yang dapat memberikan kelebihan prestasi.

Sumber yang baik untuk terus belajar rekursi adalah buku The Little Schemer. Ia menggunakan format Q & A untuk mengajar anda bagaimana untuk berfikir secara rekursif.

Siaran ini telah dikemas kini dengan sumbangan Jacob Jackson. Jacob adalah pemaju web, penulis teknologi, freelancer dan penyumbang sumber terbuka.

Atas ialah kandungan terperinci Memahami rekursi dengan JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!