Rumah hujung hadapan web tutorial js Kit Temuduga: Rekursi.

Kit Temuduga: Rekursi.

Sep 05, 2024 pm 05:32 PM

Interview Kit: Recursion.

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)
}
Salin selepas log masuk

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)
Salin selepas log masuk

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


Salin selepas log masuk

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

Salin selepas log masuk

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

Salin selepas log masuk

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)
Salin selepas log masuk

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

Salin selepas log masuk

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

  1. 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
Salin selepas log masuk
  1. 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"
Salin selepas log masuk
  1. 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
Salin selepas log masuk

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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

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

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Apa yang perlu saya lakukan jika saya menghadapi percetakan kod yang dihiasi untuk resit kertas terma depan? Apa yang perlu saya lakukan jika saya menghadapi percetakan kod yang dihiasi untuk resit kertas terma depan? Apr 04, 2025 pm 02:42 PM

Soalan dan penyelesaian yang sering ditanya untuk percetakan tiket kertas terma depan dalam pembangunan front-end, percetakan tiket adalah keperluan umum. Walau bagaimanapun, banyak pemaju sedang melaksanakan ...

Demystifying JavaScript: Apa yang berlaku dan mengapa penting Demystifying JavaScript: Apa yang berlaku dan mengapa penting Apr 09, 2025 am 12:07 AM

JavaScript adalah asas kepada pembangunan web moden, dan fungsi utamanya termasuk pengaturcaraan yang didorong oleh peristiwa, penjanaan kandungan dinamik dan pengaturcaraan tak segerak. 1) Pengaturcaraan yang didorong oleh peristiwa membolehkan laman web berubah secara dinamik mengikut operasi pengguna. 2) Penjanaan kandungan dinamik membolehkan kandungan halaman diselaraskan mengikut syarat. 3) Pengaturcaraan Asynchronous memastikan bahawa antara muka pengguna tidak disekat. JavaScript digunakan secara meluas dalam interaksi web, aplikasi satu halaman dan pembangunan sisi pelayan, sangat meningkatkan fleksibiliti pengalaman pengguna dan pembangunan silang platform.

Siapa yang dibayar lebih banyak Python atau JavaScript? Siapa yang dibayar lebih banyak Python atau JavaScript? Apr 04, 2025 am 12:09 AM

Tidak ada gaji mutlak untuk pemaju Python dan JavaScript, bergantung kepada kemahiran dan keperluan industri. 1. Python boleh dibayar lebih banyak dalam sains data dan pembelajaran mesin. 2. JavaScript mempunyai permintaan yang besar dalam perkembangan depan dan stack penuh, dan gajinya juga cukup besar. 3. Faktor mempengaruhi termasuk pengalaman, lokasi geografi, saiz syarikat dan kemahiran khusus.

Adakah JavaScript sukar belajar? Adakah JavaScript sukar belajar? Apr 03, 2025 am 12:20 AM

Pembelajaran JavaScript tidak sukar, tetapi ia mencabar. 1) Memahami konsep asas seperti pembolehubah, jenis data, fungsi, dan sebagainya. 2) Pengaturcaraan asynchronous tuan dan melaksanakannya melalui gelung acara. 3) Gunakan operasi DOM dan berjanji untuk mengendalikan permintaan tak segerak. 4) Elakkan kesilapan biasa dan gunakan teknik debugging. 5) Mengoptimumkan prestasi dan mengikuti amalan terbaik.

Bagaimana untuk mencapai kesan menatal paralaks dan kesan animasi elemen, seperti laman web rasmi Shiseido?
atau:
Bagaimanakah kita dapat mencapai kesan animasi yang disertai dengan menatal halaman seperti laman web rasmi Shiseido? Bagaimana untuk mencapai kesan menatal paralaks dan kesan animasi elemen, seperti laman web rasmi Shiseido? atau: Bagaimanakah kita dapat mencapai kesan animasi yang disertai dengan menatal halaman seperti laman web rasmi Shiseido? Apr 04, 2025 pm 05:36 PM

Perbincangan mengenai realisasi kesan animasi tatal dan elemen Parallax dalam artikel ini akan meneroka bagaimana untuk mencapai yang serupa dengan laman web rasmi Shiseido (https://www.shiseido.co.jp/sb/wonderland/) ... ...

Evolusi JavaScript: Trend Semasa dan Prospek Masa Depan Evolusi JavaScript: Trend Semasa dan Prospek Masa Depan Apr 10, 2025 am 09:33 AM

Trend terkini dalam JavaScript termasuk kebangkitan TypeScript, populariti kerangka dan perpustakaan moden, dan penerapan webassembly. Prospek masa depan meliputi sistem jenis yang lebih berkuasa, pembangunan JavaScript, pengembangan kecerdasan buatan dan pembelajaran mesin, dan potensi pengkomputeran IoT dan kelebihan.

Bagaimana untuk menggabungkan elemen array dengan ID yang sama ke dalam satu objek menggunakan JavaScript? Bagaimana untuk menggabungkan elemen array dengan ID yang sama ke dalam satu objek menggunakan JavaScript? Apr 04, 2025 pm 05:09 PM

Bagaimana cara menggabungkan elemen array dengan ID yang sama ke dalam satu objek dalam JavaScript? Semasa memproses data, kita sering menghadapi keperluan untuk mempunyai id yang sama ...

Perbezaan dalam Konsol.Log Output Result: Mengapa kedua -dua panggilan berbeza? Perbezaan dalam Konsol.Log Output Result: Mengapa kedua -dua panggilan berbeza? Apr 04, 2025 pm 05:12 PM

Perbincangan mendalam mengenai punca-punca utama perbezaan dalam output konsol.log. Artikel ini akan menganalisis perbezaan hasil output fungsi Console.log dalam sekeping kod dan menerangkan sebab -sebab di belakangnya. � ...

See all articles