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

Analisis Kompleksitas Algoritma

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