Rekursi

Fungsi rekursif dengan kasus dasar dan kasus rekursif, beserta persoalan klasiknya.

Daftar isi

Rekursi adalah teknik memecahkan masalah dengan metode yang memanggil dirinya sendiri pada masukan yang lebih kecil, sampai masukannya cukup kecil untuk dijawab langsung. Topik ini membahas dua syarat setiap rekursi, yaitu kasus dasar dan kasus rekursif, alur tumpukan panggilan di baliknya, serta dua persoalan klasiknya, faktorial dan deret Fibonacci. Setelah membacanya, metode rekursif sederhana dapat ditulis lengkap dengan kedua syaratnya.

Dua syarat rekursi#

Setiap metode rekursif memuat dua bagian, yaitu kasus dasar (base case) yang menjawab langsung tanpa memanggil dirinya lagi, dan kasus rekursif yang memanggil dirinya dengan masukan yang mendekati kasus dasar. Tanpa kasus dasar, pemanggilan tidak pernah selesai dan program berhenti dengan error. Faktorial adalah contoh klasiknya, yaitu hasil kali sebuah bilangan bulat positif dengan seluruh bilangan di bawahnya.

n! = n \times (n-1) \times (n-2) \times \cdots \times 1

Kasus dasarnya adalah $0! = 1$ , dan kasus rekursifnya adalah $n! = n \times (n-1)!$ . Kedua bagian itu diterjemahkan ke Ruby sebagai berikut.

ruby faktorial.rb

# Faktorial secara rekursif

def faktorial(n)
  return 1 if n <= 1

  n * faktorial(n - 1)
end

p faktorial(5)
p faktorial(0)

text Keluaran

120
1

Baris return 1 if n <= 1 adalah kasus dasarnya, yang mengembalikan 1 apabila n bernilai 0 atau 1. Baris n * faktorial(n - 1) adalah kasus rekursifnya, yaitu mengalikan n dengan faktorial dari bilangan di bawahnya. Pemanggilan faktorial(5) menghasilkan 120, sedangkan pemanggilan faktorial(0) langsung jatuh ke kasus dasar tanpa rekursi sama sekali. Diagram berikut merangkum alur yang sama pada faktorial(3) dalam dua fase, yaitu fase menumpuk ketika metode terus memanggil dirinya dan fase pengembalian ketika hasil dihitung dari kasus dasar.

Dua fase rekursi pada faktorial(3)

Alur tumpukan panggilan#

Setiap pemanggilan metode menumpuk sebuah bingkai (frame) pada tumpukan panggilan (call stack), yaitu catatan internal runtime tentang metode yang sedang menunggu selesai. Pada rekursi, tumpukan tumbuh sebanyak jumlah pemanggilan yang belum selesai, lalu menyusut ketika kasus dasar tercapai dan nilai kembalian dihitung dari bawah ke atas. Kedalaman tumpukan inilah yang membedakan rekursi dari perulangan biasa, karena setiap tingkatnya menyimpan keadaan pemanggilan tersendiri.

Simulasi interaktif berikut mengikuti pemanggilan faktorial(4) langkah demi langkah. Tekan tombol Maju untuk menumpuk panggilan baru, amati saat kasus dasar tercapai, lalu lanjutkan sampai nilai 24 kembali ke pemanggil pertama. Tombol Mundur menelusuri ulang langkah sebelumnya, sedangkan tombol Ulangi mengembalikan simulasi ke keadaan awal.

Kode sumber demo

<!DOCTYPE html>
<html lang="id">
<head>
<meta charset="utf-8">
<title>Simulasi tumpukan panggilan faktorial(4)</title>
<link rel="stylesheet" href="index.css">
</head>
<body>
<main>
  <section id="panel-tumpukan">
    <h2>Tumpukan panggilan</h2>
    <div id="tumpukan"></div>
  </section>
  <section id="panel-catatan">
    <h2>Catatan langkah</h2>
    <div id="catatan"></div>
  </section>
</main>
<footer>
  <button id="maju" type="button">Maju</button>
  <button id="mundur" type="button">Mundur</button>
  <button id="ulangi" type="button">Ulangi</button>
  <span id="status"></span>
</footer>
<script src="index.js"></script>

