Advertisement
  1. Code
  2. JavaScript

Memahami Rekursi dengan JavaScript

by
Read Time:8 minsLanguages:

Indonesian (Bahasa Indonesia) translation by Imam Firmansyah (you can also view the original English article)

Pengenalan

Beberapa masalah lebih alami jika dipecahkan menggunakan rekursi. Sebagai contoh, urutan seperti deret Fibonacci memiliki definisi rekursif. Setiap angka dalam urutan adalah jumlah dari dua angka sebelumnya dalam urutan. Masalah yang mengharuskan Anda untuk membangun atau melintasi struktur data seperti pohon juga dapat diselesaikan dengan rekursi. Melatih diri Anda untuk berpikir secara rekursif akan memberi Anda keterampilan yang kuat untuk menyelesaikan masalah seperti itu.

Dalam tutorial ini, saya akan membahas beberapa fungsi rekursif selangkah demi selangkah untuk melihat cara kerjanya dan menunjukkan teknik yang dapat Anda gunakan untuk menentukan fungsi rekursif secara sistematis.

Isi:

  • Apa itu Rekursi?
  • Rekursi dengan Angka
  • Rekursi dengan List
  • Membangun List
  • Tinjauan

Apa itu Rekursi?

Fungsi yang didefinisikan secara rekursif adalah fungsi yang didefinisikan dalam bentuk versi yang lebih sederhana dari dirinya sendiri. Ini adalah contoh yang disederhanakan:

Untuk memahami bagaimana rekursi bekerja secara konseptual, kita akan melihat contoh yang tidak ada hubungannya dengan kode. Bayangkan Anda bertanggung jawab untuk menjawab panggilan telepon ditempat kerja. Karena ini adalah perusahaan yang sibuk, telepon Anda memiliki beberapa saluran telepon sehingga Anda dapat menangani banyak panggilan sekaligus. Setiap saluran telepon merupakan tombol pada penerima, dan ketika ada panggilan masuk, tombol akan berkedip. Hari ini, ketika Anda tiba untuk bekerja dan menghidupkan telepon, ada empat saluran yang berkedip sekaligus. Jadi Anda mulai bekerja untuk menjawab semua panggilan.

Anda mengambil panggilan pertama dan memberi tahu mereka 'tolong tunggu'. Kemudian Anda mengambil panggilan kedua dan memintanya untuk menunggu. Selanjutnya, Anda mengambil panggilan ketiga dan memintanya untuk menunggu. Akhirnya, Anda menjawab panggilan ke empat dan berbicara dengan si penelepon. Ketika Anda selesai dengan penelepon ke empat, Anda menutup telepon dan mengambil panggilan ketiga. Ketika Anda selesai dengan panggilan ketiga, Anda menutup telepon dan mengambil panggilan kedua. Ketika Anda selesai dengan panggilan kedua, Anda menutup dan mengangkat panggilan pertama. Saat Anda menyelesaikan panggilan tersebut, akhirnya Anda dapat meletakkan telepon Anda.

Setiap panggilan telepon dalam contoh ini seperti panggilan rekursif dalam suatu fungsi. Ketika Anda mendapat panggilan, panggilan tersebut diletakkan dalam tumpukan panggilan (kita berbica tentang pemrograman). Jika Anda tidak dapat menyelesaikan panggilan dengan segera, Anda dapat menahan panggilan tersebut. Jika Anda memiliki fungsi pemanggil yang tidak dapat segera diperiksa, panggilan akan tetap berada pada tumpukan panggilan. Ketika Anda dapat menjawab panggilan, lakukan panggilan tersebut. Ketika kode Anda dapat mengevaluasi pemanggilan fungsi, kode tersebut akan muncul dari tumpukan. Ingatlah analogi ini saat Anda melihat contoh kode berikut.

Rekursi dengan Angka

Semua fungsi rekursif membutuhkan kondisi utama sehingga mereka akan berhenti. Namun, menambahkan kondisi utama ke fungsi tidak mencegahnya berjalan tanpa batas. Fungsi harus memiliki langkah untuk membawa kita lebih dekat ke kondisi utama. Terakhir adalah langkah rekursif. Dalam langkah rekursif, masalahnya dikurangi menjadi versi masalah yang lebih kecil.

Misalkan Anda memiliki fungsi yang akan menjumlahkan angka dari 1 hingga n. Misalnya, jika n = 4, itu akan berjumlah 1 + 2 + 3 + 4.

Pertama, kami menentukan kondisi utama. Menemukan kondisi utama juga dapat dianggap sebagai menemukan kondisi dimana masalah dapat diselesaikan tanpa rekursi. Dalam kondisi ini, saat n sama dengan nol. Zero (nol) tidak memiliki bagian, sehingga rekursi kami dapat hentikan ketika kami mencapai nilai 0.

Di setiap langkah, Anda akan mengurangi satu dari nilai terkini. Apa itu kondisi rekursif? Kondisi rekursif adalah jumlah fungsi yang di panggil dengan penguranan jumlah.

Ini adalah apa yang terjadi pada setiap langkah:

  • Menuju fungsi sum(4).
  • Apakah 4 sama dengan 0? Jika tidak. Tempatkan sum(4) panda kondisi Menunggu dan Menuju fungsi sum(3).
  • Apakah 3 sama dengan 0? Jika tidak. Tempatkan sum(3) panda kondisi Menunggu dan Menuju fungsi sum(2).
  • Apakah 2 sama dengan 0? Jika tidak. Tempatkan sum(2) panda kondisi Menuggu dan Menuju fungsi sum(1).
  • Apakah 1 sama dengan 0? Jika tidak. Tempatkan sum(1) panda kondisi Menunggu dan Menuju fungsi sum(0).
  • Apakah 0 sama dengan 0? Jika ya. Periksa sum(0).
  • Mengambil fungsi sum(1).
  • Mengambil fungsi sum(2).
  • Mengambil fungsi sum(3).
  • Mengambil fungsi sum(4).

