Membongkar Tuntas Logika dan Penyelesaian Soal Rekursif

Dalam dunia ilmu komputer dan pemrograman, ada beberapa konsep yang sekaligus elegan, kuat, namun terkenal membingungkan bagi pemula. Salah satu konsep tersebut adalah rekursi. Rekursi adalah ide di mana solusi untuk suatu masalah bergantung pada solusi untuk versi yang lebih kecil dari masalah yang sama. Secara sederhana, ini adalah sebuah fungsi yang memanggil dirinya sendiri.

Bayangkan Anda sedang berdiri di depan cermin sambil memegang cermin lain yang lebih kecil. Di dalam cermin yang Anda pegang, Anda akan melihat pantulan diri Anda yang memegang cermin, yang di dalamnya ada pantulan lagi, dan begitu seterusnya, menciptakan ilusi kedalaman tanpa akhir. Itulah esensi dari rekursi.

Meskipun terdengar seperti paradoks yang bisa berjalan tanpa henti, rekursi adalah teknik pemecahan masalah yang sangat praktis. Teknik ini menjadi inti dari banyak algoritma canggih, mulai dari mengurutkan data (seperti Quicksort dan Mergesort) hingga menavigasi struktur data kompleks seperti pohon (trees).

Kunci untuk menguasai rekursi adalah memahami dua komponen utamanya: Base Case (kasus dasar) dan Recursive Case (kasus rekursif). Artikel ini akan membongkar logika di balik rekursi dan memandumu melalui contoh-contoh soal klasik, lengkap dengan penyelesaiannya langkah demi langkah.

baca juga:Panduan Lengkap Menyusun Distribusi Frekuensi Beserta

Dua Pilar Utama Rekursi: Basis dan Rekurens

Sebelum kita terjun ke contoh soal, kita wajib memahami dua pilar yang menopang setiap algoritma rekursif. Tanpa salah satunya, fungsi Anda akan gagal.

1. Base Case (Kasus Dasar atau Basis)Ini adalah “rem” dari fungsi rekursif Anda. Base case adalah kondisi di mana masalah sudah sangat sederhana sehingga dapat diselesaikan secara langsung tanpa perlu memanggil fungsi itu lagi. Jika Anda membayangkan rekursi sebagai proses menuruni tangga, base case adalah lantai dasar. Tanpa base case, fungsi Anda akan terus memanggil dirinya sendiri selamanya, yang pada akhirnya akan menyebabkan stack overflow (tumpukan memori penuh).
2. Recursive Case (Kasus Rekursif atau Rekurens)Ini adalah bagian di mana fungsi tersebut memanggil dirinya sendiri. Namun, ada aturan penting: panggilan tersebut harus dilakukan dengan masalah yang “lebih kecil” atau “lebih sederhana” yang selangkah lebih dekat ke base case. Ini adalah langkah menuruni tangga. Fungsi ini pada dasarnya berkata, “Saya tidak tahu cara menyelesaikan masalah sebesar ini, tapi saya tahu cara memecahnya menjadi bagian yang lebih kecil. Saya akan menyelesaikan satu bagian kecil dan menyerahkan sisa masalah (yang lebih kecil) kepada ‘klon’ diri saya sendiri.”

Dengan memahami dua pilar ini, mari kita terapkan pada contoh soal nyata.

Contoh Soal 1: “Hello World” Rekursif – Faktorial

Soal faktorial adalah contoh pengenalan rekursi yang paling klasik. Faktorial dari sebuah bilangan non-negatif $n$, ditulis sebagai $n!$, adalah hasil perkalian semua bilangan bulat positif dari 1 hingga $n$.

Soal:

Buatlah sebuah fungsi rekursif untuk menghitung nilai faktorial dari n (ditulis n!).

Contoh: 5!=5×4×3×2×1=120.

Penyelesaian dan Logika:

Mari kita pecahkan masalah ini secara rekursif.

Bagaimana kita mendefinisikan 5!? Kita bisa bilang 5!=5×4!.

Lalu, apa itu 4!? Itu adalah 4×3!.

Dan 3!=3×2!.

Dan 2!=2×1!.

Kapan kita berhenti? Kita tahu bahwa 1!=1 (atau 0!=1 menurut definisi). Ini adalah base case kita!

