Berkali-kali, Anda mendengar orang berkata “Rekursi terlalu sulit”, atau “Mengapa saya perlu mempelajari rekursi jika dapat diselesaikan dengan iterasi?” Pencarian Google sederhana akan menemukan banyak pertanyaan yang menanyakan mengapa rekursi sangat sulit untuk dipahami.

Jadi mengapa belajar rekursi? Kemampuan berpikir secara rekursif sangat penting dalam pemrograman karena beberapa alasan:

  • Seringkali penyelesaian masalah dengan rekursi lebih bersih dan mudah untuk diterapkan dibandingkan jika Anda melakukannya secara berulang. Contoh bagus mengenai kegunaan rekursi adalah pada algoritma QuickSort.
  • Ini dapat digunakan untuk memecah masalah menjadi komponen-komponen yang lebih kecil — pola rekursif yang dikenal sebagai Divide and Conquer. Hal ini sangat berguna untuk teknik seperti MergeSort, pencarian biner, dan pencarian depth-first.

Rekursi adalah gaya pemecahan masalah yang mendasar dan setiap pengembang harus memilikinya di kotak peralatan mereka. Anda akan terkejut (mungkin tidak) melihat betapa seringnya rekursi muncul dalam wawancara coding, terutama di perusahaan besar seperti Google, Microsoft, dan Facebook. Jadi jika Anda akan melakukan wawancara dan merasa muak dengan rekursi, mungkin ini saatnya untuk memolesnya, dan kami akan membantu Anda.

Mencari kursus lengkap tentang rekursi untuk wawancara? Mulailah di sini.

Mulai dari mana

Salah satu program pertama yang membuat Anda berpikir tentang rekursi adalah Deret Fibonacci. Mari kita luangkan waktu sejenak untuk melihat contoh di C++.

{ 
  // base case 
  
  if (n<=1) 
  
  { 
     return n; 
  } 
  
  // recursive case 
  else 
  
  { 
     return (fibonacci(n-1) + fibonacci(n-2))   
  } 
}

Di sini, kita memiliki fungsi rekursif yang berisi dua bagian; kasus dasar dan kasus rekursif. Kasus dasar fungsi didefinisikan di baris 5 di mana fungsi akan berhenti dan mengembalikan “n” ketika kondisi “jika” n‹=1 terpenuhi. Dengan kata lain, kasus dasar adalah apa yang mengakhiri program Anda.

Berikutnya adalah kasus rekursif, atau fungsi yang ingin kita ulangi hingga kita mencapai kasus dasar. Jadi jika kondisi kasus dasar tidak bernilai benar, fungsi tersebut kemudian memasuki blok “else” ( baris 8–11), yang kemudian secara rekursif memanggil dirinya sendiri dengan argumen masukan “fibonacci(n- 1)+ fibonacci(n-2)”, seperti terlihat pada baris 10.

Sekarang, pewawancara Anda akan memberi tahu Anda sesuatu seperti, “kembalikan elemen ke-n dalam deret Fibonacci.” Jadi Anda memutuskan untuk menggunakan perulangan while tradisional dan berhasil, tetapi apakah ini efisien? Jadi pewawancara bertanya, “bagaimana Anda mengoptimalkan algoritma ini?” Salah satu cara untuk melakukannya adalah melalui rekursi karena Anda hanya memiliki dua variabel (fibonacci n-1) dan (fibonacci n-2). Mereka mungkin mengajukan pertanyaan lanjutan seperti, “bagaimana Anda lebih mengoptimalkan fungsi rekursif Anda?” Salah satu cara untuk melakukan hal ini adalah melalui memoisasi — teknik yang digunakan untuk mempercepat program komputer dengan menyimpan hasil pemanggilan fungsi yang mahal dan mengembalikan hasil cache ketika input yang sama muncul lagi.

Apa yang hebat tentang contoh ini dan deret Fibonacci adalah transisi ke beberapa teknik yang sangat berguna seperti memoisasi dan pemrograman dinamis.

Selalu pikirkan kasus dasarnya

Jika Anda sedang menjalani wawancara teknis dan muncul pertanyaan rekursi, yang terbaik adalah memulai dengan mempertimbangkan tujuan akhir atau kasus dasar. Ada dua bagian fungsi rekursif;

  • Yang pertama adalah kasus dasar, di mana panggilan ke fungsi berhenti, yaitu tidak membuat panggilan rekursif berikutnya.
  • Bagian kedua dari fungsi rekursif adalah kasus rekursif, dimana fungsi tersebut memanggil dirinya sendiri berulang kali hingga mencapai kasus dasar.

Penting untuk diingat bahwa kasus dasar Anda memastikan bahwa program akan keluar. Jika tidak, program Anda akan berjalan tanpa batas waktu (pada kenyataannya, program Anda akan berjalan hingga Anda mencapai stack overflow).

Mengidentifikasi Q rekursi — dengarkan kata kunci

