Menguasai Rekursi Python: Bagaimana Fungsi Memanggil Diri Sendiri
Menguasai Rekursi Python
Temukan bagaimana fungsi Python dapat memanggil diri sendiri, mekanisme rekursi, dan praktik terbaik untuk menulis kode rekursif yang aman dan efisien.
Apa Itu Rekursi?
Rekursi adalah teknik untuk mendefinisikan masalah dalam bentuk instance yang lebih kecil dari masalah yang sama.
Ilustrasi klasik melibatkan dua cermin sejajar yang menghadap satu sama lain; setiap gambar adalah refleksi rekursif dari yang lain.
Fungsi Rekursif Python
Dalam Python, fungsi dapat memanggil fungsi lain, dan bahkan dapat memanggil dirinya sendiri. Konstruksi semacam ini disebut fungsi rekursif.
Gambar di bawah menunjukkan tumpukan panggilan untuk fungsi rekursif sederhana bernama recurse:
Di bawah ini adalah contoh klasik: implementasi rekursif dari fungsi factorial, yang mengembalikan hasil kali semua bilangan bulat positif hingga x.
Contoh Fungsi Rekursif
def factorial(x): """Menghitung faktorial bilangan bulat positif secara rekursif.""" if x == 1: return 1 return x * factorial(x - 1) num = 3 print("The factorial of", num, "is", factorial(num))
Output
The factorial of 3 is 6
Di sini, factorial() adalah fungsi rekursif karena ia memanggil dirinya sendiri sampai kondisi dasar x == 1 tercapai.
Saat dipanggil dengan bilangan bulat positif, fungsi berulang kali memanggil dirinya sendiri dengan nilai yang menurun:
factorial(3) # pemanggilan ke-1 dengan 3 3 * factorial(2) # pemanggilan ke-2 dengan 2 3 * 2 * factorial(1) # pemanggilan ke-3 dengan 1 3 * 2 * 1 # kembali dari pemanggilan ke-3 3 * 2 # kembali dari pemanggilan ke-2 6 # kembali dari pemanggilan ke-1
Di bawah ini adalah representasi visual dari proses langkah demi langkah ini:
Rekursi berakhir ketika nilai input mencapai kondisi dasar (dalam hal ini, x == 1). Setiap fungsi rekursif harus menyertakan kriteria berhenti tersebut; jika tidak, ia akan berlanjut tanpa henti dan akhirnya menguras tumpukan panggilan.
Python memberlakukan batas rekursi maksimal (default 1000) untuk mencegah rekursi tak hingga yang menyebabkan interpreter crash. Melebihi batas ini menghasilkan RecursionError:
def recursor(): recursor() recursor()
Output
Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded
Anda dapat menyesuaikan batas rekursi secara terprogram menggunakan sys.setrecursionlimit(), tetapi lakukan dengan hati-hati untuk menghindari stack overflow.
Keuntungan Rekursi
Solusi rekursif seringkali lebih ringkas dan lebih mudah dibaca, terutama untuk masalah yang secara alami diekspresikan dalam istilah rekursif.
Mereka memungkinkan dekomposisi elegan dari tugas kompleks menjadi sub-masalah yang lebih sederhana.
Generasi urutan (misalnya, Fibonacci, permutasi) mudah dilakukan dengan rekursi dibandingkan dengan nested loop.
Kerugian Rekursi
Logika rekursif dapat lebih sulit diikuti dan dipahami bagi pemula.
Setiap panggilan rekursif mengonsumsi ruang tumpukan; rekursi dalam dapat memakan banyak memori dan lebih lambat daripada alternatif iteratif.
Debugging rekursi dapat menantang karena tumpukan panggilan berlapis.
Dalam praktiknya, pilih rekursi ketika ia menghasilkan kode yang lebih jelas dan lebih mudah dirawat dan ketika ukuran input sedang. Untuk input yang sangat besar, pendekatan iteratif atau optimasi rekursi ekor (ketika didukung) mungkin lebih diutamakan.