Pemahaman modern tentang rekursi: definisi fungsionalitas dan aksesnya dari luar dan dari fungsi ini. Diyakini bahwa rekursi dilahirkan oleh ahli matematika: perhitungan faktorial, deret tak hingga, fraktal, pecahan lanjutan … Namun, rekursi dapat ditemukan di mana-mana. Hukum alam objektif "menganggap" rekursi sebagai algoritma utama mereka dan bentuk ekspresi (eksistensi) tidak begitu banyak dari objek dunia material, tetapi secara umum algoritma utama gerakan.
Orang-orang dari berbagai spesialisasi di berbagai bidang ilmu pengetahuan dan teknologi menggunakan algoritma rekursif f (x), di mana "x ~/=f (x)". Sebuah fungsi yang memanggil dirinya sendiri adalah solusi yang kuat, tetapi membentuk dan memahami solusi ini, dalam banyak kasus, merupakan tugas yang sangat sulit.
Pada zaman kuno, rekursi digunakan untuk menambah ruang istana. Melalui sistem cermin yang diarahkan satu sama lain, Anda dapat menciptakan efek spasial tiga dimensi yang menakjubkan. Tetapi apakah begitu mudah untuk memahami caranyamenyesuaikan cermin ini? Bahkan lebih sulit untuk menentukan di mana sebuah titik dalam ruang, dipantulkan melalui beberapa cermin.
Rekursi, algoritma rekursif: makna dan sintaks
Masalah yang dirumuskan dengan mengulangi urutan operasi, dapat diselesaikan secara rekursif. Algoritma sederhana (menghitung persamaan kuadrat, skrip untuk mengisi halaman web dengan informasi, membaca file, mengirim pesan…) tidak memerlukan rekursi.
Perbedaan utama dari algoritma yang memungkinkan solusi rekursif:
- ada algoritma yang perlu dieksekusi beberapa kali;
- algoritma membutuhkan data yang berubah setiap saat;
- algoritma tidak harus berubah setiap saat;
- ada kondisi akhir: algoritmanya rekursif - tidak terbatas.
Secara umum, tidak dapat dikatakan bahwa eksekusi satu kali adalah kondisi yang diperlukan untuk tidak adanya alasan untuk rekursi. Anda juga tidak dapat meminta kondisi akhir wajib: rekursi tak terbatas memiliki cakupannya sendiri.
Algoritme ini rekursif: ketika urutan operasi dilakukan berulang kali, pada data yang berubah setiap kali dan memberikan hasil baru setiap kali.
Rumus rekursi
Pemahaman matematis rekursi dan analognya dalam pemrograman berbeda. Matematika, meskipun ada tanda-tanda pemrograman, tetapi pemrograman adalah matematika dengan urutan yang jauh lebih tinggi.
Algoritme yang ditulis dengan baik adalah seperti cermin kecerdasan penulisnya. Umumrumus rekursi dalam pemrograman adalah "f(x)", di mana "x ~/=f(x)" memiliki setidaknya dua interpretasi. Di sini "~" adalah kesamaan atau ketidakhadiran hasil, dan "=" adalah keberadaan hasil fungsi.
Opsi pertama: dinamika data.
- function "f(x)" memiliki algoritma rekursif dan tidak dapat diubah;
- "x" dan hasil "f(x)" memiliki nilai baru setiap kali, hasil "f(x)" adalah parameter "x" baru dari fungsi ini.
Opsi kedua: dinamika kode.
- function "f(x)" memiliki beberapa algoritma yang menyaring (menganalisis) data;
- analisis data - satu bagian dari kode dan implementasi algoritma rekursif yang melakukan tindakan yang diinginkan - bagian kedua dari kode;
- hasil dari fungsi "f(x)" bukan.
Tidak ada hasil yang normal. Pemrograman bukan matematika, di sini hasilnya tidak harus secara eksplisit hadir. Fungsi rekursif dapat dengan mudah mengurai situs dan mengisi database, atau membuat instance objek sesuai dengan input yang masuk.
Data dan rekursi
Pemrograman algoritma rekursif bukan tentang menghitung faktorial, di mana fungsi menerima setiap kali nilai yang diberikan satu lebih atau kurang dari satu - opsi implementasi tergantung pada preferensi pengembang.
Tidak masalah seberapa faktorial "8!",algoritma yang secara ketat mengikuti rumus ini.
Memproses informasi adalah "matematika" dengan urutan yang sama sekali berbeda. Fungsi dan algoritma rekursif di sini beroperasi pada huruf, kata, frasa, kalimat, dan paragraf. Setiap level berikutnya menggunakan level sebelumnya.
Aliran data masukan dianalisis pada berbagai kondisi, tetapi proses analisis umumnya rekursif. Tidak masuk akal untuk menulis algoritme unik untuk semua varian aliran input. Seharusnya ada satu fungsi. Di sini, algoritma rekursif adalah contoh bagaimana membentuk aliran output yang memadai untuk input. Ini bukan output dari algoritma rekursif, tetapi ini adalah solusi yang diinginkan dan diperlukan.
Abstraksi, rekursi, dan OOP
Pemrograman berorientasi objek (OOP) dan rekursi pada dasarnya adalah entitas yang berbeda, tetapi keduanya saling melengkapi dengan sempurna. Abstraksi tidak ada hubungannya dengan rekursi, tetapi melalui lensa OOP ini menciptakan kemungkinan untuk mengimplementasikan rekursi kontekstual.
Misalnya, informasi sedang diuraikan dan huruf, kata, frasa, kalimat, dan paragraf disorot secara terpisah. Jelas, pengembang akan menyediakan pembuatan instance objek dari lima jenis ini dan menawarkan solusi algoritma rekursif di setiap level.
Sementara, jika pada tataran huruf “tidak ada gunanya mencari makna”, maka semantik muncul pada tataran kata. Anda dapat membagi kata menjadi kata kerja, kata benda, kata keterangan, kata depan… Anda dapat melangkah lebih jauh dan mendefinisikan kasus.
Pada tingkat frase, semantik dilengkapi dengan tanda baca dan logikakombinasi kata. Pada tataran kalimat ditemukan tataran semantik yang lebih sempurna, dan sebuah paragraf dapat dikatakan sebagai suatu pemikiran yang utuh.
Pengembangan berorientasi objek menentukan sebelumnya pewarisan properti dan metode dan mengusulkan untuk memulai hierarki objek dengan pembuatan leluhur yang sepenuhnya abstrak. Pada saat yang sama, tidak diragukan lagi, analisis setiap turunan akan berulang dan tidak akan terlalu berbeda pada tingkat teknis di banyak posisi (huruf, kata, frasa, dan kalimat). Paragraf, seperti pemikiran yang lengkap, mungkin menonjol dari daftar ini, tetapi itu bukan intinya.
Penting bahwa bagian besar dari algoritme dapat dirumuskan pada tingkat leluhur abstrak, menyempurnakannya pada tingkat setiap turunan dengan data dan metode yang dipanggil dari tingkat abstrak. Dalam konteks ini, abstraksi membuka cakrawala baru untuk rekursi.
Fitur historis OOP
OOP telah datang ke dunia perangkat lunak dua kali, meskipun beberapa ahli mungkin memilih munculnya komputasi awan dan ide-ide modern tentang objek dan kelas sebagai babak baru dalam pengembangan teknologi TI.
Istilah "objek" dan "tujuan" dalam konteks modern OOP biasanya dikaitkan dengan 50-an dan 60-an abad terakhir, tetapi mereka terkait dengan 1965 dan munculnya Simula, Lisp, Algol, Smalltalk.
Pada masa itu, pemrograman tidak dikembangkan secara khusus dan tidak dapat secara memadai menanggapi konsep-konsep revolusioner. Perjuangan ide dan gaya pemrograman (C / C ++ dan Pascal - kebanyakan) masih jauh, dan basis data masih terbentuk secara konseptual.
Pada akhir 80-an dan awal 90-an, objek muncul di Pascal dan semua orang mengingat kelas dalam C / C ++ - ini menandai babak baru minat OOP dan saat itulah alat, terutama bahasa pemrograman, menjadi tidak hanya mendukung ide berorientasi objek, tetapi berkembang sesuai dengan itu.
Tentu saja, jika algoritma rekursif sebelumnya hanya fungsi yang digunakan dalam kode umum program, sekarang rekursi dapat menjadi bagian dari properti objek (kelas), yang memberikan peluang menarik dalam konteks pewarisan.
Fitur OOP modern
Pengembangan OOP awalnya mendeklarasikan objek (kelas) sebagai kumpulan data dan properti (metode). Padahal, itu tentang data yang memiliki sintaks dan makna. Tapi kemudian tidak mungkin menghadirkan OOP sebagai alat untuk mengelola objek nyata.
OOP telah menjadi alat untuk mengelola objek "sifat komputer". Skrip, tombol, item menu, bilah menu, tag di jendela browser adalah objek. Tapi bukan mesin, produk makanan, kata, atau kalimat. Objek nyata tetap berada di luar pemrograman berorientasi objek, dan alat komputer telah mengambil inkarnasi baru.
Karena perbedaan bahasa pemrograman populer, banyak dialek OOP telah muncul. Dalam hal semantik, mereka secara praktis setara, dan fokus mereka pada bidang instrumental, dan bukan pada yang diterapkan, memungkinkan untuk mengambil deskripsi objek nyata di luar.algoritma dan memastikan "keberadaan" lintas platform dan lintas bahasa mereka.
Tumpukan dan mekanisme panggilan fungsi
Mekanisme pemanggilan fungsi (prosedur, algoritme) memerlukan data (parameter), mengembalikan hasil, dan mengingat alamat operator yang harus menerima kontrol setelah fungsi (prosedur) selesai.
Biasanya, tumpukan digunakan untuk tujuan ini, meskipun bahasa pemrograman atau pengembang sendiri dapat menyediakan berbagai opsi untuk mentransfer kontrol. Pemrograman modern mengakui bahwa nama suatu fungsi tidak hanya dapat menjadi parameter: ia dapat dibentuk selama eksekusi algoritme. Sebuah algoritme juga dapat dibuat saat menjalankan algoritme lain.
Konsep algoritma rekursif, ketika nama dan badan mereka dapat ditentukan pada saat pembentukan tugas (memilih algoritma yang diinginkan), memperluas rekursi tidak hanya untuk bagaimana melakukan sesuatu, tetapi juga siapa yang sebenarnya harus lakukan. Memilih algoritme dengan nama yang "bermakna" memang menjanjikan, tetapi menimbulkan kesulitan.
Rekursif pada sekumpulan fungsi
Anda tidak dapat mengatakan bahwa suatu algoritme rekursif ketika ia memanggil dirinya sendiri dan hanya itu. Pemrograman bukanlah sebuah dogma, dan konsep rekursif bukanlah persyaratan eksklusif untuk memanggil diri Anda sendiri dari badan algoritme Anda sendiri.
Aplikasi praktis tidak selalu memberikan solusi yang bersih. Seringkali, data awal harus disiapkan, dan hasil dari panggilan rekursif harus dianalisis dalam konteks seluruh masalah (seluruh algoritma) dikeseluruhan.
Faktanya, tidak hanya sebelum fungsi rekursif dipanggil, tetapi juga setelah selesai, program lain dapat atau harus dipanggil. Jika tidak ada masalah khusus dengan panggilan: fungsi rekursif A() memanggil fungsi B(), yang melakukan sesuatu dan memanggil A(), maka segera ada masalah dengan kembalinya kontrol. Setelah menyelesaikan panggilan rekursif, fungsi A() harus menerima kontrol untuk memanggil kembali B(), yang akan memanggilnya lagi. Mengembalikan kontrol sebagaimana mestinya di tumpukan kembali ke B() adalah solusi yang salah.
Pemrogram tidak terbatas dalam memilih parameter dan dapat melengkapinya dengan nama fungsi. Dengan kata lain, solusi ideal adalah meneruskan nama B() ke A() dan membiarkan A() sendiri memanggil B(). Dalam hal ini, tidak akan ada masalah dengan kontrol kembali, dan implementasi algoritma rekursif akan lebih transparan.
Memahami dan tingkat rekursi
Masalah dalam mengembangkan algoritme rekursif adalah Anda perlu memahami dinamika proses. Saat menggunakan rekursi dalam metode objek, terutama pada tingkat leluhur abstrak, ada masalah dalam memahami algoritme Anda sendiri dalam konteks waktu eksekusinya.
Saat ini, tidak ada batasan pada tingkat fungsi dan kapasitas tumpukan dalam mekanisme panggilan, tetapi ada masalah pemahaman: pada titik waktu mana tingkat data atau tempat mana dalam algoritme umum yang disebut rekursif fungsi dan pada nomor berapa dia memanggil dirinya sendiri.
Alat debugging yang ada seringkali tidak berdayaberi tahu programmer solusi yang tepat.
Loop dan rekursi
Dianggap bahwa eksekusi siklik setara dengan rekursi. Memang, dalam beberapa kasus, algoritma rekursif dapat diimplementasikan dalam sintaks konstruksi bersyarat dan siklik.
Namun, jika ada pemahaman yang jelas bahwa fungsi tertentu harus diimplementasikan melalui algoritme rekursif, penggunaan eksternal dari perulangan atau pernyataan kondisional harus ditinggalkan.
Artinya di sini solusi rekursif berupa fungsi yang menggunakan dirinya sendiri akan menjadi algoritma yang lengkap, lengkap secara fungsional. Algoritma ini akan membutuhkan programmer untuk membuatnya dengan usaha, memahami dinamika algoritma, tetapi ini akan menjadi solusi akhir yang tidak memerlukan kontrol eksternal.
Kombinasi apa pun dari operator kondisional dan siklik eksternal tidak memungkinkan kita untuk merepresentasikan algoritme rekursif sebagai fungsi yang lengkap.
Konsensus Rekursi dan OOP
Di hampir semua varian pengembangan algoritma rekursif, muncul rencana untuk mengembangkan dua algoritma. Algoritma pertama menghasilkan daftar objek masa depan (instance), dan algoritma kedua sebenarnya adalah fungsi rekursif.
Solusi terbaik adalah mengatur rekursi sebagai satu properti (metode) yang benar-benar berisi algoritma rekursif, dan memasukkan semua pekerjaan persiapan ke dalam konstruktor objek.
Algoritme rekursif hanya akan menjadi solusi yang tepat jika berhasilhanya oleh dirinya sendiri, tanpa kontrol dan manajemen eksternal. Sebuah algoritma eksternal hanya dapat memberikan sinyal untuk bekerja. Hasil dari pekerjaan ini harus menjadi solusi yang diharapkan, tanpa dukungan eksternal.
Rekursi harus selalu menjadi solusi lengkap yang berdiri sendiri.
Pemahaman intuitif dan kelengkapan fungsional
Ketika pemrograman berorientasi objek menjadi standar de facto, menjadi jelas bahwa untuk membuat kode secara efektif, Anda perlu mengubah pemikiran Anda sendiri. Pemrogram harus berpindah dari sintaks dan semantik bahasa ke dinamika semantik selama eksekusi algoritma.
Karakteristik rekursi: dapat diterapkan ke semua hal:
- pengikisan web;
- operasi pencarian;
- mengurai informasi teks;
- membaca atau membuat dokumen MS Word;
- sampling atau analisis tag…
Karakteristik OOP: memungkinkan untuk mendeskripsikan algoritme rekursif pada tingkat leluhur abstrak, tetapi menyediakannya untuk merujuk ke turunan unik, yang masing-masing memiliki palet data dan propertinya sendiri.
Rekursi sangat ideal karena membutuhkan kelengkapan fungsional dari algoritmanya. OOP meningkatkan kinerja algoritme rekursif dengan memberikannya akses ke semua anak unik.
