Rekursi - apakah itu "membagi dan menaklukkan" atau "menggunakan kembali kode"

Rekursi - seperti yang kita semua tahu - adalah salah satu masalah itu - yang membungkus kepala Anda terasa seperti mencapai "tonggak" dalam perjalanan pemrograman Anda.

Tetapi ketika benar-benar menggunakannya dalam masalah dunia nyata - mengetahui mekanisme rekursi TIDAK cukup - kita juga harus memahami sifat masalah di mana rekursi adalah solusi yang paling cocok.

Jadi pertanyaan saya adalah ini ...

• apa "pola masalah" yang membutuhkan solusi rekursi
• adalah rekursi bentuk strategi "divide & conquer" atau bentuk "code reuse" - atau, adalah pola desain dengan haknya sendiri
• dapatkah Anda memberi kami contoh masalah dunia nyata di mana rekursi datang ke pikiran sebagai solusi langsung

- PEMBARUAN -

banyak jawaban mengacu pada "masalah nyata" sebagai melintasi pohon, faktorial, dll. Saya lebih suka "masalah nyata NYATA" - izinkan saya memberi Anda sebuah contoh ...

Kami memiliki potongan teks BESAR (sekitar 30 MB teks sebagai daftar tertaut structs), dan kami perlu membuat indeksnya untuk pencarian teks lengkap. Kami perlu menyimpan seluruh indeks dalam memori dan mengindeks ulang teks setiap 10 menit.

Setiap 10 menit kami membandingkan seluruh teks (dua daftar yang ditautkan, baris demi baris) dengan potongan teks yang baru dibuat - untuk melihat baris mana yang diubah - dan kemudian kami akan mengindeks ulang hanya baris itu - dengan cara itu kami dapat menghindari pengindeksan ulang teks SELURUH. Ingat - kami perlu menemukan titik perbedaan antara dua daftar yang terhubung 30 MB.

Salah satu kolega saya datang dengan program fantastis yang menggunakan rekursi HEAVY untuk membandingkan garis - dan kemudian mengumpulkan posisi di mana chuck berbeda dalam array - ya saya tahu itu terdengar membingungkan - bagaimana rekursi dapat membantu di sini - tetapi itu benar.

Intinya adalah - bagaimana dia bisa melihat bahwa masalah ini dapat diselesaikan dengan cerdas dengan menggunakan rekursi yang berat?

• apa "pola masalah" yang membutuhkan solusi rekursi

Saya tidak akan mengatakan ada yang namanya pola masalah untuk penggunaan rekursi. Setiap fungsi yang dapat diimplementasikan dengan rekursi juga dapat diimplementasikan secara iteratif, seringkali dengan mendorong dan membuka tumpukan.

Ini masalah ekspresi dan juga kinerja. Algoritma berulang sering kali memiliki kinerja yang lebih baik dan lebih mudah untuk dioptimalkan. Namun, algoritma rekursif mendapat manfaat dari ekspresi yang lebih jelas sehingga seringkali lebih mudah dibaca, dipahami, dan diimplementasikan.

Beberapa hal bahkan tidak dapat diungkapkan tanpa rekursi, daftar yang tak terbatas misalnya. Apa yang disebut bahasa fungsional sangat bergantung pada rekursi, karena itu adalah cara berekspresi alami mereka. Pepatahnya adalah: "Pemrograman rekursif adalah pemrograman fungsional yang dilakukan dengan benar".

• adalah rekursi bentuk strategi "divide & conquer" atau bentuk "code reuse" - atau, adalah pola desain dengan haknya sendiri

Saya tidak akan menyebutnya pola desain. Ini masalah ekspresi. Kadang-kadang ekspresi rekursif hanya lebih kuat dan lebih ekspresif dan dengan demikian mengarah pada kode yang lebih baik dan lebih bersih.

• dapatkah Anda memberi kami contoh masalah dunia nyata di mana rekursi datang ke pikiran sebagai solusi langsung

Apa pun yang perlu melintasi pohon akan diekspresikan dengan baik oleh algoritma rekursif.

adalah rekursi bentuk strategi "divide & conquer" atau bentuk "code reuse" - atau, adalah pola desain dengan haknya sendiri

Tidak juga. Membagi & taklukkan menggunakan rekursi. Tetapi rekursi tidak harus memecah belah & menaklukkan karena yang terakhir berarti membagi masalah menjadi dua (atau lebih) bagian dan menyelesaikan masing-masing secara simetris. Dalam rekursi, Anda tidak melakukan ini.

Penggunaan kembali kode sama sekali tidak terkait, dan pola desain ikut bermain di tingkat yang jauh lebih tinggi. Misalnya, bahkan membagi & menaklukkan (juga pola tingkat lebih tinggi dari rekursi) masih tidak dianggap sebagai pola desain - melainkan pola algoritmik .

dapatkah Anda memberi kami contoh masalah dunia nyata di mana rekursi datang ke pikiran sebagai solusi langsung

Traversal pohon. Atau lebih umum grafik traversal. Ini termasuk melintasi struktur folder.

Dan tentu saja apa pun yang menggunakan pemrograman divide & conquer atau dinamis karena keduanya secara alami dinyatakan dalam istilah rekursi.

what are the "problem patterns" that call for the solution of recursion

Berasal dari kesamaan diri fraktal, saya akan mengatakan bahwa kesetaraan diri atau identitas diri (atau bagaimanapun disebut) adalah pola masalah khas untuk rekursi. Yaitu masalah dapat dipecah menjadi sub-masalah yang memiliki struktur yang sama dengan masalah utama.

