Tutorial Rekursif dalam Python

Rekursif adalah teknik pemrograman di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan masalah. Fungsi rekursif biasanya memiliki kondisi berhenti (base case) untuk mencegah panggilan tak terbatas dan memecah masalah menjadi sub-masalah yang lebih kecil. Tutorial ini akan menjelaskan konsep rekursif dengan contoh praktis dalam Python.

Struktur Dasar Rekursif

1. Fungsi yang Memanggil Dirinya Sendiri: Ciri utama rekursif.
2. Kondisi Berhenti: Menghentikan proses rekursif agar tidak berjalan terus-menerus.
3. Pembagian Masalah: Memecah masalah menjadi bagian-bagian kecil yang lebih mudah diselesaikan.

Rekursif sangat berguna untuk masalah dengan struktur berulang, seperti traversal pohon, algoritma divide-and-conquer (misalnya, quicksort), atau saat kode rekursif lebih mudah dibaca dibandingkan iterasi.

Contoh 1: Faktorial

Faktorial dari ( n ) (ditulis ( n! )) adalah hasil kali semua bilangan bulat positif dari 1 hingga ( n ). Secara matematis, faktorial didefinisikan sebagai:

$$ n! = \begin{cases} 1 & \text{jika } n = 0 \\ n \times (n-1)! & \text{kalo } n > 0 \end{cases} $$

Kode Python

def faktorial(n):
    if n < 0:
        raise ValueError("Input harus non-negatif")
    if n == 0:
        return 1
    return n * faktorial(n - 1)

# Contoh penggunaan
print(faktorial(5))  # Output: 120

Penjelasan

• Kondisi Berhenti: Jika ( n = 0 ), fungsi mengembalikan 1.
• Panggilan Rekursif: Jika ( n > 0 ), fungsi memanggil dirinya sendiri dengan ( n-1 ), lalu mengalikan hasilnya dengan ( n ).
• Catatan: Python memiliki batas rekursif default (biasanya 1000 panggilan). Untuk input besar, Anda dapat meningkatkan batas dengan:import sys sys.setrecursionlimit(2000) Namun, gunakan dengan hati-hati karena dapat menyebabkan stack overflow jika terlalu dalam.

Contoh 2: Deret Fibonacci

Deret Fibonacci adalah urutan di mana setiap angka adalah jumlah dari dua angka sebelumnya, dimulai dari 0 dan 1. Secara rekursif:

$$ F(n) = \begin{cases} 0 & \text{jika } n = 0 \\ 1 & \text{jika } n = 1 \\ F(n-1) + F(n-2) & \text{jika } n > 1 \end{cases} $$

Kode Python (Versi Dasar)

def fibonacci(n):
    if n < 0:
        raise ValueError("Input harus non-negatif")
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

# Contoh penggunaan
print(fibonacci(7))  # Output: 13

Kode Python (Versi dengan Memoization)

Versi dasar di atas memiliki kompleksitas waktu ( O(2^n) ), yang sangat tidak efisien untuk ( n ) besar. Dengan memoization (menyimpan hasil perhitungan sebelumnya), kompleksitas menjadi ( O(n) ):

def fibonacci_memo(n, memo={}):
    if n < 0:
        raise ValueError("Input harus non-negatif")
    if n == 0:
        return 0
    elif n == 1:
        return 1
    if n not in memo:
        memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# Contoh penggunaan
print(fibonacci_memo(7))  # Output: 13

Penjelasan

• Kondisi Berhenti: Jika ( n = 0 ) atau ( n = 1 ), fungsi mengembalikan ( n ).
• Panggilan Rekursif: Fungsi memanggil dirinya sendiri dengan ( n-1 ) dan ( n-2 ), lalu menjumlahkan hasilnya.
• Memoization: Hasil perhitungan disimpan dalam dictionary memo untuk mencegah perhitungan ulang.

Contoh 3: Deret Bilangan Genap

Fungsi ini menghasilkan daftar bilangan genap dari 0 hingga \( 2 \times (n – 1) \).

Kode Python

def deret_genap(n):
    if n < 0:
        raise ValueError("Input harus non-negatif")
    if n == 0:
        return []
    deret_sebelumnya = deret_genap(n - 1)
    return deret_sebelumnya + [2 * (n - 1)]

# Contoh penggunaan
print(deret_genap(5))  # Output: [0, 2, 4, 6, 8]

Penjelasan

• Kondisi Berhenti: Jika \( n = 0 \), fungsi mengembalikan daftar kosong.
• Panggilan Rekursif: Fungsi memanggil dirinya sendiri dengan \( n – 1 \), lalu menambahkan elemen baru \( 2 \times (n – 1) \) ke daftar.
• Catatan: Operasi penggabungan daftar (+) menciptakan daftar baru setiap kali, yang bisa memakan memori untuk \( n \) besar. Pendekatan iteratif mungkin lebih efisien dalam kasus ini.

Catatan Penting

• Kondisi Berhenti: Selalu pastikan fungsi memiliki kondisi berhenti untuk mencegah infinite recursion yang dapat menyebabkan program crash.
• Efisiensi Memori: Setiap panggilan rekursif menyimpan state di call stack, yang dapat memakan memori. Untuk kasus sederhana, iterasi sering lebih hemat memori.
• Tail Recursion: Beberapa bahasa seperti Scheme mengoptimalkan tail recursion, tetapi Python tidak. Oleh karena itu, gunakan iterasi untuk rekursif dalam jika memungkinkan.
• Input Tidak Valid: Gunakan exception (raise ValueError) untuk menangani input tidak valid agar kode lebih robust.

Kesimpulan

Rekursif adalah alat yang kuat untuk menyelesaikan masalah dengan struktur berulang, seperti traversal pohon atau algoritma divide-and-conquer. Namun, gunakan dengan bijak, pastikan kondisi berhenti jelas, dan pertimbangkan efisiensi. Untuk latihan lebih lanjut, coba buat fungsi rekursif untuk:

1. Membalikkan string (misalnya, “hello” menjadi “olleh”).
2. Menghitung jumlah digit dalam bilangan (misalnya, 1234 menghasilkan 4).
3. Menghitung pangkat bilangan (misalnya, \( 2^3 = 8 \)).

Jika Anda memiliki pertanyaan atau ingin contoh lain, silakan tanyakan!