Fungsi Rekursif Python: Pengertian dan Contoh Lengkap

Fungsi rekursif Python adalah fungsi yang memanggil dirinya sendiri secara berulang hingga mencapai kondisi tertentu (base case). Konsep ini sering digunakan untuk menyelesaikan masalah yang dapat dipecah menjadi submasalah lebih kecil, seperti menghitung faktorial, deret Fibonacci, dan menelusuri struktur data bersarang. Dalam artikel ini, kita akan mempelajari pengertian, cara kerja, serta contoh penggunaan fungsi rekursif di Python secara mendalam.

Apa Itu Fungsi Rekursif?

Rekursi adalah teknik pemrograman di mana sebuah fungsi memanggil dirinya sendiri untuk memecahkan masalah yang lebih kecil dari versi aslinya. Dalam Python, fungsi rekursif biasanya terdiri dari dua bagian penting:

• Base Case – Kondisi yang menghentikan rekursi agar tidak berjalan tanpa batas.
• Recursive Case – Bagian di mana fungsi memanggil dirinya sendiri dengan input yang lebih kecil.

Struktur umum fungsi rekursif dalam Python adalah sebagai berikut:

def fungsi_rekursif(parameter):
    if kondisi_berhenti:
        return hasil
    else:
        return fungsi_rekursif(parameter_baru)

Contoh 1: Menghitung Faktorial dengan Fungsi Rekursif

Faktorial dari sebuah bilangan n (ditulis n!) adalah hasil perkalian semua bilangan bulat positif dari 1 sampai n. Kita dapat menggunakan rekursi untuk menghitungnya dengan mudah:

def faktorial(n):
    if n == 1:
        return 1
    else:
        return n * faktorial(n - 1)

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

Pada contoh di atas, fungsi faktorial() akan terus memanggil dirinya sendiri dengan nilai n yang berkurang satu setiap kali, hingga mencapai base case n == 1.

Contoh 2: Deret Fibonacci dengan Fungsi Rekursif

Deret Fibonacci adalah urutan angka di mana setiap angka merupakan hasil penjumlahan dua angka sebelumnya. Contohnya: 0, 1, 1, 2, 3, 5, 8, dan seterusnya.

def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# Cetak deret Fibonacci hingga n = 10
for i in range(10):
    print(fibonacci(i), end=" ")

Fungsi di atas akan terus memanggil dirinya sendiri untuk menghitung nilai fibonacci(n-1) dan fibonacci(n-2), hingga mencapai kondisi dasar (n == 0 atau n == 1).

Kelebihan dan Kekurangan Fungsi Rekursif

Kelebihan:

• Kode lebih singkat dan mudah dibaca untuk masalah yang bersifat rekursif.
• Cocok untuk struktur data bersarang seperti pohon (tree) dan grafik.

Kekurangan:

• Konsumsi memori lebih besar karena setiap pemanggilan fungsi disimpan di stack.
• Bisa menyebabkan RecursionError jika tidak ada base case yang tepat.

Contoh 3: Menelusuri Folder Secara Rekursif

Selain untuk perhitungan matematis, rekursi juga berguna dalam menelusuri data bersarang seperti struktur folder atau file system:

import os

def telusuri_folder(path, level=0):
    for item in os.listdir(path):
        full_path = os.path.join(path, item)
        print("  " * level + "- " + item)
        if os.path.isdir(full_path):
            telusuri_folder(full_path, level + 1)

# Contoh penggunaan
telusuri_folder("/home/user/Documents")

Pada contoh di atas, fungsi telusuri_folder() akan memanggil dirinya sendiri setiap kali menemukan sub-folder baru, hingga seluruh struktur direktori selesai ditelusuri.

Optimasi Fungsi Rekursif dengan Memoization

Beberapa fungsi rekursif seperti Fibonacci sering kali melakukan perhitungan berulang. Untuk meningkatkan performa, kita bisa menggunakan teknik memoization agar hasil yang sudah dihitung tidak dihitung ulang.

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_efisien(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_efisien(n-1) + fibonacci_efisien(n-2)

# Contoh penggunaan
for i in range(10):
    print(fibonacci_efisien(i), end=" ")

Dengan dekorator @lru_cache, Python akan menyimpan hasil perhitungan sebelumnya sehingga fungsi berjalan jauh lebih cepat.

Kesimpulan

Fungsi rekursif Python adalah alat yang sangat berguna untuk menyelesaikan masalah kompleks yang dapat dipecah menjadi bagian kecil. Dengan memahami konsep dasar, base case, dan cara kerja rekursi, kita dapat menulis kode Python yang efisien dan elegan. Namun, penting juga untuk memperhatikan batas rekursi dan performa agar program tidak mengalami error atau lambat dalam eksekusi.

Dengan latihan dan pemahaman yang baik, kamu bisa menguasai konsep fungsi rekursif Python dan menerapkannya dalam berbagai proyek pemrograman.