Recursion adalah teknik di mana fungsi memanggil dirinya sendiri untuk menyelesaikan masalah yang lebih kecil.

Dua komponen wajib:

1. Base case — kondisi berhenti (tanpa ini = infinite loop!)
2. Recursive case — panggil diri sendiri dengan masalah lebih kecil

// Factorial: 5! = 5 × 4 × 3 × 2 × 1 = 120
function factorial(n) {
  if (n <= 1) return 1;        // Base case
  return n * factorial(n - 1); // Recursive case
}

// Call stack:
// factorial(5) → 5 * factorial(4)
//   factorial(4) → 4 * factorial(3)
//     factorial(3) → 3 * factorial(2)
//       factorial(2) → 2 * factorial(1)
//         factorial(1) → 1 (base case!)
//       → 2 * 1 = 2
//     → 3 * 2 = 6
//   → 4 * 6 = 24
// → 5 * 24 = 120

Fibonacci:

// Versi rekursif naif — O(2ⁿ) 😱
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// fib(5) memanggil fib(4) + fib(3)
// fib(4) memanggil fib(3) + fib(2)
// fib(3) dihitung BERKALI-KALI! → sangat boros

Recursion vs Iteration:

Kapan pakai recursion?

• Tree/graph traversal — natural fit
• Divide and conquer — merge sort, quick sort
• Backtracking — sudoku solver, N-queens
• Masalah yang definisinya rekursif (factorial, fibonacci)

🎭 Analogi sehari-hari: Buka kotak hadiah, di dalamnya ada kotak lebih kecil, di dalam itu ada kotak lebih kecil lagi... sampai ketemu kotak paling kecil (base case). Lalu balik tutup satu per satu sambil bawa hadiah dari dalam. Setiap langkah masuk = recursive call. Kotak paling kecil = base case. Balik tutup = return.

💡 Mental model debug recursion: Bayangin call stack sebagai tumpukan kertas. Setiap call = kertas baru ditumpuk. Saat return, kertas paling atas dibuang dengan hasil. Yang sering bikin pusing: variable di kertas atas TIDAK bisa diakses dari kertas bawah (scope terisolasi).

⚠️ Jebakan klasik:

• Lupa base case = stack overflow infinite recursion
• Base case salah = miss case 1-2, error halus
• Recursion tanpa progress = f(n) → f(n) bukan f(n-1) = infinite loop
• Stack overflow untuk n besar — JS sekitar 10rb-15rb deep. Pakai iteratif kalau perlu
• Recompute sub-problem seperti fib(n) naive = O(2ⁿ), pakai memoization

🎯 Pola "kalau melihat ini, pikir recursion":

• "Tree/graph" → natural recursion
• "Pohon keputusan dengan banyak cabang" → backtracking
• "Bagi masalah jadi 2-3 sub-masalah" → divide & conquer
• "Definisi natural rekursif" — factorial(n) = n * factorial(n-1)

🧪 Tebakan cepat: fib(40) naive berapa kali manggil dirinya? >165 juta kali (1.65 × 10⁸). Karena overlap subproblem. Pakai memo? Cuma 40 unique calls.

TL;DR: Recursion = fungsi panggil diri sendiri. Wajib base case + recursive case. Cocok untuk tree, divide-conquer, definisi rekursif. Awas: stack overflow + redundant computation. Memoization sering wajib.