<style>
body {
  font-family: sans-serif;
  font-size: 14px;
  color: #222;
  margin: 0;
  padding: 10px;
}

main {
  display: flex;
  gap: 12px;
}

main section {
  flex: 1;
  min-width: 0;
}

h2 {
  font-size: 13px;
  margin: 0 0 8px;
  color: #555;
  text-transform: uppercase;
  letter-spacing: 0.04em;
}

#tumpukan {
  display: flex;
  flex-direction: column;
  gap: 6px;
  min-height: 200px;
}

.bingkai {
  border: 2px solid #1a5fb4;
  border-radius: 6px;
  padding: 6px 10px;
  font-family: ui-monospace, Menlo, Consolas, monospace;
  font-size: 13px;
  background: #f4f8ff;
}

.bingkai.terbaru {
  border-color: #b02a2a;
  background: #fdeaea;
}

.bingkai .tunggu {
  color: #777;
  font-size: 12px;
  display: block;
}

#catatan {
  border: 1px solid #ddd;
  border-radius: 6px;
  padding: 8px 10px;
  min-height: 200px;
  background: #fafafa;
}

#catatan p {
  margin: 0 0 6px;
  font-size: 13px;
}

#catatan p.terkini {
  font-weight: bold;
}

footer {
  margin-top: 10px;
  display: flex;
  align-items: center;
  gap: 8px;
}

button {
  padding: 6px 14px;
  font-size: 13px;
  cursor: pointer;
}

#status {
  margin-left: auto;
  color: #666;
  font-size: 12px;
}

</style>
<style>
body {
  font-family: sans-serif;
  font-size: 14px;
  color: #222;
  margin: 0;
  padding: 10px;
}

main {
  display: flex;
  gap: 12px;
}

main section {
  flex: 1;
  min-width: 0;
}

h2 {
  font-size: 13px;
  margin: 0 0 8px;
  color: #555;
  text-transform: uppercase;
  letter-spacing: 0.04em;
}

#tumpukan {
  display: flex;
  flex-direction: column;
  gap: 6px;
  min-height: 200px;
}

.bingkai {
  border: 2px solid #1a5fb4;
  border-radius: 6px;
  padding: 6px 10px;
  font-family: ui-monospace, Menlo, Consolas, monospace;
  font-size: 13px;
  background: #f4f8ff;
}

.bingkai.terbaru {
  border-color: #b02a2a;
  background: #fdeaea;
}

.bingkai .tunggu {
  color: #777;
  font-size: 12px;
  display: block;
}

#catatan {
  border: 1px solid #ddd;
  border-radius: 6px;
  padding: 8px 10px;
  min-height: 200px;
  background: #fafafa;
}

#catatan p {
  margin: 0 0 6px;
  font-size: 13px;
}

#catatan p.terkini {
  font-weight: bold;
}

footer {
  margin-top: 10px;
  display: flex;
  align-items: center;
  gap: 8px;
}

button {
  padding: 6px 14px;
  font-size: 13px;
  cursor: pointer;
}

#status {
  margin-left: auto;
  color: #666;
  font-size: 12px;
}

</style>
<script>
// Simulasi tumpukan panggilan faktorial(4), langkah demi langkah.

// Setiap langkah memuat keadaan lengkap: isi tumpukan (dari bawah ke atas),
// catatan kejadian, dan penanda langkah selesai.
const LANGKAH = [
  { tumpukan: [], catatan: "Tumpukan kosong. Tekan Maju untuk memanggil faktorial(4).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }], catatan: "faktorial(4) dipanggil. Karena 4 > 1, kasus rekursif dijalankan: 4 × faktorial(3).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }, { n: 3, tunggu: "menunggu 3 × faktorial(2)" }], catatan: "faktorial(3) dipanggil. Karena 3 > 1, kasus rekursif dijalankan: 3 × faktorial(2).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }, { n: 3, tunggu: "menunggu 3 × faktorial(2)" }, { n: 2, tunggu: "menunggu 2 × faktorial(1)" }], catatan: "faktorial(2) dipanggil. Karena 2 > 1, kasus rekursif dijalankan: 2 × faktorial(1).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }, { n: 3, tunggu: "menunggu 3 × faktorial(2)" }, { n: 2, tunggu: "menunggu 2 × faktorial(1)" }, { n: 1, tunggu: "kasus dasar" }], catatan: "faktorial(1) dipanggil. Karena 1 <= 1, kasus dasar tercapai: kembalikan 1.", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }, { n: 3, tunggu: "menunggu 3 × faktorial(2)" }, { n: 2, tunggu: "menunggu 2 × faktorial(1)" }], catatan: "faktorial(1) selesai. Nilai 1 dikembalikan ke faktorial(2).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }, { n: 3, tunggu: "menunggu 3 × faktorial(2)" }], catatan: "faktorial(2) menghitung 2 × 1 = 2. Nilai 2 dikembalikan ke faktorial(3).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }], catatan: "faktorial(3) menghitung 3 × 2 = 6. Nilai 6 dikembalikan ke faktorial(4).", selesai: false },
  { tumpukan: [], catatan: "faktorial(4) menghitung 4 × 6 = 24. Selesai: faktorial(4) = 24 kembali ke pemanggil.", selesai: true },
];

