Recursion

Sepanjang section ini, function yang kita tulis memanggil function lain. Recursion memangkas arah panggilan itu ke dirinya sendiri: sebuah function di dalam badannya memanggil nama function yang sama dengan masukan yang lebih kecil, berulang-ulang, sampai kondisi berhenti tercapai. Ide ini cocok untuk masalah yang bisa dipecah menjadi versi lebih kecil dari dirinya — menghitung faktorial, menelusuri struktur bertingkat, atau membaca isi folder di dalam folder.

Recursion punya dua syarat yang tidak boleh dilanggar: setiap panggilan harus mengarah pada kasus yang lebih sederhana, dan harus ada base case — kondisi yang membuat function berhenti memanggil dirinya. Chapter ini membangun keduanya lewat faktorial, mengukur biaya recursion pada fibonacci, dan membuktikan apa yang terjadi bila syaratnya dilanggar.

Faktorial: Loop vs Rekursif #

Faktorial dari n adalah hasil perkalian 1 × 2 × ... × n, dan 5! = 120. Hubungan antar-langkahnya bersarang secara alami: 5! = 5 × 4!, 4! = 4 × 3!, dan seterusnya sampai 1! = 1. Karena itulah faktorial menjadi contoh klasik recursion. Berkas berikut menghitungnya dengan dua cara — loop dan rekursif — lengkap dengan jejak setiap panggilan:

js
faktorial-rekursif.js
// faktorial-rekursif.js
// Recursion: function yang memanggil dirinya sendiri dengan base case.

// --- 1. faktorial versi loop sebagai pembanding ---
function faktorialLoop(n) {
  let hasil = 1;
  for (let i = 2; i <= n; i++) {
    hasil = hasil * i;
  }
  return hasil;
}

console.log("Faktorial 5 (loop):", faktorialLoop(5));

// --- 2. faktorial versi rekursif, dilacak langkah demi langkah ---
function faktorial(n) {
  console.log("Masuk faktorial(" + n + ")");
  if (n <= 1) {
    console.log("Base case tercapai, kembalikan 1");
    return 1;
  }
  const sisa = faktorial(n - 1);
  console.log("faktorial(" + n + ") = " + n + " * " + sisa);
  return n * sisa;
}

console.log("Hasil:", faktorial(5));

// --- 3. fibonacci singkat dan biaya pemanggilannya ---
let jumlahPanggil = 0;

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

console.log("Fibonacci 10:", fibonacci(10));
console.log("fibonacci(10) dipanggil:", jumlahPanggil, "kali");

jumlahPanggil = 0;
fibonacci(20);
console.log("fibonacci(20) dipanggil:", jumlahPanggil, "kali");

// --- 4. recursion tanpa base case menghabiskan ruang stack ---
function turunTanpaHenti(n) {
  return turunTanpaHenti(n + 1); // tidak pernah mencapai base case
}

try {
  turunTanpaHenti(1);
} catch (error) {
  console.log(error.name, "-", error.message);
}

Output yang Dihasilkan:

text
Faktorial 5 (loop): 120
Masuk faktorial(5)
Masuk faktorial(4)
Masuk faktorial(3)
Masuk faktorial(2)
Masuk faktorial(1)
Base case tercapai, kembalikan 1
faktorial(2) = 2 * 1
faktorial(3) = 3 * 2
faktorial(4) = 4 * 6
faktorial(5) = 5 * 24
Hasil: 120
Fibonacci 10: 55
fibonacci(10) dipanggil: 109 kali
fibonacci(20) dipanggil: 13529 kali
RangeError - Maximum call stack size exceeded

Mari kita telaah apa yang terjadi pada baris-baris kode di atas:

Baris 5–13 (faktorialLoop): versi loop mengumpulkan perkalian dalam satu variabel hasil. Keluarannya 120 — angka yang akan dipakai sebagai pembanding.
Baris 16–27 (faktorial versi rekursif): bentuk inti recursion ada di baris 22 dan 24 — faktorial(n) memanggil faktorial(n - 1), lalu mengalikan hasilnya dengan n. Setiap panggilan membawa masukan yang lebih kecil satu angka, sehingga rantai pasti bergerak menuju base case.
Baris 18–21 (base case): kondisi n <= 1 adalah pintu keluarnya. Tanpa baris ini, faktorial(0) akan memanggil faktorial(-1), dan seterusnya tanpa akhir.
Jejak keluaran (baris Masuk ... dan faktorial(...) = ...): keluaran memperlihatkan dua fase. Lima baris Masuk turun berurutan — call stack menumpuk panggilan yang menunggu. Setelah base case mengirim 1, baris faktorial(2) = 2 * 1 dan seterusnya naik kembali: setiap lapisan tumpukan menyelesaikan perhitungannya lalu menyerahkan hasil ke pemanggilnya, sampai 5 * 24 = 120.
Baris 30–45 (fibonacci dan penghitungnya): setiap pemanggilan menaikkan jumlahPanggil, sehingga biaya recursion terukur nyata: fibonacci(10) dipanggil 109 kali, sedangkan fibonacci(20) — hanya dua kali lipat masukannya — dipanggil 13529 kali. Perhitungan berlipat-lipat karena tiap tingkat memanggil dua cabang, dan banyak nilai dihitung berulang-ulang.
Baris 48–56 (turunTanpaHenti): recursion tanpa pintu keluar. Setiap panggilan menumpuk satu lapisan call stack hingga ruangnya habis; Node menghentikannya dengan RangeError: Maximum call stack size exceeded.

