Recursion — Algoritma

Recursion adalah teknik di mana fungsi memanggil dirinya sendiri untuk menyelesaikan masalah yang lebih kecil. Dua komponen wajib: Base case — kondisi…

Rekursi (recursion) adalah function yang memanggil dirinya sendiri untuk menyelesaikan versi masalah yang lebih kecil. Masalahnya terus dikecilkan sampai cukup kecil untuk dijawab langsung, lalu jawabannya dirakit balik. Mirip kotak kado bersarang: kamu buka kotak demi kotak sampai ketemu yang paling kecil, isinya hadiah.

🧪 Tebakan cepat: kalau baris base case di factorial dihapus, apa yang terjadi: hasilnya 0, undefined, atau programnya crash? Tebak dulu, jawabannya ada di bagian "Call stack: tumpukan panggilan".

Base case dan recursive case

Factorial 5, ditulis 5!, adalah 5 × 4 × 3 × 2 × 1 = 120. Itu sama dengan 5 × 4!, jadi factorial(5) cukup menghitung 5 * factorial(4), dan begitu terus sampai 1:

Panggilan	Isinya	Yang dikembalikan
`factorial(5)`	`5 * factorial(4)`	5 × 24 = 120
`factorial(4)`	`4 * factorial(3)`	4 × 6 = 24
`factorial(3)`	`3 * factorial(2)`	3 × 2 = 6
`factorial(2)`	`2 * factorial(1)`	2 × 1 = 2
`factorial(1)`	base case	1

Kolom tengah dibaca dari atas ke bawah: tiap panggilan menunggu panggilan di bawahnya. Kolom kanan dibaca dari bawah ke atas: begitu factorial(1) menjawab 1, jawabannya naik satu per satu.

function factorial(n) {
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // recursive case
}

console.log(factorial(5)); // 120
console.log(factorial(0)); // 1

if (n <= 1) return 1; adalah base case, kondisi berhenti: function langsung menjawab tanpa memanggil dirinya lagi. n <= 1 juga menangkap 0, jadi factorial(0) hasilnya 1 (memang begitu aturannya).
return n * factorial(n - 1); adalah recursive case: function memanggil dirinya dengan angka lebih kecil, n - 1, lalu mengalikan hasilnya dengan n. return di depannya penting, tanpa itu hasilnya dibuang dan function mengembalikan undefined.
Tiap panggilan harus makin dekat ke base case. n - 1 mengecil terus sampai kena n <= 1.

Call stack: tumpukan panggilan

Panggilan yang belum selesai disimpan JavaScript di call stack, sebuah tumpukan. factorial(5) menunggu jawaban factorial(4), jadi factorial(4) ditaruh di atasnya, dan seterusnya. Panggilan paling atas, si base case, selesai duluan, lalu tumpukannya berkurang satu per satu.

Tanpa base case, gak ada panggilan yang bisa selesai. factorial terus memanggil dirinya (5, 4, 3, lalu 0, -1, -2, ...) sampai stack-nya penuh, dan program crash dengan error stack overflow. Di Chrome bunyinya RangeError: Maximum call stack size exceeded. Itu jawaban tebakan tadi: crash. Hal yang sama terjadi kalau base case-nya gak pernah kena, misalnya if (n === 1) lalu kamu memanggil factorial(0).

Stack itu terbatas, kira-kira 10.000 panggilan, tergantung browser dan function-nya. Rekursi sedalam sejuta panggilan tetap crash walau base case-nya benar, jadi untuk hitungan sepanjang itu pakai loop.

Hitung mundur dan menjumlah

function mundur(n) {
  if (n === 0) return; // berhenti di 0
  console.log(n);
  mundur(n - 1); // panggil lagi dengan angka lebih kecil
}

mundur(3); // 3, lalu 2, lalu 1

function jumlah(n) {
  if (n <= 0) return 0;
  return n + jumlah(n - 1);
}

console.log(jumlah(4)); // 10

mundur gak mengembalikan apa-apa, dia mencetak lalu memanggil mundur(n - 1). jumlah(4) adalah 4 + 3 + 2 + 1 + 0 = 10: polanya sama dengan factorial, cuma * jadi + dan base case-nya mengembalikan 0.

Fibonacci: dua base case

Deret Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Tiap angka adalah jumlah dua angka sebelumnya. Hitungannya mulai dari ke-0: fibonacci(0) = 0, fibonacci(1) = 1, fibonacci(6) = 8, fibonacci(10) = 55.

function fibonacci(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6)); // 8

Tiap panggilan turun ke n - 1 dan n - 2, jadi butuh dua base case. Kalau cuma if (n <= 1) return 1, fibonacci(0) jadi 1, salah. Dua baris itu boleh disingkat jadi if (n <= 1) return n;.

⚠️ Jebakan yang sering ketemu

Lupa return di recursive case. n * factorial(n - 1); tanpa return menghitung lalu membuang hasilnya, jadi yang keluar undefined.
Angkanya gak mengecil. factorial(n) yang memanggil factorial(n) lagi, bukan factorial(n - 1), gak pernah sampai base case dan crash.
Fibonacci rekursif lambat untuk n besar. fibonacci(5) menghitung fibonacci(2) tiga kali. Jumlah panggilannya hampir dua kali lipat tiap n naik 1: fibonacci(30) sudah sekitar 2,7 juta panggilan. Obatnya, menyimpan hasil yang sudah dihitung, ada di lesson Memoization.

TL;DR: Rekursi adalah function yang memanggil dirinya dengan masalah lebih kecil. Dia butuh base case (kondisi berhenti yang langsung return jawaban) dan recursive case (return panggilan dirinya dengan angka lebih kecil). Panggilan yang belum selesai menunggu di call stack; tanpa base case stack-nya penuh dan program crash (stack overflow). factorial(n) adalah n * factorial(n - 1) dengan factorial(0) = 1. fibonacci(n) adalah fibonacci(n - 1) + fibonacci(n - 2) dengan dua base case: 0 untuk n = 0 dan 1 untuk n = 1.