Dalam traversal pohon yang disebutkan, masing-masing sub-pohon itu sendiri merupakan pohon penuh, sama seperti pohon utama, dan pohon utama dapat menjadi sub-pohon di dalam pohon lain.

Jadi saya kira kolega Anda menemukan sifat kesetaraan diri dari masalah pengindeksan Anda. Atau dia pergi sebaliknya dan mengubah masalah menjadi representasi yang setara.

Nah, rekursi dapat dipahami dengan mudah jika seseorang akan mencoba mengubah loop imperatif menjadi fungsi fungsional. Bagaimanapun, mari kita coba memberikan jawaban untuk semua pertanyaan:

apa "pola masalah" yang membutuhkan solusi rekursi

Jika Anda memiliki struktur atau algoritma seperti pohon, Anda perlu rekursi. Jika kode imperatif Anda berurusan dengan stack, Anda perlu rekursi. Jika langkah tertentu dalam algoritme Anda bergantung pada langkah sebelumnya (pikirkan loop), Anda perlu rekursi. Perlu di sini adalah untuk diartikan sebagai dapat digunakan.

adalah rekursi bentuk strategi "divide & conquer" atau bentuk "code reuse" - atau, adalah pola desain dengan haknya sendiri

Tidak ada Membagi dan menaklukkan menggunakan rekursi tetapi dapat diimplementasikan dengan tumpukan. Penggunaan kembali kode mengacu pada sesuatu yang lain. Pola desain lebih rumit daripada rekursi sederhana.

dapatkah Anda memberi kami contoh masalah dunia nyata di mana rekursi datang ke pikiran sebagai solusi langsung

Parsing dan segala sesuatu yang berhubungan dengan struktur pohon. Bahkan struktur pohon implisit.

Jika ada cara untuk menyederhanakannya sehingga mudah, itu bisa menjadi petunjuk bahwa rekursi bisa bekerja. Anda dapat mengambil pengurutan dan mencari contoh di mana ada solusi rekursif seperti Gabung Sort dan Binary Search masing-masing.

Yang perlu diingat adalah bagaimana beberapa masalah dapat diselesaikan dengan buruk dengan rekursi seperti faktorial.

Adapun contoh dunia nyata di mana saya akan menggunakan rekursi, mencari buku dari rak buku bisa dilakukan dengan mudah secara rekursif. Saya hanya melihat buku itu dan jika bukan itu yang saya inginkan, saya beralih ke buku berikutnya. Saya berhenti ketika saya menemukan buku itu atau mencapai ujung baris. Pengulangan memeriksa buku dan beralih ke yang berikutnya dapat dilakukan secara rekursif. Mungkin ini contoh yang terlalu nyata.

apa "pola masalah" yang membutuhkan solusi rekursi

Dalam istilah yang sangat umum, rekursi diperlukan ketika Anda memecahkan masalah di mana f (x) = f (g (x)) . Kecuali jika Anda baik-baik saja dengan rekursi tak terbatas, g (x) tidak seharusnya mengevaluasi ke x .

adalah rekursi bentuk strategi "divide & conquer" atau bentuk "code reuse" - atau, adalah pola desain dengan haknya sendiri

Bukan dari salah satu di atas. Ini hanya cara untuk melakukan hal yang sama berulang kali, terkadang berdasarkan variasi pada input. Konsep ini telah ada jauh lebih lama daripada pola desain, penggunaan kembali kode atau bahkan komputer, dalam hal ini.

dapatkah Anda memberi kami contoh masalah dunia nyata di mana rekursi datang ke pikiran sebagai solusi langsung

Faktorial, urutan Fibonacci, traversal pohon, dan banyak masalah lain dapat diselesaikan dengan recusrion. Rekursi dalam arti fungsi yang memanggil dirinya sendiri belum tentu cara terbaik untuk mengimplementasikan hal-hal semacam itu; ada cara lain untuk mencapai efek yang sama (misalnya, tumpukan dan putaran) yang mungkin lebih diinginkan.

Saat Anda menulis algoritma rekursif, Anda biasanya menerjemahkan definisi rekursif masalah ke kode. Maka Anda bahkan tidak perlu tahu bagaimana itu akan dieksekusi.

Itulah yang terjadi dalam pemrograman fungsional. Bahkan, Anda menentukan apa (definisi) daripada bagaimana . Dengan kata lain, Anda mendefinisikan basis dan kemudian mendefinisikan masalah Anda dalam istilah sub-masalah.

Misalnya perhatikan Factorialalgoritma

• Definisikan basis: Factorial (1) = 1;
• Define Factorial n: Factorial (n) = n * Factorial (n-1);

Kemudian ketika Anda menghadapi masalah, Anda harus berpikir apakah Anda dapat mendefinisikannya secara rekursif atau tidak, jika Anda dapat mendefinisikannya secara rekursif, Anda hampir telah menyelesaikannya.

Namun, fungsi rekursif apa pun seharusnya tidak menjadi definisi rekursif. Anda dapat mendefinisikan basis dan menghubungkan (mendefinisikan) solusi dari masalah utama ke solusi (definisi) dari sub-masalah. Tetapi untuk hubungan ini Anda mungkin perlu prosedur.

Contohnya adalah MergeSortdi mana mergebisa menjadi prosedur penting untuk menghubungkan definisi atau solusi penyortiran seluruh array dengan jenis sub-array.