Rekursi

Memindahkan Menara Hanoi berisi 64 cakram butuh 18 446 744 073 709 551 615 gerakan; fungsi rekursif menjelaskan penyelesaiannya dalam empat baris.

Fungsi yang memanggil dirinya sendiri

Beberapa masalah mengandung salinan dirinya yang lebih kecil. Faktorial dari 5, ditulis 5!, adalah 5 × 4 × 3 × 2 × 1 = 120. Lihat sekali lagi: itu sama dengan 5 × (4 × 3 × 2 × 1), yaitu 5 × 4!. Secara umum n! = n × (n − 1)!, jadi untuk menghitung faktorial kamu bisa menghitung faktorial yang lebih kecil lalu mengalikannya. Fungsi yang menyelesaikan masalah dengan memanggil dirinya sendiri pada versi yang lebih kecil disebut rekursif.

function factorial(n) {
  if (n <= 1) return 1;          // kasus dasar: berhenti di sini
  return n * factorial(n - 1);   // kasus rekursif: masalah yang lebih kecil
}
console.log(factorial(5)); // 120

Setiap fungsi rekursif butuh dua bagian. Kasus dasar adalah masukan yang cukup kecil untuk langsung dijawab, tanpa pemanggilan lagi: di sini, faktorial dari 1 adalah 1. Kasus rekursif memperkecil masalahnya dan memanggil fungsi itu lagi. Setiap pemanggilan harus makin dekat ke kasus dasar. Kalau tidak, misalnya kalau kamu tidak sengaja menulis factorial(n + 1), pemanggilannya tidak pernah berakhir.

Tumpukan pemanggilan (call stack)

Bagaimana komputer mencatat semua pemanggilan yang belum selesai itu? Saat factorial(5) berjalan, ia sampai di 5 * factorial(4) dan harus menunggu jawabannya. Komputer menaruh pemanggilan yang menunggu itu di tumpukan (stack), yaitu timbunan tempat benda yang terakhir ditaruh menjadi yang pertama diambil. factorial(4) menunggu factorial(3), dan seterusnya sampai factorial(1), yang langsung mengembalikan 1. Lalu tumpukan itu terurai: factorial(2) mengembalikan 2, factorial(3) mengembalikan 6, factorial(4) mengembalikan 24, dan factorial(5) mengembalikan 120.

Ukuran tumpukan itu terbatas. Rekursi yang tidak pernah mencapai kasus dasarnya terus menambah pemanggilan sampai ruangnya habis, dan JavaScript berhenti dengan galat; di Chrome dan Node.js pesannya "RangeError: Maximum call stack size exceeded". Batas yang sama berarti rekursi yang sangat dalam, ratusan ribu tingkat, lebih baik ditulis sebagai perulangan.

Menara Hanoi

Menara Hanoi adalah teka-teki yang diterbitkan matematikawan Prancis Édouard Lucas pada 1883. Ada tiga tiang dan setumpuk cakram berbeda ukuran di tiang pertama, yang terbesar di paling bawah. Tujuannya memindahkan seluruh tumpukan ke tiang ketiga. Kamu hanya boleh memindahkan satu cakram setiap kali, hanya cakram teratas di sebuah tiang, dan tidak pernah menaruh cakram yang lebih besar di atas cakram yang lebih kecil.

Memikirkan langkah demi langkah ke mana setiap cakram pergi cepat membingungkan. Berpikir secara rekursif membuatnya singkat. Untuk memindahkan n cakram dari A ke C: pertama, pindahkan n − 1 cakram teratas ke samping, dari A ke B. Lalu pindahkan cakram terbesar dari A ke C. Lalu pindahkan n − 1 cakram dari B ke atasnya di C. Memindahkan n − 1 cakram adalah teka-teki yang sama, satu ukuran lebih kecil, dan memindahkan satu cakram adalah kasus dasarnya. Untuk 3 cakram ini menghasilkan 7 gerakan; laboratorium menunjukkan tumpukan pemanggilan yang menunggu di setiap gerakan.

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7 gerakan

Berapa gerakan yang dibutuhkan n cakram? Memindahkan n cakram memakan dua kali pemindahan n − 1 cakram ditambah satu: M(n) = 2M(n − 1) + 1, dengan M(1) = 1. Hasilnya 1, 3, 7, 15, 31, jadi M(n) = 2ⁿ − 1, dan tidak ada penyelesaian yang bisa memakai lebih sedikit gerakan. Sepuluh cakram butuh 1023 gerakan. Enam puluh empat cakram butuh 2⁶⁴ − 1 = 18 446 744 073 709 551 615 gerakan; dengan satu gerakan per detik, itu sekitar 585 miliar tahun. Inilah pertumbuhan O(2ⁿ) dari unit sebelumnya.

Rekursi, perulangan, dan pekerjaan berulang

Apa pun yang ditulis dengan rekursi bisa ditulis dengan perulangan dan tumpukan buatan sendiri, dan kasus sederhana seperti faktorial sering lebih jelas sebagai perulangan. Rekursi unggul ketika masalahnya sendiri berbentuk seperti pohon: memecah daftar dalam merge sort, menjelajahi folder di dalam folder, atau mencari jalan di labirin, yang menjadi topik unit terakhir. Satu jebakannya adalah pekerjaan berulang. Bilangan Fibonacci 0, 1, 1, 2, 3, 5, 8, … mengikuti fib(n) = fib(n − 1) + fib(n − 2). Jika ditulis langsung sebagai rekursi, fib(10) = 55 melakukan 177 pemanggilan, fib(20) melakukan 21 891, dan fib(30) melakukan 2 692 537, karena nilai-nilai kecil yang sama dihitung berulang-ulang. Mengingat jawaban yang sudah ditemukan, atau membangun dari bawah dengan perulangan, menghilangkan pemborosan itu.