Rekursi di Python: Konsep, Contoh, dan Tips

Rekursi adalah konsep mendasar dalam pemrograman, dan memiliki peran penting khususnya di Python. Ini mengacu pada teknik di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan suatu masalah dengan memecahnya menjadi submasalah yang lebih kecil dan mudah dikelola. 

Metode ini memungkinkan solusi yang elegan dan ringkas, terutama saat menangani masalah yang melibatkan tugas berulang atau struktur hierarkis. Di Python, rekursi digunakan dalam berbagai aplikasi, mulai dari menyortir algoritme hingga penelusuran data yang kompleks. 

Solusi rekursif sering mencerminkan definisi matematis dari suatu masalah, sehingga intuitif bagi mereka yang akrab dengan penalaran matematis. Keindahan rekursi terletak pada kemampuannya mengekspresikan algoritme kompleks hanya dalam beberapa baris kode, menghasilkan solusi yang elegan dan mudah dibaca. Namun, menguasai rekursi memerlukan perubahan cara berpikir dari pendekatan iteratif yang lebih umum.

Dalam artikel ini, saya akan membahas konsep rekursi, cara kerjanya di Python, dan penerapannya secara praktis, termasuk pembahasan masalah umum serta perbandingannya dengan iterasi. Jika Anda baru memulai Python, pertimbangkan untuk mengikuti salah satu kursus kami, seperti Pengenalan Python, Konsep Paradigma Pemrograman, atau Dasar-Dasar Pemrograman Python.

Apa Itu Rekursi di Python?

Di Python, rekursi mengacu pada fungsi yang memanggil dirinya sendiri untuk menyelesaikan suatu masalah. Ini melibatkan dua komponen penting:

• Base case: Kondisi yang menghentikan rekursi. Tanpanya, pemanggilan rekursif akan terus berlangsung selamanya dan pada akhirnya menyebabkan fungsi mogok atau kehabisan memori.
• Recursive case: Bagian fungsi yang memecah masalah menjadi bagian yang lebih kecil dan memanggil fungsi tersebut kembali dengan bagian yang lebih kecil itu.

Cara sederhana untuk memikirkan rekursi: bayangkan sebuah fungsi yang menyelesaikan masalah kompleks dengan menyelesaikan versi yang lebih kecil dari masalah yang sama, hingga akhirnya mencapai solusi yang tidak memerlukan rekursi lebih lanjut.

Pendekatan rekursif mengikuti strategi "divide and conquer", memecah masalah kompleks menjadi versi yang lebih sederhana hingga mencapai kasus sepele. Pendekatan ini sering mencerminkan cara kita secara alami memikirkan pemecahan masalah. Misalnya, saat menyortir setumpuk kartu, kita mungkin secara alami menyortir kelompok yang lebih kecil lalu menggabungkannya, yang pada dasarnya adalah cara kerja algoritme pengurutan rekursif seperti merge sort.

Setiap fungsi rekursif harus memiliki setidaknya satu base case dan setidaknya satu recursive case. Base case mencegah rekursi tak terbatas dengan menyediakan kondisi yang tidak memerlukan pemanggilan fungsi lebih lanjut. Recursive case mengurangi ukuran masalah pada setiap pemanggilan, memastikan base case akhirnya tercapai.

Bagaimana Rekursi Bekerja di Python?

Rekursi bekerja dengan memungkinkan sebuah fungsi memanggil dirinya sendiri dengan argumen yang dimodifikasi, secara bertahap menyelesaikan masalah dalam langkah-langkah yang lebih kecil. Untuk memahaminya secara konkret, pertimbangkan tugas menghitung jumlah bilangan dari 1 hingga num.

Berikut pendekatan rekursif sederhana untuk menghitung jumlah tersebut:

def sum_recursive(num):
    if num == 1:  # Base case
        return num
    return num + sum_recursive(num - 1)  # Recursive case

print(sum_recursive(3)) # 3 + 2 + 1 Didukung oleh

6Didukung oleh

Dalam fungsi ini, base case adalah saat num == 1, yang menghentikan rekursi. Jika tidak, fungsi memanggil dirinya sendiri dengan num - 1 hingga mencapai base case.

Cara kerjanya langkah demi langkah:

1. sum_recursive(3) memanggil sum_recursive(2).
2. sum_recursive(2) memanggil sum_recursive(1).
3. sum_recursive(1) mengembalikan 1 (base case).
4. Sekarang, sum_recursive(2) dapat mengembalikan 2 + 1 = 3, dan sum_recursive(3) dapat mengembalikan 3 + 3 = 6.

Contoh lain adalah fungsi rekursif untuk menghitung pangkat suatu bilangan:

