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
Ganti aksara rentetan dalam javascriptGanti aksara rentetan dalam javascriptMar 11, 2025 am 12:07 AM

Penjelasan terperinci mengenai kaedah penggantian rentetan javascript dan Soalan Lazim Artikel ini akan meneroka dua cara untuk menggantikan watak rentetan dalam JavaScript: Kod JavaScript dalaman dan HTML dalaman untuk laman web. Ganti rentetan di dalam kod JavaScript Cara yang paling langsung ialah menggunakan kaedah pengganti (): str = str.replace ("cari", "ganti"); Kaedah ini hanya menggantikan perlawanan pertama. Untuk menggantikan semua perlawanan, gunakan ungkapan biasa dan tambahkan bendera global g: str = str.replace (/fi

Tutorial Persediaan API Carian Google CustomTutorial Persediaan API Carian Google CustomMar 04, 2025 am 01:06 AM

Tutorial ini menunjukkan kepada anda bagaimana untuk mengintegrasikan API carian Google tersuai ke dalam blog atau laman web anda, menawarkan pengalaman carian yang lebih halus daripada fungsi carian tema WordPress standard. Ia menghairankan mudah! Anda akan dapat menyekat carian ke y

Bina Aplikasi Web Ajax anda sendiriBina Aplikasi Web Ajax anda sendiriMar 09, 2025 am 12:11 AM

Jadi di sini anda, bersedia untuk mempelajari semua perkara ini yang dipanggil Ajax. Tetapi, apa sebenarnya? Istilah Ajax merujuk kepada kumpulan teknologi longgar yang digunakan untuk membuat kandungan web yang dinamik dan interaktif. Istilah Ajax, yang asalnya dicipta oleh Jesse J

Contoh warna json failContoh warna json failMar 03, 2025 am 12:35 AM

Siri artikel ini ditulis semula pada pertengahan 2017 dengan maklumat terkini dan contoh segar. Dalam contoh JSON ini, kita akan melihat bagaimana kita dapat menyimpan nilai mudah dalam fail menggunakan format JSON. Menggunakan notasi pasangan nilai utama, kami boleh menyimpan apa-apa jenis

10 JQuery Syntax Highlighters10 JQuery Syntax HighlightersMar 02, 2025 am 12:32 AM

Tingkatkan Penyampaian Kod Anda: 10 Penyeret Sintaks untuk Pemaju Coretan kod perkongsian di laman web atau blog anda adalah amalan biasa bagi pemaju. Memilih penyapu sintaks yang betul dapat meningkatkan daya tarikan dan daya tarikan visual dengan ketara. T

8 plugin susun atur halaman jquery yang menakjubkan8 plugin susun atur halaman jquery yang menakjubkanMar 06, 2025 am 12:48 AM

Leverage JQuery untuk Layouts Laman Web yang mudah: 8 Plugin Essential JQuery memudahkan susun atur laman web dengan ketara. Artikel ini menyoroti lapan plugin jQuery yang kuat yang menyelaraskan proses, terutamanya berguna untuk penciptaan laman web manual

10 JavaScript & JQuery MVC Tutorial10 JavaScript & JQuery MVC TutorialMar 02, 2025 am 01:16 AM

Artikel ini membentangkan pemilihan lebih daripada 10 tutorial mengenai rangka kerja javascript dan jquery model-view-controller (MVC), sesuai untuk meningkatkan kemahiran pembangunan web anda pada tahun baru. Tutorial ini merangkumi pelbagai topik, dari Foundatio

Apa itu ' ini ' Dalam JavaScript?Apa itu ' ini ' Dalam JavaScript?Mar 04, 2025 am 01:15 AM

Mata teras Ini dalam JavaScript biasanya merujuk kepada objek yang "memiliki" kaedah, tetapi ia bergantung kepada bagaimana fungsi dipanggil. Apabila tidak ada objek semasa, ini merujuk kepada objek global. Dalam penyemak imbas web, ia diwakili oleh tetingkap. Apabila memanggil fungsi, ini mengekalkan objek global; tetapi apabila memanggil pembina objek atau mana -mana kaedahnya, ini merujuk kepada contoh objek. Anda boleh mengubah konteks ini menggunakan kaedah seperti panggilan (), memohon (), dan mengikat (). Kaedah ini memanggil fungsi menggunakan nilai dan parameter yang diberikan. JavaScript adalah bahasa pengaturcaraan yang sangat baik. Beberapa tahun yang lalu, ayat ini

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.

Alat panas

MantisBT

MantisBT

Mantis ialah alat pengesan kecacatan berasaskan web yang mudah digunakan yang direka untuk membantu dalam pengesanan kecacatan produk. Ia memerlukan PHP, MySQL dan pelayan web. Lihat perkhidmatan demo dan pengehosan kami.

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

mPDF

mPDF

mPDF ialah perpustakaan PHP yang boleh menjana fail PDF daripada HTML yang dikodkan UTF-8. Pengarang asal, Ian Back, menulis mPDF untuk mengeluarkan fail PDF "dengan cepat" dari tapak webnya dan mengendalikan bahasa yang berbeza. Ia lebih perlahan dan menghasilkan fail yang lebih besar apabila menggunakan fon Unicode daripada skrip asal seperti HTML2FPDF, tetapi menyokong gaya CSS dsb. dan mempunyai banyak peningkatan. Menyokong hampir semua bahasa, termasuk RTL (Arab dan Ibrani) dan CJK (Cina, Jepun dan Korea). Menyokong elemen peringkat blok bersarang (seperti P, DIV),

DVWA

DVWA

Damn Vulnerable Web App (DVWA) ialah aplikasi web PHP/MySQL yang sangat terdedah. Matlamat utamanya adalah untuk menjadi bantuan bagi profesional keselamatan untuk menguji kemahiran dan alatan mereka dalam persekitaran undang-undang, untuk membantu pembangun web lebih memahami proses mengamankan aplikasi web, dan untuk membantu guru/pelajar mengajar/belajar dalam persekitaran bilik darjah Aplikasi web keselamatan. Matlamat DVWA adalah untuk mempraktikkan beberapa kelemahan web yang paling biasa melalui antara muka yang mudah dan mudah, dengan pelbagai tahap kesukaran. Sila ambil perhatian bahawa perisian ini