let posisi = 0;

const elemenTumpukan = document.getElementById("tumpukan");
const elemenCatatan = document.getElementById("catatan");
const elemenStatus = document.getElementById("status");

function render() {
  const langkah = LANGKAH[posisi];

  // Bingkai terbaru berada di puncak tumpukan, sehingga digambar paling atas.
  elemenTumpukan.innerHTML = "";
  const urutanAtas = [...langkah.tumpukan].reverse();
  urutanAtas.forEach((bingkai, indeks) => {
    const div = document.createElement("div");
    div.className = "bingkai" + (indeks === 0 ? " terbaru" : "");
    div.textContent = "faktorial(" + bingkai.n + ")";
    if (bingkai.tunggu) {
      const kecil = document.createElement("span");
      kecil.className = "tunggu";
      kecil.textContent = bingkai.tunggu;
      div.appendChild(kecil);
    }
    elemenTumpukan.appendChild(div);
  });
  if (urutanAtas.length === 0) {
    elemenTumpukan.innerHTML = '<p style="color:#999;font-size:12px;">(kosong)</p>';
  }

  // Catatan menampilkan riwayat langkah sampai posisi sekarang.
  elemenCatatan.innerHTML = "";
  for (let i = 1; i <= posisi; i++) {
    const p = document.createElement("p");
    if (i === posisi) {
      p.className = "terkini";
    }
    p.textContent = LANGKAH[i].catatan;
    elemenCatatan.appendChild(p);
  }

  elemenStatus.textContent = "Langkah " + posisi + " / " + (LANGKAH.length - 1);
  document.getElementById("maju").disabled = posisi >= LANGKAH.length - 1;
  document.getElementById("mundur").disabled = posisi <= 0;
}

document.getElementById("maju").addEventListener("click", () => {
  if (posisi < LANGKAH.length - 1) {
    posisi += 1;
    render();
  }
});

document.getElementById("mundur").addEventListener("click", () => {
  if (posisi > 0) {
    posisi -= 1;
    render();
  }
});

document.getElementById("ulangi").addEventListener("click", () => {
  posisi = 0;
  render();
});

render();

</script>
<script>
// Simulasi tumpukan panggilan faktorial(4), langkah demi langkah.

// Setiap langkah memuat keadaan lengkap: isi tumpukan (dari bawah ke atas),
// catatan kejadian, dan penanda langkah selesai.
const LANGKAH = [
  { tumpukan: [], catatan: "Tumpukan kosong. Tekan Maju untuk memanggil faktorial(4).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }], catatan: "faktorial(4) dipanggil. Karena 4 > 1, kasus rekursif dijalankan: 4 × faktorial(3).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }, { n: 3, tunggu: "menunggu 3 × faktorial(2)" }], catatan: "faktorial(3) dipanggil. Karena 3 > 1, kasus rekursif dijalankan: 3 × faktorial(2).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }, { n: 3, tunggu: "menunggu 3 × faktorial(2)" }, { n: 2, tunggu: "menunggu 2 × faktorial(1)" }], catatan: "faktorial(2) dipanggil. Karena 2 > 1, kasus rekursif dijalankan: 2 × faktorial(1).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }, { n: 3, tunggu: "menunggu 3 × faktorial(2)" }, { n: 2, tunggu: "menunggu 2 × faktorial(1)" }, { n: 1, tunggu: "kasus dasar" }], catatan: "faktorial(1) dipanggil. Karena 1 <= 1, kasus dasar tercapai: kembalikan 1.", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }, { n: 3, tunggu: "menunggu 3 × faktorial(2)" }, { n: 2, tunggu: "menunggu 2 × faktorial(1)" }], catatan: "faktorial(1) selesai. Nilai 1 dikembalikan ke faktorial(2).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }, { n: 3, tunggu: "menunggu 3 × faktorial(2)" }], catatan: "faktorial(2) menghitung 2 × 1 = 2. Nilai 2 dikembalikan ke faktorial(3).", selesai: false },
  { tumpukan: [{ n: 4, tunggu: "menunggu 4 × faktorial(3)" }], catatan: "faktorial(3) menghitung 3 × 2 = 6. Nilai 6 dikembalikan ke faktorial(4).", selesai: false },
  { tumpukan: [], catatan: "faktorial(4) menghitung 4 × 6 = 24. Selesai: faktorial(4) = 24 kembali ke pemanggil.", selesai: true },
];