def power(base, exponent):
    if exponent == 0:  # Base case
        return 1
    else:
        return base * power(base, exponent - 1)  # Recursive case

print(power(2, 3))Didukung oleh

8Didukung oleh

Penjelasan langkah demi langkah untuk fungsi pangkat ini:

• power(2, 3) memanggil power(2, 2).
• power(2, 2) memanggil power(2, 1).
• power(2, 1) memanggil power(2, 0).
• power(2, 0) mengembalikan 1 (base case).
• Kemudian, mundur: power(2, 1) mengembalikan 2 * 1 = 2.
• Lalu power(2, 2) mengembalikan 2 * 2 = 4.
• Terakhir, power(2, 3) mengembalikan 2 * 4 = 8.

Saat fungsi rekursif dipanggil, setiap pemanggilan rekursif membuat entri baru pada call stack. Stack ini melacak semua pemanggilan fungsi dan variabelnya. Ketika base case tercapai, stack mulai menyelesaikan setiap pemanggilan dalam urutan terbalik, menghitung hasil akhir selangkah demi selangkah.

Memahami perilaku stack ini sangat penting karena menjelaskan kekuatan sekaligus keterbatasan rekursi di Python. Ia mempertahankan konteks secara elegan tetapi juga dapat menyebabkan masalah memori pada rekursi yang dalam.

Menerapkan Faktorial di Python Menggunakan Rekursi

Fungsi faktorial adalah contoh klasik untuk mendemonstrasikan rekursi. Faktorial dari sebuah bilangan n, dilambangkan n!, adalah hasil kali semua bilangan bulat positif yang kurang dari atau sama dengan n. Secara matematis:

n! = n × (n − 1) × (n − 2) × … × 1

Secara rekursif, fungsi faktorial dapat didefinisikan sebagai:

n! = n × (n − 1)!

Mari kita terapkan ini di Python:

def compute_factorial(num):
    if num == 0:  # Base case
        return 1
    return num * compute_factorial(num - 1)  # Recursive case

print(compute_factorial(4)) # 4 * 3 * 2 * 1Didukung oleh

24Didukung oleh

Penjelasan kode langkah demi langkah:

• Fungsi compute_factorial(num) memeriksa apakah num == 0 dan mengembalikan 1 dalam kasus tersebut.
• Jika tidak, ia mengembalikan num * compute_factorial(num - 1), di mana fungsi memanggil dirinya sendiri dengan nilai num yang lebih kecil.

Fungsi faktorial dengan sempurna menggambarkan keanggunan rekursi. Definisi matematisnya sendiri bersifat rekursif, sehingga implementasi kodenya intuitif dan selaras erat dengan konsep matematis. Ini adalah salah satu kekuatan rekursi: memungkinkan kode mengekspresikan definisi matematis secara langsung.

Perlu dicatat bahwa ada kasus tepi yang perlu dipertimbangkan. Misalnya, faktorial biasanya hanya didefinisikan untuk bilangan bulat tak negatif. Implementasi yang tangguh mungkin menyertakan penanganan kesalahan untuk input negatif atau pemeriksaan tipe. 

Selain itu, untuk nilai num yang besar, solusi rekursif dapat menyebabkan stack overflow, yang merupakan keterbatasan yang akan saya bahas lebih lanjut.

Masalah Umum: Cara Memperbaiki Error Rekursi di Python

Meskipun rekursi dapat menjadi alat yang kuat, ada beberapa masalah umum yang sering muncul, seperti:

Melebihi kedalaman rekursi maksimum

Python memiliki batas rekursi default sebesar 1000 pemanggilan. Jika suatu fungsi rekursif memanggil dirinya sendiri terlalu banyak, sebuah RecursionError akan muncul.

Berikut cara mengatasinya:

Anda dapat meningkatkan kedalaman rekursi menggunakan sys.setrecursionlimit(). Namun, ini tidak direkomendasikan kecuali benar-benar diperlukan, karena dapat menyebabkan stack overflow.

import sys  

# Get the current recursion limit
current_limit = sys.getrecursionlimit()
print(f'Current limit: {current_limit}')  

# Set a new recursion limit to 200
new_limit = 200
sys.setrecursionlimit(new_limit)  

# Get the new recursion limit
changed_current_limit = sys.getrecursionlimit()
print(f'Current limit after change: {changed_current_limit}')  Didukung oleh

Current limit: 1000
Current limit after change: 200Didukung oleh

Base case hilang

Base case yang hilang atau salah akan menyebabkan fungsi rekursi tanpa henti, yang berujung pada stack overflow.

Untuk mengatasinya, pastikan base case Anda terdefinisi dengan baik dan dapat dicapai.

Cara Menghentikan Rekursi di Python

