Rekursi (Recursion)
Terakhir diperbarui
Rekursi adalah fungsi yang memanggil dirinya sendiri pada versi yang lebih kecil dari masalah yang sama, sampai mencapai kasus yang cukup kecil untuk dijawab secara langsung. Kasus yang bisa dijawab langsung itu disebut base case, dan setiap fungsi rekursif membutuhkannya: fib(n) terus bercabang menjadi fib(n - 1) dan fib(n - 2) sampai mencapai fib(1) atau fib(0), yang langsung mengembalikan dirinya sendiri. Visualisasi di atas menjalankan persis hal ini: tekan Putar dan lihat pemanggilan bercabang menjadi pohon, mencapai base case di leaf, lalu mengembalikan nilainya ke atas dan digabungkan di setiap level.
Hal kedua yang ditampilkan animasi adalah call stack: setiap pemanggilan yang sudah dimulai tetapi belum kembali. Stack bertambah saat pemanggilan makin dalam, mencapai puncaknya di kedalaman rekursi, lalu mengurai saat hasil kembali. Itulah sebabnya rekursi yang dalam bisa terkena stack overflow, sedangkan loop iteratif tidak pernah menambah stack. Bentuk pemanggilan yang sama menggerakkan depth-first search, merge sort, dan sebagian besar operasi pada binary tree.
Kompleksitas waktu dan ruang
Untuk Fibonacci rekursif naif yang ditampilkan di atas, dan dua perbaikan standarnya:
| Pendekatan | Waktu | Ruang | Catatan |
|---|---|---|---|
| Rekursi naif | O(2^n) | O(n) | Pohon pemanggilan berlipat dua di setiap level; ruangnya adalah stack terdalam, bukan seluruh pohon. |
| Dengan memoization | O(n) | O(n) | Setiap fib(k) dihitung sekali lalu disimpan; subtree yang berulang menyusut menjadi pencarian di cache. |
| Loop iteratif | O(n) | O(1) | Dua variabel yang terus diperbarui menggantikan stack sepenuhnya. |
| Rekursi apa pun, secara umum | jumlah pemanggilan × kerja per pemanggilan | O(max depth) | Stack menyimpan satu frame per pemanggilan yang sudah dimulai tetapi belum kembali. |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Pemanggilan pertama fib(n) masuk ke call stack. |
| 2 | Pemanggilan itu butuh fib(n - 1), jadi pemanggilan itu juga masuk ke stack; induknya menunggu. |
| 3 | Pemanggilan terus bersarang sampai ada yang menanyakan n <= 1: base case langsung menjawab, tanpa pemanggilan yang lebih dalam. |
| 4 | Nilai dari base case kembali ke induknya, yang sekarang boleh memulai pemanggilan keduanya, fib(n - 2). |
| 5 | Saat kedua anaknya sudah kembali, induk menjumlahkan keduanya lalu ikut kembali; frame-nya keluar dari stack. |
| 6 | Proses kembali ini berulang ke atas pohon sampai frame pemanggilan pertama keluar dengan jawaban akhir dan stack kosong. |
Contoh penerapan
Mengevaluasi fib(4) sesuai urutan pemanggilan yang persis, seperti yang diputar animasi:
| Pemanggilan | Stack saat itu | Mengembalikan |
|---|---|---|
fib(4) | fib(4) | menunggu anak-anaknya |
fib(3) | fib(4) > fib(3) | menunggu anak-anaknya |
fib(2) | fib(4) > fib(3) > fib(2) | menunggu anak-anaknya |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (base case) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (base case) |
fib(2) menggabungkan | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (base case) |
fib(3) menggabungkan | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) lagi | fib(4) > fib(2) | 1, dihitung ulang dari awal |
fib(4) menggabungkan | fib(4) | 2 + 1 = 3 |
Kapan memakai rekursi
| Pakai saat | Hindari saat |
|---|---|
| Masalahnya mirip dengan dirinya sendiri: pohon, struktur bersarang, divide and conquer | Loop sederhana bisa menyatakan hal yang sama tanpa frame stack |
Kedalamannya terbatas dan wajar, seperti O(log n) pada merge sort | Kedalamannya bisa mencapai ukuran input pada input yang sangat besar, sehingga berisiko stack overflow |
| Backtracking butuh stack untuk mengingat tempat melanjutkan | Submasalah yang sama berulang dan kamu tidak menyimpannya di cache |
| Versi rekursifnya jelas lebih mudah dibaca dan diverifikasi | Kamu berada di loop yang sangat sering dijalankan, di mana beban pemanggilan fungsi terasa nyata |
Kode Recursion
Implementasi Recursion yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Recursion dalam Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)Kode Recursion dalam JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Kode Recursion dalam Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}Kode Recursion dalam C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}Kode Recursion dalam C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}FAQ Rekursi
Apa itu base case pada rekursi?
fib(n), base case-nya adalah n <= 1, yang langsung mengembalikan n. Tanpa base case yang bisa dicapai, pemanggilan tidak pernah berhenti, stack terus bertambah, dan program crash karena stack overflow.Apa itu call stack dan mengapa penting?
n level memakai memori O(n) meskipun setiap pemanggilan hampir tidak melakukan apa-apa. Deretan chip di bawah animasi menampilkan persis stack ini bertambah dan mengurai.Mengapa Fibonacci rekursif butuh waktu eksponensial?
fib(2) dievaluasi dua kali di dalam fib(4), dan duplikasinya kira-kira berlipat dua di setiap level, sehingga menghasilkan O(2^n) pemanggilan. Menyimpan setiap hasil saat pertama kali dihitung, yang disebut memoization, menyusutkan pohonnya menjadi O(n).Apakah rekursi lebih baik daripada iterasi?
Apa penyebab stack overflow pada fungsi rekursif?
Bisa karena base case tidak ada atau tidak bisa dicapai, sehingga pemanggilan tidak pernah berhenti, atau karena rekursi yang benar tetapi kedalamannya terlalu besar untuk batas stack runtime, seperti berekursi sekali per elemen pada input berisi jutaan elemen. Solusinya adalah memastikan base case tercapai, membatasi kedalaman, atau mengubahnya menjadi iterasi.
Algoritma apa saja yang secara alami bersifat rekursif?
Sumber terkait
Visualisasi lainnya
