Python - Rekursi: Panduan untuk Pemula

Helo di sana, ahli penyihir Python masa depan! Hari ini, kita akan melakukan perjalanan yang menarik ke dunia rekursi. Jangan khawatir jika ia terdengar agak menakutkan – saya janji kita akan membuatnya menyenangkan dan mudah untuk dipahami. Jadi, ambil minuman kesukaan anda, dapatkan keselesaan, dan mari kita melompat masuk!

Apa itu Rekursi?

Bayangkan anda berdiri di antara dua cermin yang menghadap satu sama lain. Anda melihat banyak refleksi tak terhingga, kan? Itu adalah agak seperti rekursi dalam pemrograman! Dalam perkataan ringkas, rekursi adalah apabila fungsi memanggil dirinya sendiri untuk menjawab masalah.

Mari kita mulai dengan contoh yang sederhana:

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

countdown(5)

Jika anda menjalankan kod ini, anda akan lihat:

5
4
3
2
1
Blastoff!

Sekarang, mari kita pecahkan ini:

1. Kita definisikan fungsi yang dipanggil countdown yang mengambil angka n.
2. Jika n adalah 0 atau kurang, kita cetak "Blastoff!"
3. Jika tidak, kita cetak n dan kemudian panggil countdown lagi dengan n - 1.

Ini adalah rekursi dalam tindakan! Fungsi terus memanggil dirinya sendiri dengan angka yang lebih kecil sampai ia 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 lihat contoh klasik lain: menghitung faktorial.

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

print(factorial(5))  # Output: 120

Berikut ini adalah yang terjadi:

1. Jika n adalah 0 atau 1, kita kembalikan 1 (ini adalah kasus dasar kita).
2. Jika tidak, kita kalikan 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 lihat contoh yang sedikit lebih tingkat: 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 yang efisien untuk menemukan item dalam 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 hadir di indeks {result}")
else:
print("Elemen tidak hadir dalam array")

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

Kapan untuk Menggunakan Rekursi

Rekursi adalah sangat berguna untuk:

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

Namun, rekursi tidak selalu adalah solusi terbaik. Ia dapat membebani memori untuk rekursi yang sangat dalam, dan kadang-kadang loop yang sederhana dapat lebih efisien dan lebih mudah untuk dipahami.

Tabel Metode Rekursi

Method	Description	Example
Rekursi Langsung	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 Bukan 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 dunia rekursi yang menarik. Ingat, seperti setiap alat yang kuat, rekursi harus digunakan dengan bijak. Ia dapat membuat kode anda lebih elegan dan menjawab masalah kompleks dengan mudah, tetapi juga dapat membuat masalah sederhana menjadi terlalu rumit secara tidak perlu.

Sebagai anda terus menjalankan perjalanan Python anda, anda akan bertemu banyak situasi di mana rekursi dapat diterapkan. Terus latihan, dan tidak lama lagi anda akan rekursing seperti pro!

Credits: Image by storyset