Kunci untuk menghentikan rekursi di Python adalah mendefinisikan base case yang tepat. Tanpanya, rekursi tidak akan pernah berakhir dan menghasilkan error.

Sebagai contoh, pada fungsi faktorial yang saya terapkan sebelumnya, base case-nya adalah if num == 0, yang menghentikan rekursi. Secara umum, Anda perlu memastikan setiap fungsi rekursif memiliki kondisi untuk terminasi.

Merancang base case yang efektif membutuhkan pemikiran yang cermat. Beberapa pedoman meliputi:

• Identifikasi versi masalah yang paling sederhana yang dapat diselesaikan secara langsung.
• Pastikan semua jalur rekursif pada akhirnya mencapai base case.
• Uji kasus tepi secara terpisah untuk memverifikasi penanganannya benar.
• Pertimbangkan beberapa base case jika masalah membutuhkannya.

Terkadang, teknik pemrograman defensif bermanfaat, dengan menambahkan pengaman terhadap input tidak valid atau pemeriksaan runtime untuk mencegah kedalaman rekursi berlebihan. Misalnya:

def safe_factorial(num, depth=0, max_depth=100):
    # Check if recursion is too deep
    if depth > max_depth:
        raise ValueError("Maximum recursion depth exceeded")
   
    # Base case
    if num <= 0:
        return 1
   
    # Recursive case with depth tracking
    return num * safe_factorial(num - 1, depth + 1, max_depth)Didukung oleh

# Calculate factorial of 5 with default depth limits
result = safe_factorial(5)

print(result) Didukung oleh

120Didukung oleh

# Calculate factorial of 5 with depth > max_depth
result = safe_factorial(5, depth=20, max_depth=10)

print(result) Didukung oleh

ValueError: Maximum recursion depth exceededDidukung oleh

Pendekatan ini memungkinkan Anda menetapkan batas khusus dan memberikan pesan kesalahan yang lebih bermakna daripada RecursionError default.

Berikut contoh lain yang menunjukkan cara berbeda dalam mendefinisikan base case: mencari pembagi bersama terbesar (GCD) dari dua bilangan menggunakan rekursi.

GCD dari dua bilangan x dan y dapat dihitung menggunakan algoritme Euclid, dengan operator modulo %:

• Base case: Jika y == 0, GCD adalah x.
• Recursive case: Jika tidak, GCD dari x dan y sama dengan GCD dari y dan x % y.

def find_gcd(x, y):
    # Base case: if y is 0, the GCD is x
    if y == 0:
        return x
    # Recursive case: GCD of y and x % y
    return find_gcd(y, x % y)

print(find_gcd(48, 18))  Didukung oleh

6Didukung oleh

Rekursi vs. Iterasi di Python

Baik rekursi maupun iterasi dapat menyelesaikan banyak masalah yang sama, tetapi masing-masing memiliki kelebihan dan kekurangan:

• Rekursi sering kali lebih elegan dan mudah dipahami, terutama untuk masalah yang memiliki struktur rekursif alami (mis., penelusuran pohon, faktorial, bilangan Fibonacci).
• Iterasi bisa lebih efisien karena tidak melibatkan overhead banyak pemanggilan fungsi dan dapat menghindari masalah terkait stack overflow. Solusi iteratif biasanya lebih hemat memori.

Kapan menggunakan rekursi:

• Saat masalah dapat secara alami dipecah menjadi submasalah yang lebih kecil.
• Untuk masalah yang melibatkan struktur data hierarkis, seperti pohon.
• Ketika solusi dalam bentuk rekursif lebih intuitif dan menghasilkan kode yang lebih bersih.
• Saat keterbacaan kode diprioritaskan dibanding optimasi performa.
• Saat bekerja dengan data yang kedalamannya tidak diketahui (seperti mengurai JSON atau XML bertingkat).

Kapan menggunakan iterasi:

• Untuk masalah yang memerlukan tugas berulang tanpa memecah masalah menjadi submasalah yang lebih kecil.
• Untuk tugas yang kritis terhadap performa, di mana rekursi yang dalam dapat mengakibatkan penggunaan memori tinggi.
• Saat bekerja dengan dataset besar yang mungkin melebihi batas rekursi.
• Ketika penggunaan memori menjadi perhatian utama.
• Untuk masalah yang secara alami bersifat sekuensial, bukan hierarkis.

Mari bandingkan implementasi rekursif dan iteratif untuk masalah yang sama, menghitung jumlah bilangan dari 1 hingga num:

Rekursif:

def sum_recursive(num):
    if num == 1:
        return 1
    else:
        return num + sum_recursive(num - 1)Didukung oleh

Iteratif:

def iterative_sum(num):
    total = 0
    for i in range(1, num + 1):
        total += i
    return totalDidukung oleh

