Kit Temuduga: Rekursi.
Memanggil diri anda berulang kali, tetapi menjadi lebih mudah dengan setiap panggilan—itu secara ringkasnya berulang! Ia merupakan definisi tidak formal, tetapi ia menangkap intipati dengan sempurna.
Walaupun susulan semula jadi kepada artikel terakhir saya tentang Tetingkap Gelongsor ialah corak Dua Penunjuk, kami mengambil sedikit lencongan. kenapa? Kadangkala, menangani konsep yang agak berbeza sebenarnya boleh menjadikan pembelajaran lebih mudah:
1) Ia memberi otak kepelbagaian untuk bekerja.
2) Mari kita hadapi itu, terdapat begitu banyak manipulasi tatasusunan yang boleh kita lakukan sebelum perkara bermula kabur bersama!
Selain itu, rekursi mesti diketahui sebelum menyelam ke dalam pokok binari, jadi artikel ini akan memfokuskan pada itu. Jangan bimbang—corak Dua Penunjuk dan pengenalan pokok akan datang tidak lama lagi. Kami hanya membuat perhentian strategik untuk memastikan keadaan sentiasa segar!
Rekursi 101
Rekursi ialah salah satu konsep yang membina intuisi lebih penting daripada menghafal definisi. Idea utama? Pengulangan dan menjadikan masalah secara progresif lebih mudah.
Jadi, apakah rekursi?
Rekursi ialah tentang mengulangi proses berulang kali pada masalah, tetapi dengan setiap pengulangan, masalah menjadi lebih mudah sehingga anda mencapai titik di mana ia tidak dapat dipermudahkan lagi—ini dipanggil kas asas.
Mari kita pecahkannya dengan beberapa peraturan asas.
Peraturan 1: Masalah mesti semakin kecil
Pada setiap lelaran, masalah harus dikurangkan dari segi saiz atau kerumitan. Bayangkan bermula dengan segi empat sama, dan dengan setiap langkah, anda mengecilkannya.
Nota: Jika, bukannya segi empat sama yang lebih kecil, anda mendapat bentuk rawak, ia bukan lagi proses rekursif, masalah yang lebih mudah ialah versi yang lebih kecil daripada yang lebih besar.
Peraturan 2: Mesti ada kes asas
Satu kes asas ialah versi masalah yang paling mudah dan remeh—titik di mana tiada pengulangan lanjut diperlukan. Tanpa ini, fungsi akan terus memanggil dirinya selama-lamanya, menyebabkan limpahan tindanan.
Contoh: Mengira mundur
Katakan anda mempunyai masalah mudah: mengira detik daripada x kepada 0. Ini bukan masalah dunia sebenar, tetapi ia adalah ilustrasi pengulangan yang baik.
function count(x) { // Base case if (x == 0) { return 0; } // Recursive call: we simplify the problem by reducing x by 1 count(x - 1); // will only run during the bubbling up // the first function call to run is the one before base case backwards // The printing will start from 1.... console.log(x) }
Dalam contoh ini, panggilan count(10) akan mencetuskan satu siri panggilan rekursif, setiap satu memudahkan masalah dengan menolak 1 sehingga mencapai kes asas 0. Setelah kes asas dipukul, fungsi berhenti memanggil dirinya sendiri dan rekursi "berbuih", bermakna setiap panggilan sebelumnya selesai melaksanakan dalam urutan terbalik.
Contoh Pokok Rekursif
Berikut ialah perwakilan ASCII tentang cara panggilan rekursif berfungsi dengan count(3):
count(3) | +-- count(2) | +-- count(1) | +-- count(0) (base case: stop here)
Apa-apa sahaja dipulangkan daripada kiraan(0) akan "bergelembung" sehingga kiraan(1) ... sehingga kiraan 3.
Jadi ia sebatian daripada kes asas yang paling remeh!.
Lebih banyak masalah!
Contoh rekursif
Ingat bahagian intuisi? lebih banyak masalah rekursif yang anda selesaikan lebih baik, ini ialah gambaran keseluruhan cepat masalah rekursif klasik.
Faktorial
Faktorial nombor n ialah hasil darab semua integer positif kurang daripada atau sama dengan n.
const factorialRecursive = num => { if(num === 0) { return 1; } return num * factorialRecursive(num - 1); }
visual
faktorialRekursif(5)
factorialRecursive(5) │ ├── 5 * factorialRecursive(4) │ │ │ ├── 4 * factorialRecursive(3) │ │ │ │ │ ├── 3 * factorialRecursive(2) │ │ │ │ │ │ │ ├── 2 * factorialRecursive(1) │ │ │ │ │ │ │ │ │ ├── 1 * factorialRecursive(0) │ │ │ │ │ │ │ │ │ │ │ └── returns 1 │ │ │ │ └── returns 1 * 1 = 1 │ │ │ └── returns 2 * 1 = 2 │ │ └── returns 3 * 2 = 6 │ └── returns 4 * 6 = 24 └── returns 5 * 24 = 120
Perhatikan bagaimana jawapan yang dikira sebelumnya berbuih, jawapan 2 * factorialRecursive(1) menggelembung menjadi arg untuk 3 * factorialRecursive(2) dan seterusnya... <- kuasai idea ini!
fibonnaci
Fungsi rekursif yang mengembalikan nombor ke-n dalam jujukan Fibonacci, di mana setiap nombor ialah jumlah dua nombor sebelumnya, bermula dari 0 dan 1.
const fibonacci = num => { if (num <= 1) { return num; } return fibonacci(num - 1) + fibonacci(num - 2); }
Visual
fibonacci(4)
fibonacci(4) │ ├── fibonacci(3) │ ├── fibonacci(2) │ │ ├── fibonacci(1) (returns 1) │ │ └── fibonacci(0) (returns 0) │ └── returns 1 + 0 = 1 │ ├── fibonacci(2) │ ├── fibonacci(1) (returns 1) │ └── fibonacci(0) (returns 0) └── returns 1 + 1 = 2 a bit tricky to visualize in ascii (way better in a tree like structure)
Beginilah ia berfungsi:
- fibonacci(4) memanggil fibonacci(3) dan fibonacci(2).
-
fibonacci(3) terbahagi kepada:
- fibonacci(2) → Ini berpecah kepada fibonacci(1) (mengembalikan 1) dan fibonacci(0) (mengembalikan 0). Jumlahnya ialah 1 + 0 = 1.
- fibonacci(1) → Ini mengembalikan 1.
- Jadi, fibonacci(3) mengembalikan 1 (dari fibonacci(2)) + 1 (dari fibonacci(1)) = 2.
-
fibonacci(2) rosak semula:
- fibonacci(1) mengembalikan 1.
- fibonacci(0) mengembalikan 0.
- Jumlahnya ialah 1 + 0 = 1.
- Akhir sekali, fibonacci(4) mengembalikan 2 (dari fibonacci(3)) + 1 (dari fibonacci(2)) = 3.
Cabaran pengoptimuman: Jika anda perasan dalam contoh, fib(2) dikira dua kali jawapan yang sama, bolehkah kita melakukan sesuatu? cache? bayangkan masalah besar dengan pendua!
Sum Array
Write a recursive function to find the sum of all elements in an array.
const sumArray = arr => { if(arr.length == 0){ return 0 } return arr.pop() + sumArray(arr) } <p>visual</p> <p>sumArray([1, 2, 3, 4])<br> </p> <pre class="brush:php;toolbar:false">sumArray([1, 2, 3, 4]) │ ├── 4 + sumArray([1, 2, 3]) │ │ │ ├── 3 + sumArray([1, 2]) │ │ │ │ │ ├── 2 + sumArray([1]) │ │ │ │ │ │ │ ├── 1 + sumArray([]) │ │ │ │ │ │ │ │ │ └── returns 0 │ │ │ └── returns 1 + 0 = 1 │ │ └── returns 2 + 1 = 3 │ └── returns 3 + 3 = 6 └── returns 4 + 6 = 10
This covers the basics, the more problems you solve the better when it comes to recursion.
I am going to leave a few challenges below:
Challenges for Practice
- Check Palindrome: Write a recursive function to check if a given string is a palindrome (reads the same backward as forward).
console.log(isPalindrome("racecar")); // Expected output: true console.log(isPalindrome("hello")); // Expected output: false
- Reverse String: Write a recursive function to reverse a given string.
console.log(reverseString("hello")); // Expected output: "olleh" console.log(reverseString("world")); // Expected output: "dlrow"
- Check Sorted Array: Write a recursive function to check if a given array of numbers is sorted in ascending order.
console.log(isSorted([1, 2, 3, 4])); // Expected output: true console.log(isSorted([1, 3, 2, 4])); // Expected output: false
Recursion is all about practice and building that muscle memory. The more you solve, the more intuitive it becomes. Keep challenging yourself with new problems!
If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!
Atas ialah kandungan terperinci Kit Temuduga: Rekursi.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

Video Face Swap
Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Artikel Panas

Alat panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas











Python lebih sesuai untuk pemula, dengan lengkung pembelajaran yang lancar dan sintaks ringkas; JavaScript sesuai untuk pembangunan front-end, dengan lengkung pembelajaran yang curam dan sintaks yang fleksibel. 1. Sintaks Python adalah intuitif dan sesuai untuk sains data dan pembangunan back-end. 2. JavaScript adalah fleksibel dan digunakan secara meluas dalam pengaturcaraan depan dan pelayan.

Penggunaan utama JavaScript dalam pembangunan web termasuk interaksi klien, pengesahan bentuk dan komunikasi tak segerak. 1) kemas kini kandungan dinamik dan interaksi pengguna melalui operasi DOM; 2) pengesahan pelanggan dijalankan sebelum pengguna mengemukakan data untuk meningkatkan pengalaman pengguna; 3) Komunikasi yang tidak bersesuaian dengan pelayan dicapai melalui teknologi Ajax.