Membaca Pohon Pemanggilan Fibonacci #

Angka 13529 itu masuk akal bila kita melihat bentuk panggilannya. Berbeda dengan faktorial yang hanya menumbuhkan satu cabang, fibonacci menumbuhkan dua — dan setiap cabang menumbuhkan dua cabang lagi. Untuk fibonacci(4), pohonnya tampak seperti ini:

flowchart TD F4["fibonacci(4)"] --> F3["fibonacci(3)"] F4 --> F2a["fibonacci(2)"] F3 --> F2b["fibonacci(2)"] F3 --> F1["fibonacci(1)"]

Bagan di atas membaca dua fakta. Pertama, jumlah simpul bertambah cepat: setiap tingkat kedalaman menggandakan pekerjaan, sehingga biaya tumbuh mengikuti kurva yang jauh lebih curam daripada masukannya — dari 109 panggilan pada masukan 10 menjadi 13529 pada masukan 20. Kedua, ada pekerjaan yang diulang tanpa perlu: fibonacci(2) dihitung dua kali untuk masukan sekecil 4, dan pengulangan itu berlipat jumlahnya di masukan yang lebih besar. Inilah alasan versi rekursif fibonacci berbahaya dipakai mentah-mentah, sekaligus alasan teknik penyimpanan hasil (mengingat nilai yang sudah dihitung) menjadi materi penting di bagian performa.

Base Case dan Kedalaman Stack #

Setiap pemanggilan function menempati satu lapisan di call stack, dan jumlah lapisan itu ada batasnya — ribuan, bukan jutaan. Dua pelanggaran berujung pada RangeError yang sama. Pertama, base case yang hilang atau tak terjangkau, seperti turunTanpaHenti di berkas contoh. Kedua, recursion yang sah tetapi terlalu dalam: faktorial(100000) pun memunculkan RangeError: Maximum call stack size exceeded karena tumpukannya melebihi batas sebelum mencapai 1. Untuk praktik pembelajaran, ujilah dengan nilai kecil — kedua perilaku tersebut sudah terbukti tanpa perlu mendorong mesin ke batasnya. Pesan errornya pun tidak menyebut baris mana yang salah: RangeError hanya melaporkan bahwa tumpukan penuh, sehingga penyebabnya harus dicari dari struktur recursion itu sendiri.

Merancang Recursion yang Aman #

Empat kebiasaan menjaga recursion tetap terkendali — berlaku untuk faktorial, fibonacci, maupun masalah yang lebih besar:

Tetapkan base case lebih dulu, sebelum menulis badan rekursifnya. Tanyakan: masukan seperti apa yang tidak perlu memanggil diri lagi? Pada faktorial jawabannya n <= 1; pada penelusuran folder, folder kosong.
Pastikan setiap panggilan bergerak menuju base case. Masukan harus menyempit setiap langkah — n - 1, folder induk yang lebih atas, daftar yang lebih pendek. Panggilan yang menyamping atau membesar tidak akan pernah tiba.
Percayai hasil dari panggilan rekursif. Tulis n * faktorial(n - 1) dengan keyakinan bahwa faktorial(n - 1) benar — buktinya menumpuk dari base case yang paling kecil. Cara berpikir ini meringankan kepala: cukup selesaikan satu langkah, sisanya adalah langkah yang sama dalam ukuran lebih kecil.
Ukur biayanya pada masukan yang mewakili. Penghitung jumlahPanggil pada berkas contoh adalah alat sederhana untuk itu; bila jumlah panggilan membengkak tidak wajar, cari pekerjaan yang diulang — atau gunakan loop.

Recursion menutup section Functions: kita sudah menguasai seluruh bentuk definisi function — declaration, expression, dan arrow — beserta parameter dalam segala variasinya, statement return, pola callback, aturan scope, closure, hingga function yang memanggil dirinya sendiri. Wadah data yang selama ini kita pakai secukupnya — array — belum kita pelajari secara tertib. Section berikutnya mengisinya: Arrays.

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

javascript
// faktorial-rekursif.js
// Recursion: function yang memanggil dirinya sendiri dengan base case.

// --- 1. faktorial versi loop sebagai pembanding ---
function faktorialLoop(n) {
  let hasil = 1;
  for (let i = 2; i <= n; i++) {
    hasil = hasil * i;
  }
  return hasil;
}

console.log("Faktorial 5 (loop):", faktorialLoop(5));

// --- 2. faktorial versi rekursif, dilacak langkah demi langkah ---
function faktorial(n) {
  console.log("Masuk faktorial(" + n + ")");
  if (n <= 1) {
    console.log("Base case tercapai, kembalikan 1");
    return 1;
  }
  const sisa = faktorial(n - 1);
  console.log("faktorial(" + n + ") = " + n + " * " + sisa);
  return n * sisa;
}

console.log("Hasil:", faktorial(5));

// --- 3. fibonacci singkat dan biaya pemanggilannya ---
let jumlahPanggil = 0;

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

console.log("Fibonacci 10:", fibonacci(10));
console.log("fibonacci(10) dipanggil:", jumlahPanggil, "kali");

jumlahPanggil = 0;
fibonacci(20);
console.log("fibonacci(20) dipanggil:", jumlahPanggil, "kali");

// --- 4. recursion tanpa base case menghabiskan ruang stack ---
function turunTanpaHenti(n) {
  return turunTanpaHenti(n + 1); // tidak pernah mencapai base case
}

try {
  turunTanpaHenti(1);
} catch (error) {
  console.log(error.name, "-", error.message);
}