cari

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

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...

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 



<p>Visual</p>

<p>fibonacci(4)<br>
</p>

<pre class="brush:php;toolbar:false">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)
}


visual

sumArray([1, 2, 3, 4])

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

  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
  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"
  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

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
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
Memahami Enjin JavaScript: Butiran PelaksanaanMemahami Enjin JavaScript: Butiran PelaksanaanApr 17, 2025 am 12:05 AM

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 vs JavaScript: Keluk Pembelajaran dan Kemudahan PenggunaanPython vs JavaScript: Keluk Pembelajaran dan Kemudahan PenggunaanApr 16, 2025 am 12:12 AM

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.

Python vs JavaScript: Komuniti, Perpustakaan, dan SumberPython vs JavaScript: Komuniti, Perpustakaan, dan SumberApr 15, 2025 am 12:16 AM

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.

Dari C/C ke JavaScript: Bagaimana semuanya berfungsiDari C/C ke JavaScript: Bagaimana semuanya berfungsiApr 14, 2025 am 12:05 AM

Peralihan dari C/C ke JavaScript memerlukan menyesuaikan diri dengan menaip dinamik, pengumpulan sampah dan pengaturcaraan asynchronous. 1) C/C adalah bahasa yang ditaip secara statik yang memerlukan pengurusan memori manual, manakala JavaScript ditaip secara dinamik dan pengumpulan sampah diproses secara automatik. 2) C/C perlu dikumpulkan ke dalam kod mesin, manakala JavaScript adalah bahasa yang ditafsirkan. 3) JavaScript memperkenalkan konsep seperti penutupan, rantaian prototaip dan janji, yang meningkatkan keupayaan pengaturcaraan fleksibiliti dan asynchronous.

Enjin JavaScript: Membandingkan PelaksanaanEnjin JavaScript: Membandingkan PelaksanaanApr 13, 2025 am 12:05 AM

Enjin JavaScript yang berbeza mempunyai kesan yang berbeza apabila menguraikan dan melaksanakan kod JavaScript, kerana prinsip pelaksanaan dan strategi pengoptimuman setiap enjin berbeza. 1. Analisis leksikal: Menukar kod sumber ke dalam unit leksikal. 2. Analisis Tatabahasa: Menjana pokok sintaks abstrak. 3. Pengoptimuman dan Penyusunan: Menjana kod mesin melalui pengkompil JIT. 4. Jalankan: Jalankan kod mesin. Enjin V8 mengoptimumkan melalui kompilasi segera dan kelas tersembunyi, Spidermonkey menggunakan sistem kesimpulan jenis, menghasilkan prestasi prestasi yang berbeza pada kod yang sama.

Beyond the Browser: JavaScript di dunia nyataBeyond the Browser: JavaScript di dunia nyataApr 12, 2025 am 12:06 AM

Aplikasi JavaScript di dunia nyata termasuk pengaturcaraan sisi pelayan, pembangunan aplikasi mudah alih dan Internet of Things Control: 1. Pengaturcaraan sisi pelayan direalisasikan melalui node.js, sesuai untuk pemprosesan permintaan serentak yang tinggi. 2. Pembangunan aplikasi mudah alih dijalankan melalui reaktnatif dan menyokong penggunaan silang platform. 3. Digunakan untuk kawalan peranti IoT melalui Perpustakaan Johnny-Five, sesuai untuk interaksi perkakasan.

Membina aplikasi SaaS Multi-penyewa dengan Next.js (Integrasi Backend)Membina aplikasi SaaS Multi-penyewa dengan Next.js (Integrasi Backend)Apr 11, 2025 am 08:23 AM

Saya membina aplikasi SaaS multi-penyewa berfungsi (aplikasi edTech) dengan alat teknologi harian anda dan anda boleh melakukan perkara yang sama. Pertama, apakah aplikasi SaaS multi-penyewa? Aplikasi SaaS Multi-penyewa membolehkan anda melayani beberapa pelanggan dari Sing

Cara Membina Aplikasi SaaS Multi-Tenant dengan Next.js (Integrasi Frontend)Cara Membina Aplikasi SaaS Multi-Tenant dengan Next.js (Integrasi Frontend)Apr 11, 2025 am 08:22 AM

Artikel ini menunjukkan integrasi frontend dengan backend yang dijamin oleh permit, membina aplikasi edtech SaaS yang berfungsi menggunakan Next.Js. Frontend mengambil kebenaran pengguna untuk mengawal penglihatan UI dan memastikan permintaan API mematuhi dasar peranan

See all articles

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

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
1 bulan yang laluBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Tetapan grafik terbaik
1 bulan yang laluBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Cara Memperbaiki Audio Jika anda tidak dapat mendengar sesiapa
1 bulan yang laluBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Arahan sembang dan cara menggunakannya
1 bulan yang laluBy尊渡假赌尊渡假赌尊渡假赌

Alat panas

Penyesuai Pelayan SAP NetWeaver untuk Eclipse

Penyesuai Pelayan SAP NetWeaver untuk Eclipse

Integrasikan Eclipse dengan pelayan aplikasi SAP NetWeaver.

Pelayar Peperiksaan Selamat

Pelayar Peperiksaan Selamat

Pelayar Peperiksaan Selamat ialah persekitaran pelayar selamat untuk mengambil peperiksaan dalam talian dengan selamat. Perisian ini menukar mana-mana komputer menjadi stesen kerja yang selamat. Ia mengawal akses kepada mana-mana utiliti dan menghalang pelajar daripada menggunakan sumber yang tidak dibenarkan.

Muat turun versi mac editor Atom

Muat turun versi mac editor Atom

Editor sumber terbuka yang paling popular

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

Dreamweaver Mac版

Dreamweaver Mac版

Alat pembangunan web visual