Fungsi rekursif adalah salah satu konsep fundamental dalam algoritma pemrograman lanjut yang memungkinkan sebuah fungsi memanggil dirinya sendiri. Konsep ini sangat powerful untuk menyelesaikan masalah yang dapat dipecah menjadi sub-masalah yang lebih kecil dengan pola yang sama.
Dalam artikel ini, kita akan mempelajari berbagai contoh fungsi rekursif mulai dari yang sederhana hingga kompleks, lengkap dengan implementasi dan analisis kompleksitasnya.
Konsep Dasar Rekursi
Komponen Rekursi
- Base Case: Kondisi berhenti
- Recursive Case: Pemanggilan diri sendiri
- Progress: Menuju base case
- Return Value: Nilai kembalian
Keuntungan Rekursi
- Kode lebih bersih dan elegant
- Mudah memahami logika
- Natural untuk masalah tertentu
- Implementasi algoritma divide-conquer
⚠️ Perhatian Penting
Rekursi tanpa base case yang tepat akan menyebabkan stack overflow. Selalu pastikan ada kondisi yang membuat rekursi berhenti!
Visualisasi Rekursi – Faktorial
factorial(4) = 4 × factorial(3)
factorial(3) = 3 × factorial(2)
factorial(2) = 2 × factorial(1)
factorial(1) = 1 × factorial(0)
factorial(0) = 1 (Base Case)
Contoh 1: Faktorial
Faktorial adalah contoh klasik rekursi. n! = n × (n-1)! dengan base case 0! = 1.
Python – Faktorial:
def faktorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case
return n * faktorial(n - 1)
# Contoh penggunaan
print(f"5! = {faktorial(5)}") # Output: 120
print(f"0! = {faktorial(0)}") # Output: 1
# Trace eksekusi faktorial(4):
# faktorial(4) = 4 * faktorial(3)
# faktorial(3) = 3 * faktorial(2)
# faktorial(2) = 2 * faktorial(1)
# faktorial(1) = 1 (base case)
# Hasil: 4 * 3 * 2 * 1 = 24
JavaScript – Faktorial:
function faktorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * faktorial(n - 1);
}
// Contoh penggunaan
console.log(`5! = ${faktorial(5)}`); // Output: 120
console.log(`3! = ${faktorial(3)}`); // Output: 6Contoh 2: Fibonacci
Deret Fibonacci adalah contoh rekursi dengan dua pemanggilan rekursif. Untuk memahami lebih dalam tentang optimasi algoritma rekursif, mari lihat implementasi dan optimasinya.
Fibonacci Dasar (Tidak Efisien):
def fibonacci(n):
# Base cases
if n <= 1:
return n
# Recursive case
return fibonacci(n - 1) + fibonacci(n - 2)
# Contoh penggunaan
for i in range(10):
print(f"F({i}) = {fibonacci(i)}")
# Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
Fibonacci dengan Memoization (Efisien):
def fibonacci_memo(n, memo={}):
# Cek apakah sudah dihitung sebelumnya
if n in memo:
return memo[n]
# Base cases
if n <= 1:
return n
# Hitung dan simpan hasil
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
# Contoh penggunaan
print(f"F(50) = {fibonacci_memo(50)}") # Sangat cepat!📊 Perbandingan Kompleksitas
- Fibonacci Dasar: O(2^n) – Exponential time
- Fibonacci Memoization: O(n) – Linear time
- Space Complexity: O(n) untuk menyimpan memo
Contoh 3: Binary Search
Binary search adalah algoritma pencarian yang sangat efisien menggunakan pendekatan divide-and-conquer dengan rekursi.
Binary Search Rekursif:
def binary_search(arr, target, left=0, right=None):
if right is None:
right = len(arr) - 1
# Base case: element tidak ditemukan
if left > right:
return -1
# Hitung middle index
mid = (left + right) // 2
# Base case: element ditemukan
if arr[mid] == target:
return mid
# Recursive cases
if target < arr[mid]:
return binary_search(arr, target, left, mid - 1)
else:
return binary_search(arr, target, mid + 1, right)
# Contoh penggunaan
data = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7
result = binary_search(data, target)
if result != -1:
print(f"Element {target} ditemukan di index {result}")
else:
print(f"Element {target} tidak ditemukan")Contoh 4: Tree Traversal
Rekursi sangat natural untuk operasi pada struktur data tree. Untuk pemahaman yang lebih mendalam tentang struktur data tree dan graph, mari lihat implementasi traversal.
Tree Node dan Traversal:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_traversal(root):
"""Left -> Root -> Right"""
if root is None:
return []
result = []
result.extend(inorder_traversal(root.left)) # Left
result.append(root.val) # Root
result.extend(inorder_traversal(root.right)) # Right
return result
def preorder_traversal(root):
"""Root -> Left -> Right"""
if root is None:
return []
result = []
result.append(root.val) # Root
result.extend(preorder_traversal(root.left)) # Left
result.extend(preorder_traversal(root.right)) # Right
return result
def postorder_traversal(root):
"""Left -> Right -> Root"""
if root is None:
return []
result = []
result.extend(postorder_traversal(root.left)) # Left
result.extend(postorder_traversal(root.right)) # Right
result.append(root.val) # Root
return result
# Contoh penggunaan
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print("Inorder:", inorder_traversal(root)) # [4, 2, 5, 1, 3]
print("Preorder:", preorder_traversal(root)) # [1, 2, 4, 5, 3]
print("Postorder:", postorder_traversal(root)) # [4, 5, 2, 3, 1]Contoh 5: Permutasi dan Kombinasi
Rekursi sangat powerful untuk generating permutasi dan kombinasi dari suatu set data.
Generate Permutations:
def generate_permutations(arr):
# Base case
if len(arr) <= 1:
return [arr]
result = []
for i in range(len(arr)):
# Ambil element saat ini
current = arr[i]
# Sisa elements
remaining = arr[:i] + arr[i+1:]
# Generate permutations dari sisa elements
for perm in generate_permutations(remaining):
result.append([current] + perm)
return result
# Contoh penggunaan
data = [1, 2, 3]
perms = generate_permutations(data)
print("Permutations:")
for perm in perms:
print(perm)
# Output:
# [1, 2, 3], [1, 3, 2], [2, 1, 3],
# [2, 3, 1], [3, 1, 2], [3, 2, 1]
Generate Combinations:
def generate_combinations(arr, r):
# Base cases
if r == 0:
return [[]]
if len(arr) < r:
return []
result = []
# Include first element
first = arr[0]
rest = arr[1:]
# Combinations yang include first element
for combo in generate_combinations(rest, r - 1):
result.append([first] + combo)
# Combinations yang tidak include first element
result.extend(generate_combinations(rest, r))
return result
# Contoh penggunaan
data = [1, 2, 3, 4]
combos = generate_combinations(data, 2)
print("Combinations (r=2):")
for combo in combos:
print(combo)
# Output: [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]Best Practices dan Tips
✅ Do’s (Yang Harus Dilakukan)
- Selalu definisikan base case yang jelas
- Pastikan setiap recursive call menuju base case
- Gunakan memoization untuk optimasi jika diperlukan
- Pertimbangkan iterative solution untuk deep recursion
- Test dengan input edge cases (0, 1, negative numbers)
❌ Don’ts (Yang Harus Dihindari)
- Jangan lupakan base case (menyebabkan infinite recursion)
- Hindari rekursi yang terlalu dalam (stack overflow)
- Jangan gunakan rekursi untuk masalah yang lebih efisien dengan iterasi
- Hindari duplicate computation tanpa memoization
- Jangan abaikan space complexity dari call stack
Analisis Kompleksitas
| Algoritma | Time Complexity | Space Complexity | Catatan |
|---|---|---|---|
| Faktorial | O(n) | O(n) | Linear recursion |
| Fibonacci (basic) | O(2^n) | O(n) | Exponential – tidak efisien |
| Fibonacci (memo) | O(n) | O(n) | Dengan memoization |
| Binary Search | O(log n) | O(log n) | Divide and conquer |
| Tree Traversal | O(n) | O(h) | h = height of tree |
Frequently Asked Questions (FAQ)
Kapan sebaiknya menggunakan rekursi dibanding iterasi?
Gunakan rekursi ketika masalah memiliki struktur rekursif natural (seperti tree traversal, divide-conquer), atau ketika solusi rekursif lebih mudah dipahami. Gunakan iterasi untuk masalah sederhana atau ketika performance dan memory usage menjadi concern utama.
Apa itu tail recursion dan mengapa penting?
Tail recursion adalah rekursi dimana pemanggilan rekursif adalah operasi terakhir dalam fungsi. Beberapa compiler dapat mengoptimasi tail recursion menjadi loop, sehingga menghemat stack space. Namun Python tidak melakukan optimasi ini secara default.
Bagaimana cara menghindari stack overflow dalam rekursi?
Beberapa cara: 1) Pastikan base case yang benar, 2) Gunakan iterasi untuk deep recursion, 3) Implementasi trampolines atau continuation-passing style, 4) Increase stack limit (tidak direkomendasikan), 5) Gunakan memoization untuk mengurangi depth.
Apa perbedaan direct dan indirect recursion?
Direct recursion: fungsi memanggil dirinya sendiri langsung (seperti factorial). Indirect recursion: fungsi A memanggil fungsi B, dan fungsi B memanggil kembali fungsi A. Indirect recursion lebih kompleks dan sulit di-debug.
Bagaimana cara mengkonversi rekursi menjadi iterasi?
Gunakan stack atau queue eksplisit untuk menyimpan state yang biasanya disimpan di call stack. Untuk tail recursion, bisa langsung dikonversi ke loop. Untuk rekursi yang lebih kompleks, perlu simulate call stack dengan data structure.
Kesimpulan
Fungsi rekursif adalah tool yang powerful dalam pemrograman, terutama untuk masalah yang memiliki struktur rekursif natural. Dengan memahami konsep base case, recursive case, dan optimasi seperti memoization, Anda dapat mengimplementasikan solusi yang elegant dan efisien.
Praktik yang konsisten dengan berbagai contoh rekursi akan meningkatkan kemampuan problem-solving dan pemahaman algoritma yang lebih mendalam. Ingat untuk selalu mempertimbangkan trade-off antara readability dan performance.