let posisi = 0;

const elemenTumpukan = document.getElementById("tumpukan");
const elemenCatatan = document.getElementById("catatan");
const elemenStatus = document.getElementById("status");

function render() {
  const langkah = LANGKAH[posisi];

  // Bingkai terbaru berada di puncak tumpukan, sehingga digambar paling atas.
  elemenTumpukan.innerHTML = "";
  const urutanAtas = [...langkah.tumpukan].reverse();
  urutanAtas.forEach((bingkai, indeks) => {
    const div = document.createElement("div");
    div.className = "bingkai" + (indeks === 0 ? " terbaru" : "");
    div.textContent = "faktorial(" + bingkai.n + ")";
    if (bingkai.tunggu) {
      const kecil = document.createElement("span");
      kecil.className = "tunggu";
      kecil.textContent = bingkai.tunggu;
      div.appendChild(kecil);
    }
    elemenTumpukan.appendChild(div);
  });
  if (urutanAtas.length === 0) {
    elemenTumpukan.innerHTML = '<p style="color:#999;font-size:12px;">(kosong)</p>';
  }

  // Catatan menampilkan riwayat langkah sampai posisi sekarang.
  elemenCatatan.innerHTML = "";
  for (let i = 1; i <= posisi; i++) {
    const p = document.createElement("p");
    if (i === posisi) {
      p.className = "terkini";
    }
    p.textContent = LANGKAH[i].catatan;
    elemenCatatan.appendChild(p);
  }

  elemenStatus.textContent = "Langkah " + posisi + " / " + (LANGKAH.length - 1);
  document.getElementById("maju").disabled = posisi >= LANGKAH.length - 1;
  document.getElementById("mundur").disabled = posisi <= 0;
}

document.getElementById("maju").addEventListener("click", () => {
  if (posisi < LANGKAH.length - 1) {
    posisi += 1;
    render();
  }
});

document.getElementById("mundur").addEventListener("click", () => {
  if (posisi > 0) {
    posisi -= 1;
    render();
  }
});

document.getElementById("ulangi").addEventListener("click", () => {
  posisi = 0;
  render();
});

render();

</script></body>
</html>

Bingkai yang tersorot merah pada simulasi adalah pemanggilan terbaru, yaitu tingkat tempat perhitungan berikutnya akan terjadi. Pada program nyata, kedalaman tumpukan terbatas oleh memori, sehingga rekursi yang terlalu dalam akan berhenti dengan error sebagaimana ditunjukkan pada bagian kesalahan umum.

Fibonacci dan biaya rekursi#

Deret Fibonacci menyusun bilangan berikutnya dari dua bilangan sebelumnya, sehingga definisinya cocok ditulis secara rekursif. Kasus dasarnya adalah dua nilai pertama deret, sedangkan kasus rekursifnya menjumlahkan dua pemanggilan sekaligus.

ruby fibonacci.rb

# Deret Fibonacci secara rekursif

def fibonacci(n)
  return n if n <= 1

  fibonacci(n - 1) + fibonacci(n - 2)
end

p fibonacci(10)

text Keluaran

