Python - Rekursi: Panduan untuk Pemula

Halo sobat masa depan yang akan menjadi ahli Python! Hari ini, kita akan memulai perjalanan yang menarik ke dalam dunia rekursi. Jangan khawatir jika ini terdengar agak menakutkan - saya berjanji akan membuat ini menyenangkan dan mudah dipahami. Jadi, ambil minuman kesukaan Anda, Duduklah dengan nyaman, dan mari kita melompat!

Apa itu Rekursi?

Bayangkan Anda berdiri di antara dua cermin yang berhadapan satu sama lain. Anda melihat banyak refleksi tak terhingga, kan? Itu sedikit seperti rekursi dalam pemrograman! Dalam istilah sederhana, rekursi adalah ketika sebuah fungsi memanggil dirinya sendiri untuk mengatasai masalah.

Mari kita mulai dengan contoh sederhana:

def countdown(n):
if n <= 0:
print("Blastoff!")
else:
print(n)
countdown(n - 1)

countdown(5)

Jika Anda menjalankan kode ini, Anda akan melihat:

5
4
3
2
1
Blastoff!

Sekarang, mari kita pecahkan ini:

1. Kita mendefinisikan fungsi bernama countdown yang mengambil sebuah angka n.
2. Jika n adalah 0 atau kurang, kita mencetak "Blastoff!"
3. Jika tidak, kita mencetak n dan kemudian memanggil countdown lagi dengan n - 1.

Itu adalah rekursi dalam aksi! Fungsi terus memanggil dirinya sendiri dengan angka yang lebih kecil sampai mencapai nol.

Komponen Rekursi

Setiap fungsi rekursif memiliki dua komponen utama:

1. kasus dasar : Ini adalah kondisi yang menghentikan rekursi.
2. kasus rekursif : Ini adalah tempat fungsi memanggil dirinya sendiri.

Dalam contoh countdown kita:

• Kasus dasar adalah if n <= 0
• Kasus rekursif adalah countdown(n - 1)

Mari kita lihat contoh klasik lainnya: menghitung faktorial.

def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)

print(factorial(5))  # Output: 120

Ini adalah yang terjadi:

1. Jika n adalah 0 atau 1, kita kembali ke 1 (ini adalah kasus dasar kita).
2. Jika tidak, kita kali n dengan faktorial n - 1 (ini adalah kasus rekursif kita).

Jadi, factorial(5) menjadi: 5 factorial(4) 5 (4 factorial(3)) 5 (4 (3 factorial(2))) 5 (4 (3 (2 factorial(1)))) 5 (4 (3 (2 1))) 5 4 3 2 1 = 120

Kekuatan Rekursi

Rekursi dapat membuat beberapa masalah kompleks menjadi lebih mudah untuk dipecahkan. Mari kita lihat contoh yang sedikit lebih lanjut: urutan Fibonacci.

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

for i in range(10):
print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34

Fungsi ini menghitung angka Fibonacci ke-n. Urutan Fibonacci dimulai dengan 0 dan 1, dan setiap angka berikutnya adalah jumlah dari dua angka sebelumnya.

Pencarian Binari Menggunakan Rekursi

Sekarang, mari kita tangani contoh yang lebih praktis: pencarian binari. Ini adalah cara efisien untuk menemukan item di daftar yang diurutkan.

def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2

if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1

arr = [2, 3, 4, 10, 40]
x = 10

result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:
print(f"Elemen ada di indeks {result}")
else:
print("Elemen tidak ada di dalam array")

Fungsi ini bekerja dengan secara berulang menghitung interval pencarian menjadi dua. Jika nilai kunci pencarian lebih kecil daripada item di tengah interval, perkecil interval ke bagian bawah. Jika tidak, perkecil ke bagian atas. Ulangi pengecekan sampai nilai ditemukan atau interval kosong.

Kapan Harus Menggunakan Rekursi

Rekursi sangat berguna untuk:

1. Masalah yang dapat dipecahkan menjadi sub-masalah yang sama
2. Struktur data seperti pohon (misalnya, sistem berkas, HTML DOM)
3. Algoritma seperti QuickSort, MergeSort, dll.

Namun, rekursi tidak selalu adalah solusi terbaik. Rekursi yang sangat dalam dapat memakan banyak memori, dan terkadang loop yang sederhana dapat lebih efisien dan lebih mudah dipahami.

Tabel Metode Rekursi

Metode	Deskripsi	Contoh
Rekursi Langsung	Sebuah fungsi memanggil dirinya sendiri secara langsung	Contoh countdown dan factorial kita
Rekursi Tak Langsung	Fungsi A memanggil fungsi B, yang kemudian memanggil fungsi A	Lihat contoh di bawah
Rekursi Ekor	Panggilan rekursif adalah yang terakhir dieksekusi oleh fungsi	Contoh countdown kita
Rekursi Non-Ekor	Panggilan rekursif bukan yang terakhir dieksekusi oleh fungsi	Contoh factorial kita

Berikut adalah contoh rekursi tak langsung:

def is_even(n):
if n == 0:
return True
else:
return is_odd(n - 1)

def is_odd(n):
return not is_even(n)

print(is_even(4))  # Output: True
print(is_odd(4))   # Output: False

Dalam contoh ini, is_even memanggil is_odd, yang kemudian memanggil is_even.

Kesimpulan

Selamat! Anda baru saja mengambil langkah pertama Anda ke dalam dunia rekursi yang menarik. Ingat, seperti setiap alat yang kuat, rekursi harus digunakan dengan bijak. Rekursi dapat membuat kode Anda lebih elegan dan mengatasi masalah kompleks dengan mudah, tetapi juga dapat membuat masalah sederhana menjadi terlalu rumit.

Sebagai Anda melanjutkan perjalanan Python Anda, Anda akan menemukan banyak situasi di mana rekursi dapat diterapkan. Terus latih dan segera Anda akan rekursus seperti ahli!

Credits: Image by storyset