• Base Case: Jika $n = 0$ atau $n = 1$, hasilnya adalah 1.
• Recursive Case: Jika $n > 1$, hasilnya adalah $n \times \text{faktorial}(n – 1)$.

Pseudocode (Contoh Kode Semu):

fungsi faktorial(n):
  // Base Case (Kondisi Berhenti)
  jika n == 0 atau n == 1:
    kembalikan 1
  
  // Recursive Case (Langkah Mundur)
  lainnya:
    kembalikan n * faktorial(n - 1)

Penelusuran (Tracing) untuk faktorial(4):

Untuk benar-benar memahaminya, mari kita telusuri apa yang terjadi di “tumpukan” (stack) panggilan:

1. faktorial(4) dipanggil.
   • $n = 4$. Ini bukan base case.
   • Fungsi harus mengembalikan $4 \times \text{faktorial}(3)$.
   • Fungsi “berhenti sejenak” (pause) menunggu hasil dari faktorial(3).
2. faktorial(3) dipanggil.
   • $n = 3$. Ini bukan base case.
   • Fungsi harus mengembalikan $3 \times \text{faktorial}(2)$.
   • Fungsi “berhenti sejenak” menunggu hasil dari faktorial(2).
3. faktorial(2) dipanggil.
   • $n = 2$. Ini bukan base case.
   • Fungsi harus mengembalikan $2 \times \text{faktorial}(1)$.
   • Fungsi “berhenti sejenak” menunggu hasil dari faktorial(1).
4. faktorial(1) dipanggil.
   • $n = 1$. Ini adalah Base Case!
   • Fungsi mengembalikan nilai 1.

Sekarang, tumpukan panggilan mulai “terurai” (unwind):

• Panggilan faktorial(2) yang tadinya menunggu, kini mendapat hasil. Ia mengembalikan $2 \times 1 = $ 2.
• Panggilan faktorial(3) yang tadinya menunggu, kini mendapat hasil. Ia mengembalikan $3 \times 2 = $ 6.
• Panggilan faktorial(4) yang awal, kini mendapat hasil. Ia mengembalikan $4 \times 6 = $ 24.

Hasil akhirnya adalah 24.

Contoh Soal 2: Tangga Emas – Bilangan Fibonacci

Deret Fibonacci adalah deret angka di mana setiap angka adalah jumlah dari dua angka sebelumnya, dimulai dari 0 dan 1.

Deretnya: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Soal:

Buatlah fungsi rekursif untuk menemukan bilangan Fibonacci ke-n.

Penyelesaian dan Logika:

Definisi Fibonacci sendiri sudah rekursif secara alami:

Fib(n)=Fib(n−1)+Fib(n−2)

Kapan kita berhenti? Kita membutuhkan dua base case karena kita mundur dua langkah.

Fib(1)=1

Fib(0)=0

• Base Case: Jika $n = 0$, kembalikan 0. Jika $n = 1$, kembalikan 1.
• Recursive Case: Jika $n > 1$, kembalikan $\text{fibonacci}(n – 1) + \text{fibonacci}(n – 2)$.

Pseudocode:

fungsi fibonacci(n):
  // Base Case
  jika n == 0:
    kembalikan 0
  jika n == 1:
    kembalikan 1
  
  // Recursive Case (Dua panggilan rekursif)
  lainnya:
    kembalikan fibonacci(n - 1) + fibonacci(n - 2)

Penelusuran (Tracing) untuk fibonacci(4):

Ini sedikit lebih rumit karena panggilannya bercabang:

1. fib(4) dipanggil.
   • Bukan base case.
   • Mengembalikan fib(3) + fib(2).
2. fib(3) dievaluasi terlebih dahulu.
   • Bukan base case.
   • Mengembalikan fib(2) + fib(1).
3. fib(2) (dari dalam fib(3)) dievaluasi.
   • Bukan base case.
   • Mengembalikan fib(1) + fib(0).
   • fib(1) adalah base case, mengembalikan 1.
   • fib(0) adalah base case, mengembalikan 0.
   • Jadi, fib(2) mengembalikan $1 + 0 = $ 1.
4. Kembali ke fib(3).
   • Kita sudah punya hasil fib(2) (yaitu 1).
   • Sekarang evaluasi fib(1).
   • fib(1) adalah base case, mengembalikan 1.
   • Jadi, fib(3) mengembalikan $1 + 1 = $ 2.