Versi iteratif menggunakan loop untuk mengakumulasikan jumlah, sementara versi rekursif memecah masalah menjadi menambahkan n ke jumlah bilangan dari 1 hingga num - 1. Meskipun keduanya berfungsi, versi iteratif akan lebih efisien untuk nilai num yang besar karena tidak melibatkan overhead banyak pemanggilan fungsi.

Beberapa masalah yang secara alami bersifat rekursif dapat diubah menjadi solusi iteratif menggunakan stack atau queue untuk mensimulasikan pemanggilan rekursif. Teknik ini sangat berguna saat menangani penelusuran pohon atau graf.

Contoh Praktis Rekursi di Python

Rekursi dapat diterapkan pada berbagai masalah menarik:

1. Menghitung bilangan Fibonacci

Deret Fibonacci didefinisikan secara rekursif sebagai:

• F(0) = 0
• F(1) = 1
• F(n) = F(n − 1) + F(n − 2)

Ini akan menghasilkan urutan berikut:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

Berikut cara mengimplementasikannya:

def compute_fibonacci(num):
    if num <= 0:
        return 0
    elif num == 1:
        return 1
    return compute_fibonacci(num - 1) + compute_fibonacci(num - 2)

print(compute_fibonacci(6))Didukung oleh

8Didukung oleh

Namun, implementasi naif ini menghitung ulang nilai berkali-kali. Pendekatan yang lebih efisien menggunakan memoization, yang menyimpan hasil yang sudah dihitung (caching) untuk menghindari perhitungan berulang, sehingga secara signifikan mengurangi waktu komputasi:

def optimized_fibonacci(num, cache=None):
    if cache is None:
        cache = {}
    if num in cache:
        return cache[num]
    if num <= 1:
        return num
    cache[num] = optimized_fibonacci(num - 1, cache) + optimized_fibonacci(num - 2, cache)
    return cache[num]Didukung oleh

Ini dapat disederhanakan lagi menggunakan dekorator lru_cache() dari modul functools:

from functools import lru_cache

@lru_cache(maxsize=None)  # Cache all computed values
def cached_fibonacci(num):
    if num <= 1:
        return num
    return cached_fibonacci(num - 1) + cached_fibonacci(num - 2)Didukung oleh

2. Menelusuri struktur data bertingkat

Rekursi juga berguna untuk bekerja dengan struktur data bertingkat seperti list di dalam list atau objek JSON. Misalnya, menelusuri struktur pohon direktori atau secara rekursif meratakan list bertingkat.

def flatten(nested):
    result = []
    for element in nested:
        if isinstance(element, list):
            result.extend(flatten(element))
        else:
            result.append(element)
    return result

nested_structure = [1, [2, 3], [4, [5, 6]]]

print(flatten(nested_structure))  Didukung oleh

[1, 2, 3, 4, 5, 6]Didukung oleh

3. Algoritme pengurutan (mis., quick sort atau merge sort) 

Algoritme pengurutan seperti quick sort dan merge sort sangat bergantung pada rekursi. Dalam algoritme ini, masalah dipecah menjadi submasalah yang lebih kecil, yang diurutkan secara rekursif.

Berikut implementasi sederhana quicksort:

def quicksort_algo(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    lower = [item for item in array if item < pivot]
    equal = [item for item in array if item == pivot]
    greater = [item for item in array if item > pivot]
    return quicksort_algo(lower) + equal + quicksort_algo(greater)

array = [220, 33, 400, 150, 16]

print(quicksort_algo(array))Didukung oleh

[16, 33, 150, 220, 400]Didukung oleh

Kesimpulan

Rekursi adalah konsep kuat di Python yang membantu menyelesaikan masalah kompleks dengan memecahnya menjadi submasalah yang lebih sederhana. Jika digunakan dengan tepat, rekursi menghasilkan kode yang bersih dan ringkas serta mudah dipahami. 

Namun, sangat penting untuk mendefinisikan base case yang tepat dan memperhatikan kedalaman rekursi guna menghindari kesalahan umum. 

Meskipun rekursi terkadang kurang efisien dibanding iterasi, ini adalah alat yang tak ternilai untuk menyelesaikan jenis masalah tertentu, khususnya yang melibatkan data hierarkis atau masalah yang secara alami cocok untuk solusi rekursif.

Dengan memahami rekursi dan berlatih dengan contoh seperti faktorial, deret Fibonacci, dan algoritme pengurutan, Anda akan siap memanfaatkan rekursi dalam proyek Python Anda.

Jika Anda tertarik pada topik Python lanjutan tempat Anda dapat menerapkan rekursi, lihat jalur pembelajaran berikut: Pemrograman Python, Analis Data dengan Python, dan Associate Data Scientist in Python