Aplikasi JavaScript di dunia nyata termasuk pembangunan depan dan back-end. 1) Memaparkan aplikasi front-end dengan membina aplikasi senarai TODO, yang melibatkan operasi DOM dan pemprosesan acara. 2) Membina Restfulapi melalui Node.js dan menyatakan untuk menunjukkan aplikasi back-end.

Memahami bagaimana enjin JavaScript berfungsi secara dalaman adalah penting kepada pemaju kerana ia membantu menulis kod yang lebih cekap dan memahami kesesakan prestasi dan strategi pengoptimuman. 1) aliran kerja enjin termasuk tiga peringkat: parsing, penyusun dan pelaksanaan; 2) Semasa proses pelaksanaan, enjin akan melakukan pengoptimuman dinamik, seperti cache dalam talian dan kelas tersembunyi; 3) Amalan terbaik termasuk mengelakkan pembolehubah global, mengoptimumkan gelung, menggunakan const dan membiarkan, dan mengelakkan penggunaan penutupan yang berlebihan.

Python dan JavaScript mempunyai kelebihan dan kekurangan mereka sendiri dari segi komuniti, perpustakaan dan sumber. 1) Komuniti Python mesra dan sesuai untuk pemula, tetapi sumber pembangunan depan tidak kaya dengan JavaScript. 2) Python berkuasa dalam bidang sains data dan perpustakaan pembelajaran mesin, sementara JavaScript lebih baik dalam perpustakaan pembangunan dan kerangka pembangunan depan. 3) Kedua -duanya mempunyai sumber pembelajaran yang kaya, tetapi Python sesuai untuk memulakan dengan dokumen rasmi, sementara JavaScript lebih baik dengan MDNWebDocs. Pilihan harus berdasarkan keperluan projek dan kepentingan peribadi.

