Pernahkah Anda terjebak dalam siklus yang tampaknya tak berujung di mana masalah terus bercabang menjadi fragmen yang lebih kecil?
Jika demikian, Anda mungkin telah menemukan dunia rekursi yang memikat. Meskipun tampaknya sulit untuk dipahami, jangan khawatir! Dalam postingan ini, kita akan melakukan perjalanan yang menarik untuk mempelajari tentang jenis-jenis rekursi.
Jadi bersiaplah saat kami menjelajahi berbagai pendekatan rekursif. Bersiaplah untuk memasuki dunia rekursi yang menarik dan amati kemampuannya yang luar biasa dalam memecahkan masalah yang rumit.
Apa Sebenarnya Rekursi Itu?
Dengan kata dasar, rekursi adalah teknik pemrograman yang kuat yang menyertakan fungsi yang memanggil dirinya sendiri selama eksekusi. Ini seperti menatap cermin dan melihat gambar di dalam gambar, menghasilkan siklus referensi diri.
Kita dapat mengatasi masalah besar menggunakan rekursi dengan membaginya menjadi submasalah yang lebih kecil dan lebih mudah dikelola.
Ini mirip dengan menyusun teka-teki, di mana satu bagian terhubung ke bagian lain untuk menghasilkan gambar yang utuh. Rekursi memungkinkan kita untuk menyelesaikan masalah dengan cara yang elegan dan efisien dengan mengulangi rangkaian instruksi yang sama dengan berbagai masukan.
Rekursi 1-Langsung
Rekursi langsung adalah jenis rekursi paling dasar, di mana suatu fungsi memanggil dirinya sendiri secara langsung. Ini memerlukan membagi masalah yang bermasalah menjadi submasalah yang lebih kecil sampai kasus dasar tercapai, yang mengarah pada penghentian.
Fungsi rekursif memanggil dirinya sendiri dengan berbagai input, memungkinkan eksekusi set instruksi yang sama diulang. Setiap doa dibangun di atas yang sebelumnya, semakin mendekati kasus dasar yang menyebabkan rekursi berakhir.
Mari kita periksa contoh ini.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Keluaran:
5
4
3
2
1
Rekursi 2-Tidak Langsung
Rekursi tidak langsung menambahkan sentuhan menarik ke jalur rekursif. Berbeda dengan rekursi langsung, yang melibatkan fungsi yang secara eksplisit memanggil dirinya sendiri, rekursi tidak langsung mencakup serangkaian pemanggilan fungsi.
Satu fungsi memanggil yang lain, yang kemudian dapat memanggil fungsi asli atau fungsi lain yang akhirnya kembali ke aslinya. Jaring pemanggilan fungsi yang saling berhubungan ini menghasilkan tarian yang memikat di mana beberapa fungsi berkolaborasi untuk memperbaiki masalah.
Contoh:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
Keluaran:
A: 3
B: 2
A: 1
Rekursi 3-Linear
Pertimbangkan perjalanan menyusuri rute lurus, selangkah demi selangkah, sampai Anda tiba di tujuan Anda. Teknik sekuensial ini diwujudkan dengan rekursi linier, di mana suatu fungsi melakukan satu panggilan rekursif di setiap iterasi fungsi.
Dengan setiap panggilan rekursif, proses rekursif bergerak mendekati kasus dasar dengan menurunkan ukuran masalah. Ini berlangsung dengan cara yang jelas dan linier, menyelesaikan submasalah satu per satu hingga jawaban akhir tercapai.
Contoh:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Keluaran:
120
Rekursi 4 Pohon
Ketika suatu fungsi bercabang menjadi beberapa panggilan rekursif, kita memasuki dunia rekursi pohon. Sebuah fungsi dalam rekursi pohon menghasilkan banyak panggilan rekursif, yang masing-masing memecahkan submasalah terpisah, seperti yang dilakukan cabang-cabang pohon.
Struktur percabangan ini memungkinkan penyelidikan simultan dari beberapa rute, secara efektif memecah masalah rumit menjadi komponen yang lebih kecil dan saling terkait.
Contoh:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Keluaran:
8
Rekursi Bersarang 5
Rekursi bersarang menambahkan tingkat kerumitan yang menarik ke alam semesta rekursif. Dalam bentuk rekursi ini, suatu fungsi menggabungkan panggilan rekursif sebagai argumen dalam panggilan rekursif lainnya.
Panggilan rekursif dalam bekerja pada nilai yang bergantung pada panggilan rekursif luar. Kompleksitas tumbuh dengan setiap pemanggilan bersarang, yang berpuncak pada pola panggilan rekursif bersarang yang menarik.
Contoh:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Hasil:
91
Rekursi 6 Ekor
Rekursi ekor adalah teknik optimasi untuk algoritma rekursif yang dapat meningkatkan kinerjanya. Panggilan rekursif muncul sebagai tindakan terakhir dari suatu fungsi dengan rekursi ekor, pembuatan.
Karena tidak ada operasi luar biasa yang mengikuti panggilan rekursif, kompiler atau juru bahasa dapat menyederhanakan rekursi dengan menggantinya dengan lompatan sederhana.
Pendekatan pengoptimalan ini, yang dikenal sebagai pengoptimalan panggilan ekor, mengurangi persyaratan untuk setiap panggilan rekursif untuk mempertahankan bingkai tumpukan, menghasilkan peningkatan kecepatan dan penggunaan memori yang lebih rendah.
Contoh:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Keluar keluar:
120
Rekursi 7-Non-Ekor
Berbeda dengan rekursi ekor, rekursi non-ekor melibatkan aktivitas ekstra yang dilakukan setelah pemanggilan rekursif dalam suatu fungsi. Sebelum tindakan lainnya dapat dilakukan, setiap panggilan rekursif harus diselesaikan dan dikembalikan.
Akibatnya, hingga kasus dasar tercapai dan rekursi berakhir, setumpuk operasi yang belum selesai akan dipertahankan. Rekursi non-ekor sering menggunakan lebih banyak memori dan kurang efisien dibandingkan rekursi ekor, tetapi masih merupakan alat yang berguna untuk mengatasi berbagai masalah.
Contoh:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Keluaran:
15
Bungkus
Rekursi adalah konsep yang menarik dalam pemrograman. Hal ini memungkinkan kita untuk mengatasi masalah rumit secara rekursif, self-referensial.
Ini menawarkan metode yang berbeda untuk memikirkan dan memecahkan masalah, memecahnya menjadi potongan-potongan yang lebih kecil dan lebih mudah dikelola. Namun, ketika bekerja dengan rekursi, penting untuk memperhatikan beberapa poin.
Anda harus mengidentifikasi kasus dasar yang sesuai yang memungkinkan rekursi berakhir. Jika tidak ada, fungsi dapat terus memanggil dirinya sendiri selamanya.
Kedua, berdasarkan skenario yang ada, memilih jenis rekursi yang tepat dapat menghasilkan solusi yang lebih efisien dan elegan. Cobalah untuk menemukan apa yang terbaik untuk masalah di tangan. Saat bekerja dengan kedalaman rekursi yang luas, waspadai potensi bahaya seperti stack overflow.
Tinggalkan Balasan