Ini adalah cara lain untuk melihat bagaimana fungsi memproses setiap panggilan:

Argumen harus berubah dalam kondisi rekursif dan membawa Anda lebih dekat ke kondisi utama. Argumen ini harus diuji dalam kondisi utama. Dalam contoh sebelumnya, karena kami mengurangkan satu dalam kasus rekursif, kami menguji apakah argumen sama dengan nol dalam kasus utama kami.

Tugas

  1. Menerapkan fungsi penjumlahan menggunakan perulangan sebagai ganti rekursi.
  2. Membuat sebuah fungsi yang mengalikan dua angka secara rekursif. Sebagai contoh, multiply(2,4) akan mengembalikan nilai 8. Menulis apa yang terjadi pada setiap langkah untuk  multiply(2,4).

Rekursi dengan List

Rekursi dalam List serupa dengan rekursi pada angka, kecuali bahwa sebagai ganti pengurangan jumlah pada setiap langkah, kami mengurangi list pada setiap langkah sampai kami mendapatkan list dalam kondisi kosong.

Pertimbangkan fungsi penjumlahan yang mengambil list sebagai input dan mengembalikan jumlah semua elemen dalam list. Ini adalah implementasi untuk fungsi penjumlahan:

Fungsi empty mengembalikan nilai true jika list tidak memiliki elemen. fungsi car mengembalikan elemen pertama dalam list. Sebagai contoh, car([1,2,3,4]) mengembalikan nilai 1. Fungsi cdr mengembalikan list tanpa elemen pertama. Sebagai contoh, cdr([1,2,3,4]) mengembalikan nilai [2,3,4]. Apa yang terjadi ketika kita menjalankan sum([1,2,3,4])?

Ketika rekursi dalam daftar, periksa apakah itu kosong. Jika tidak, lakukan langkah rekursif pada versi list yang lebih sedikit.

Tugas

  1. Menulis ulang fungsi penjumlahan ini sehingga menggunakan perualngan untuk jumlah setiap item dalam list yang bukan rekursi.
  2. Tentukan fungsi bernama panjang yang mengambil list sebagai input dan mengembalikan jumlah elemen dalam list tersebut. Anda tidak harus menggunakan fungsi length bawaan dari JavaScript. Misalnya, length(['a', 'b', 'c', 'd']) harus mengembalikan nilai 4. Tulis apa yang terjadi pada setiap langkah.

Membangun List

Dalam contoh terakhir, kami mengembalikan sebuah angka. Tetapi seandainya kita ingin mengembalikan sebuah list. Itu berarti sebagai gantinya akan menambahkan angka ke langkah rekursif, kami perlu menambahkan sebuah list. Pertimbangkan fungsi remove, yang mengambil item dan list sebagai input dan mengembalikan list dengan item yang dihapus. Hanya item yang ditemukan pertama yang akan dihapus.

Di sini, fungsi eq mengembalikan nilai true jika kedua input sama. Fungsi cons mengambil elemen dan list sebagai masukan dan mengembalikan list baru dengan elemen yang ditambahkan di awal.

Kami akan memeriksa apakah item pertama dalam list sama dengan item yang ingin kami hapus. Jika ya, hapus elemen pertama dari list dan kembalikan ke list baru Jika item pertama tidak sama dengan item yang ingin kita hapus, kita ambil elemen pertama dalam list dan tambahkan ke langkah rekursif. Langkah rekursif akan berisi list dengan elemen pertama yang dihapus.

Kami akan terus menghapus elemen hingga mencapai kondisi utama, yang merupakan list yang kosong. List kosong ini berarti kami telah melintasi semua item dalam list. Apa yang harus fungsi remove('c', ['a', 'b', 'c', 'd']) lakukan?

Dalam situasi ketika kita perlu membuat list, kita mengambil elemen pertama dan menambahkannya ke bagian rekursif dari list.

Tugas

  1. Tulis ulang fungsi remove sehingga menggunakan perualangan sebagai ganti rekursi untuk menghapus elemen dari list.
  2. Ubah fungsi remove sehingga menghapus semua kemunculan item dari list. Misalnya, remove('c', ['a', 'b', 'c', 'd', 'c'] mengembalikan ['a', 'b', 'd']. Tulis apa yang terjadi langkah demi langkah.

Meninjau

Ada tiga bagian ke fungsi rekursif. Yang pertama adalah kondisi utama, yang merupakan kondisi untuk mengakhiri. Yang kedua adalah langkah untuk membawa kita lebih dekat ke kasus utama kita. Yang ketiga adalah langkah rekursif, dimana fungsi memanggil dirinya dengan input yang dikurangi.

Rekursi itu seperti iterasi. Setiap fungsi yang dapat Anda definisikan secara rekursif juga dapat didefinisikan menggunakan perulangan. Hal-hal lain yang perlu dipertimbangkan ketika menggunakan rekursi berulang pada list bertingkat dan mengoptimalkan panggilan rekursif Anda.

Sumber yang bagus untuk terus belajar tentang rekursi adalah buku The Little Schemer. Ini mengajarkan Anda bagaimana berpikir secara rekursif menggunakan format pertanyaan dan jawaban.

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.