5. Kembali ke panggilan awal fib(4).
   • Kita sudah punya hasil fib(3) (yaitu 2).
   • Sekarang evaluasi fib(2). (Perhatikan: ini dipanggil lagi! Ini adalah sumber inefisiensi).
   • fib(2) mengembalikan fib(1) + fib(0), yaitu $1 + 0 = $ 1.
6. Akhirnya, fib(4) mengembalikan hasil dari fib(3) + hasil dari fib(2).
   • $2 + 1 = $ 3.

Hasil akhirnya adalah 3 (Deretnya: 0, 1, 1, 2, 3…).

Contoh Soal 3: Membalik Tumpukan – String Reversal

Rekursi tidak hanya untuk angka. Ini sangat berguna untuk memanipulasi struktur data, seperti string.

Soal:

Buatlah fungsi rekursif yang menerima sebuah string dan mengembalikan string tersebut dalam urutan terbalik.

Contoh: “kucing” harus menjadi “gnicuk”.

Penyelesaian dan Logika:

Bagaimana kita bisa membalik “kucing” secara rekursif?

Pikirkan masalah yang lebih kecil. Masalah yang lebih kecil dari “kucing” adalah “ucing”.

Jika kita bisa membalik “ucing” menjadi “gnicu”, apa yang perlu kita lakukan dengan huruf pertama, “k”? Kita hanya perlu menempelkannya di akhir.

Jadi, balik(“kucing”) adalah balik(“ucing”) + “k”.

• Base Case: Apa masalah paling sederhana? String kosong (“”) atau string dengan satu huruf (“a”). Jika dibalik, hasilnya adalah string itu sendiri.
• Recursive Case: Ambil sisa string (semua kecuali huruf pertama), panggil fungsi balik pada sisa string tersebut, lalu tempelkan huruf pertama di akhir hasilnya.

Pseudocode:

fungsi balikString(teks):
  // Base Case
  jika panjang(teks) <= 1:
    kembalikan teks
  
  // Recursive Case
  lainnya:
    hurufPertama = teks[0]
    sisaString = teks[1 sampai akhir]
    
    kembalikan balikString(sisaString) + hurufPertama

Penelusuran (Tracing) untuk balikString("abc"):

1. balik("abc") dipanggil.
   • Bukan base case.
   • hurufPertama = “a”
   • sisaString = “bc”
   • Menunggu hasil balik("bc") + "a".
2. balik("bc") dipanggil.
   • Bukan base case.
   • hurufPertama = “b”
   • sisaString = “c”
   • Menunggu hasil balik("c") + "b".
3. balik("c") dipanggil.
   • Panjangnya 1. Ini adalah Base Case!
   • Fungsi mengembalikan “c”.
4. Tumpukan terurai:
   • Panggilan balik("bc") mendapat hasil. Ia mengembalikan “c” + “b” = “cb”.
   • Panggilan balik("abc") mendapat hasil. Ia mengembalikan “cb” + “a” = “cba”.

Hasil akhirnya adalah “cba”.

baca juga:Gubernur Mirza Tinjau Masjid Agung Al Hijrah Kota Baru, Nasrullah Yusuf Sebut Kesiapan Helat Tablig Akbar Indonesia Berdoa

Kapan Harus Hati-hati dengan Rekursi

Meskipun elegan, rekursi bukanlah peluru perak. Ada dua jebakan utama:

1. Stack Overflow: Seperti yang disebutkan, jika Anda melupakan base case atau base case Anda tidak pernah tercapai, fungsi akan memanggil dirinya sendiri tanpa henti. Setiap panggilan fungsi disimpan dalam “call stack”, yang memiliki memori terbatas. Jika tumpukan ini penuh, program Anda akan crash.
2. Inefisiensi: Lihat kembali contoh Fibonacci. Untuk menghitung fib(4), kita menghitung fib(2) dua kali. Untuk menghitung fib(10), kita akan menghitung fib(5) berkali-kali. Ini disebut redundant computation (perhitungan berulang) dan sangat tidak efisien (kompleksitas waktu eksponensial). Dalam kasus seperti ini, solusi iteratif (menggunakan looping for atau while) atau teknik lanjutan yang disebut memoization (menyimpan hasil perhitungan) jauh lebih baik.

penulis:Elsandria Aurora