Fungsi Rekursif

Fungsi yang memanggil dirinya sendiri

Rekursi adalah teknik di mana fungsi memecahkan masalah dengan memanggil dirinya sendiri untuk versi masalah yang lebih kecil. Terdengar seperti lingkaran setan, tapi justru elegan untuk masalah yang strukturnya berulang.

Analogi: boneka matryoshka Rusia. Untuk menghitung total boneka, kamu buka satu, lalu ulangi pertanyaan yang sama untuk boneka di dalamnya. Rekursi = "lakukan hal yang sama untuk yang lebih kecil".

Kenapa rekursi ada?

Karena banyak masalah didefinisikan secara rekursif: faktorial (n! = n × (n-1)!), struktur folder (folder berisi folder), pohon keluarga. Solusi rekursif sering 5 baris dibanding 20 baris versi loop.

Dua bagian wajib: base case dan langkah rekursif

int faktorial(int n) {
  if (n <= 1) return 1; // BASE CASE: berhenti di sini
  return n * faktorial(n - 1); // LANGKAH REKURSIF: masalah lebih kecil
}

void main() {
  print(faktorial(5)); // 120
  // 5 * faktorial(4) -> 5 * 24
  // 4 * faktorial(3) -> 4 * 6
  // 3 * faktorial(2) -> 3 * 2
  // 2 * faktorial(1) -> 2 * 1 (base case!)
}

Tanpa base case, fungsi memanggil dirinya selamanya → stack overflow. Base case adalah rem daruratnya.

Contoh kedua, fibonacci:

int fibo(int n) {
  if (n <= 1) return n; // base case: fibo(0)=0, fibo(1)=1
  return fibo(n - 1) + fibo(n - 2);
}

void main() {
  for (int i = 0; i < 10; i++) {
    print('fibo($i) = ${fibo(i)}');
  }
  // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
}

Rekursi untuk struktur bersarang

Kekuatan sebenarnya terlihat pada data bersarang:

int hitungFile(Map<String, dynamic> folder) {
  int total = 0;
  folder.forEach((nama, isi) {
    if (isi is Map<String, dynamic>) {
      total += hitungFile(isi); // rekursi ke subfolder!
    } else {
      total += 1; // file biasa
    }
  });
  return total;
}

void main() {
  var struktur = {
    'dokumen': {'a.txt': 1, 'b.txt': 1},
    'foto': {
      'liburan': {'pantai.jpg': 1},
      'selfie.jpg': 1,
    },
  };
  print('Total file: ${hitungFile(struktur)}'); // 4
}

Versi loop untuk ini butuh stack manual yang rumit. Rekursi menanganinya natural.

Kesalahan umum

1. Lupa base case

// SALAH: tidak pernah berhenti!
// int salah(int n) => n * salah(n - 1);

// BENAR
int faktorial(int n) {
  if (n <= 1) return 1;
  return n * faktorial(n - 1);
}

2. Langkah tidak mengecil

// SALAH: n tidak berkurang, base case tak tercapai
// int salah(int n) {
//   if (n <= 1) return 1;
//   return n * salah(n); // harusnya n - 1!
// }

Setiap panggilan rekursif HARUS mendekati base case.

3. Rekursi untuk yang seharusnya loop sederhana

Fibonacci rekursif naif menghitung ulang berkali-kali (eksponensial!). Untuk n besar, pakai loop atau memoization. Rekursi = alat yang tepat untuk struktur berulang, bukan pengganti loop universal.

Kesimpulan

Rekursi = base case (kapan berhenti) + langkah rekursif (masalah mengecil). Elegan untuk faktorial, fibonacci, dan struktur bersarang. Selalu pastikan ada jalan menuju base case.

Catatan teknis: Tiap panggilan rekursif memakai memori stack. Dart tidak menjamin tail call optimization, jadi rekursi puluhan ribu level bisa stack overflow. Untuk kedalaman ekstrem, ubah ke loop iteratif.