Ingat kembali masa-masa probabilitas dan permasalahan kata? Bagaimana mereka mengajari Anda setiap kali Anda mendengar kata “dan” Anda akan mengalikan probabilitas dan “atau” berarti Anda menambahkannya. Konsep ini memiliki beberapa kesamaan dengan pemrograman dan khususnya rekursi. Indikasi yang sangat baik tentang kapan Anda harus menggunakan rekursi adalah ketika Anda mendengar konsep seperti “pohon”, “grafik”, “daftar tertaut”, atau “bersarang”. Ini adalah hadiah yang hampir mati yang Anda perlukan untuk melakukan beberapa fungsi rekursif.

Pertanyaan untuk ditanyakan pada diri sendiri

Jika Anda ditanyai pertanyaan teknis dalam sebuah wawancara yang berhubungan dengan rekursi, penting untuk memikirkan beberapa hal:

  • Apa kasus dasarnya?
  • Kasus rekursif paling sederhana apa yang bisa saya pecahkan? Kemudian kembangkan dari sana.
  • Bagaimana pendekatan Anda dalam memecahkan masalah mempengaruhi tumpukan? Kemudian pikirkan cara untuk memperbaikinya.

Konsep rekursi yang Anda ingin persiapkan

Struktur data

  • Heaps — struktur data berbasis pohon yang pohonnya merupakan pohon biner lengkap.
  • Pohon — terdiri dari kumpulan simpul yang simpul pertama pada pohon disebut akar dan simpul terakhir disebut daun.
  • Grafik — struktur data non-linier yang terdiri dari node dan edge dan digunakan untuk mewakili jaringan.
  • Daftar tertaut — kumpulan elemen data linier, yang urutannya tidak ditentukan oleh penempatan fisiknya di memori.

Algoritma

  • Traversal Grafik mis. Pencarian Kedalaman Pertama dan Pencarian Luas Pertama
  • Quicksort (mengikuti pola bagi dan taklukkan) — algoritma pengurutan yang sangat efisien dan didasarkan pada partisi array data menjadi array yang lebih kecil.
  • Mergesort (mengikuti pola bagi dan taklukkan) - memecah daftar menjadi beberapa subdaftar hingga setiap subdaftar terdiri dari satu elemen dan menggabungkan subdaftar tersebut sedemikian rupa sehingga menghasilkan daftar yang diurutkan.
  • Pencarian biner — menemukan posisi nilai target dalam larik yang diurutkan secara rekursif bekerja pada larik yang semakin kecil hingga Anda menemukan nilainya atau ukuran larik menjadi 0.

Pola

  • Bagilah dan Taklukkan - sebuah pola yang memecah masalah menjadi sub-masalah yang lebih kecil yang kemudian diselesaikan secara rekursif dan digabungkan (bagus untuk penyortiran pohon).

Teknik

  • Memoisasi — digunakan untuk mempercepat program komputer dengan menyimpan hasil pemanggilan fungsi yang mahal dan mengembalikan hasil cache ketika input yang sama muncul lagi.
  • Pelacakan mundur — mempertimbangkan pencarian setiap kemungkinan kombinasi untuk memecahkan masalah pengoptimalan.

Soal untuk membantu Anda berlatih

Agar merasa nyaman dalam wawancara teknis, Anda harus mempraktikkan konsep-konsep yang disebutkan di atas. Berikut adalah beberapa contoh masalah yang dapat Anda atasi dan membuat Anda berpikir tentang rekursi:

Bungkus

Rekursi adalah konsep yang menantang, tetapi jika Anda ingin memajukan karir Anda sebagai pengembang perangkat lunak, rekursi sangatlah penting. Ini sering kali dapat menghasilkan kode yang lebih bersih dan efisien, dan menunjukkan bahwa Anda dapat memikirkan masalah dengan cara yang berbeda.

Ada beberapa hal yang ingin Anda lakukan sebelum memasuki wawancara:

Pahami dasar-dasarnya:Pahami mengapa rekursi penting, dan mana yang berguna dan mana yang tidak. Ingatlah bahwa sebagian besar, jika tidak semua masalah dapat diselesaikan secara iteratif atau rekursif, jadi ambillah semua informasi yang tersedia dan selesaikan dengan tepat. Ingatlah untuk mendengarkan kata kunci/konsep tersebut karena mungkin memberi petunjuk tentang apa yang dicari pewawancara.

Latihan:Latihan membuat sempurna. Cobalah menuliskan solusinya di papan tulis dan bicarakan bagaimana Anda melakukannya. Selain itu, coba selesaikan masalah dengan iterasi lalu lakukan dengan rekursi dan sebaliknya.

Langkah selanjutnya.. Perluas pembelajaran Anda:Berikut adalah kursus bagus berjudul, “ Memecahkan masalah dengan rekursi”, yang mencakup beberapa konsep yang disebutkan di atas (yaitu pohon, grafik, daftar tertaut). Anda akan mempelajari dasar-dasar serta beberapa topik perantara yang kemudian dapat Anda coba dalam tantangan dan kuis interaktif.

Awalnya diterbitkan di https://blog.educative.io pada 16 April 2019.