Kedua -dua pilihan Python dan JavaScript dalam persekitaran pembangunan adalah penting. 1) Persekitaran pembangunan Python termasuk Pycharm, Jupyternotebook dan Anaconda, yang sesuai untuk sains data dan prototaip cepat. 2) Persekitaran pembangunan JavaScript termasuk node.js, vscode dan webpack, yang sesuai untuk pembangunan front-end dan back-end. Memilih alat yang betul mengikut keperluan projek dapat meningkatkan kecekapan pembangunan dan kadar kejayaan projek.

C dan C memainkan peranan penting dalam enjin JavaScript, terutamanya digunakan untuk melaksanakan jurubahasa dan penyusun JIT. 1) C digunakan untuk menghuraikan kod sumber JavaScript dan menghasilkan pokok sintaks abstrak. 2) C bertanggungjawab untuk menjana dan melaksanakan bytecode. 3) C melaksanakan pengkompil JIT, mengoptimumkan dan menyusun kod hot-spot semasa runtime, dan dengan ketara meningkatkan kecekapan pelaksanaan JavaScript.

Python lebih sesuai untuk sains data dan automasi, manakala JavaScript lebih sesuai untuk pembangunan front-end dan penuh. 1. Python berfungsi dengan baik dalam sains data dan pembelajaran mesin, menggunakan perpustakaan seperti numpy dan panda untuk pemprosesan data dan pemodelan. 2. Python adalah ringkas dan cekap dalam automasi dan skrip. 3. JavaScript sangat diperlukan dalam pembangunan front-end dan digunakan untuk membina laman web dinamik dan aplikasi satu halaman. 4. JavaScript memainkan peranan dalam pembangunan back-end melalui Node.js dan menyokong pembangunan stack penuh.