Pemanggilan fibonacci(10) menghasilkan 55, yaitu suku kesepuluh deret dengan penomoran dari nol. Perhatikan bentuk pemanggilannya, misalnya satu panggilan fibonacci(5) memanggil fibonacci(4) dan fibonacci(3), lalu masing-masing memanggil dua panggilan lagi, sehingga jumlah pemanggilan tumbuh kira-kira dua kali lipat setiap n naik satu. Nilai yang sama dihitung berulang kali di banyak cabang, dan penghitungan ulang inilah biaya bawaan rekursi naif.

Untuk n kecil, biaya tersebut tidak terasa, tetapi pemanggilan fibonacci(40) sudah memerlukan waktu yang terasa karena ratusan juta pemanggilan terjadi dan banyak di antaranya menghitung ulang nilai yang sama. Teknik menyimpan hasil yang pernah dihitung disebut memoization dan menjadi salah satu perbaikan yang umum. Perbaikan lain adalah menyusun ulang algoritma menjadi versi perulangan biasa, yang menghemat tumpukan panggilan sekaligus menghilangkan penghitungan ulang.

Kesalahan umum#

Kesalahan paling umum pada rekursi adalah kasus dasar yang hilang atau tidak pernah tercapai. Program berikut memanggil metode yang tidak punya kasus dasar sama sekali, sehingga pemanggilan baru terus menumpuk sampai tumpukan panggilan habis dan Ruby menghentikan program dengan error SystemStackError.

ruby Berkas tanpa_dasar.rb

# tidak-dijalankan

def turun(n)
  turun(n + 1)
end

turun(1)

Baris pertama berupa catatan, bukan bagian program. Menjalankan berkas tersebut dari terminal menghasilkan traceback, yaitu laporan rantai pemanggilan pada saat error terjadi, sebagaimana diperlihatkan pada keluaran berikut. Jumlah level di tengah laporan dapat berbeda dari satu mesin ke mesin lain karena bergantung pada batas tumpukan masing-masing sistem.

bash

# menjalankan berkas rekursi tanpa kasus dasar
ruby tanpa_dasar.rb

text Keluaran

tanpa_dasar.rb:2:in 'Object#turun': stack level too deep (SystemStackError)
	from tanpa_dasar.rb:2:in 'Object#turun'
	from tanpa_dasar.rb:2:in 'Object#turun'
	from tanpa_dasar.rb:2:in 'Object#turun'
	from tanpa_dasar.rb:2:in 'Object#turun'
	from tanpa_dasar.rb:2:in 'Object#turun'
	from tanpa_dasar.rb:2:in 'Object#turun'
	from tanpa_dasar.rb:2:in 'Object#turun'
	from tanpa_dasar.rb:2:in 'Object#turun'
	 ... 10908 levels...
	from tanpa_dasar.rb:2:in 'Object#turun'
	from tanpa_dasar.rb:2:in 'Object#turun'
	from tanpa_dasar.rb:2:in 'Object#turun'
	from tanpa_dasar.rb:5:in '<main>'

Pesan stack level too deep berarti tumpukan panggilan habis sebelum kasus dasar tercapai. Perbaikannya, pastikan setiap jalur eksekusi berakhir di kasus dasar, terutama dengan memeriksa bahwa masukan benar-benar mengecil pada setiap pemanggilan. Kesalahan lain yang lazim adalah kasus dasar n == 0 yang tidak pernah tercapai karena metode mengurangi masukannya dengan dua, sehingga masukan bernilai ganjil melewati nol tanpa pernah menyentuhnya. Kasus dasar yang aman ditulis sebagai n <= 1, sebagaimana contoh faktorial dan Fibonacci di atas.

Ringkasan#

Rekursi memecah masalah dengan metode yang memanggil dirinya sendiri pada masukan yang lebih kecil.
Kasus dasar menjawab tanpa rekursi, sedangkan kasus rekursif memanggil dirinya dengan masukan yang mendekati kasus dasar.
Setiap pemanggilan menumpuk sebuah bingkai pada tumpukan panggilan, yang menyusut ketika nilai kembali dari kasus dasar.
Kasus dasar yang hilang berujung pada error SystemStackError, dan rekursi naif Fibonacci tumbuh eksponensial.

Referensi#

SystemStackError — Dokumentasi Ruby 3.4 — Kelas error yang dimunculkan ketika tumpukan panggilan habis, termasuk kedudukannya di bawah Exception.