Rekursif

Studi Kasus: Menyusun Display Kaleng Susu

Pernahkah Anda melihat susunan kaleng susu berbentuk piramida/segitiga di supermarket? Aturannya jelas:

• Puncak (baris 1) butuh 1 kaleng.
• Baris ke-2 butuh 2 kaleng.
• Baris ke-3 butuh 3 kaleng, dan seterusnya.

Jika manager meminta Anda menyusun piramida setinggi 4 baris, berapa total kaleng yang harus dikeluarkan dari gudang? Kita bisa menjawabnya dengan pola: 4 + (total kaleng di 3 baris atasnya). Konsep memecahkan masalah dengan memanggil "masalah yang sama dalam skala lebih kecil" inilah yang disebut Rekursif.

Konsep Inti & Hands-On

Sebuah fungsi rekursif wajib memiliki 2 pilar utama:

1. Basis (Base Case): Kapan fungsi ini harus berhenti? Pada kasus kita, jika sampai di pucuk (baris == 1), maka jumlah kalengnya pasti 1. Fungsi berhenti memanggil dirinya sendiri.
2. Rekurens: Kondisi di mana fungsi memanggil dirinya sendiri dengan parameter yang terus mengecil mendekati Basis (yaitu baris - 1).

Perhatikan Starter Code, mari kita bedah Call Stack atau pohon eksekusinya:

hitungTotalKaleng(4)
= 4 + hitungTotalKaleng(3)
= 4 + (3 + hitungTotalKaleng(2))
= 4 + (3 + (2 + hitungTotalKaleng(1)))
= 4 + (3 + (2 + (1)))  // Terkena Basis!
= 10

Rekursif vs Iteratif

Semua masalah yang bisa diselesaikan dengan rekursif, juga bisa diselesaikan dengan iterasi (loop for/while), dan sebaliknya. Lalu kapan memilih rekursif?

Berikut perbandingan keduanya untuk masalah yang sama:

// Cara Iteratif
int hitungTotalKalengLoop(int baris) {
  int total = 0;
  for (int i = 1; i <= baris; i++) {
    total += i;
  }
  return total;
}

// Cara Rekursif (lebih ringkas, tapi boros stack)
int hitungTotalKaleng(int baris) {
  if (baris == 1) return 1;
  return baris + hitungTotalKaleng(baris - 1);
}

Analisis Kompleksitas Algoritma

Fungsi hitungTotalKaleng di atas memiliki kompleksitas waktu O(n) — terdapat tepat n kali pemanggilan fungsi secara berantai, satu per baris, hingga mencapai basis kasus baris == 1.

Namun berbeda dengan loop biasa, setiap pemanggilan rekursif menyumbang satu stack frame ke dalam call stack memori. Artinya konsumsi memorinya juga O(n), bukan O(1) seperti versi iteratif.