Fungsi Rekursif Python: Cara Menggunakan dan Contoh

pas kuliah dulu saya sempat mentok ngerjain soal faktorial, bukan karena rumusnya sulit, tapi karena fungsi yang saya tulis tidak mau berhenti memanggil dirinya sendiri sampai laptop kipasnya bunyi kenceng 🙂 belakangan saya paham, yang saya lewatkan cuma satu konsep kecil bernama base case. dari situ saya mulai kebanggaan sama yang namanya fungsi rekursif python.

di artikel ini saya tunjukkan cara kerja rekursi pakai bahasa sehari-hari, lengkap dengan contoh yang bisa langsung dicoba: faktorial, Fibonacci, FPB, sampai traversal folder. saya kasih juga penanganan RecursionError yang paling sering bikin pemula menyerah.

Apa Itu Fungsi Rekursif?

fungsi rekursif adalah fungsi yang memanggil dirinya sendiri di dalam tubuhnya sendiri. konsepnya mirip cermin yang saling berhadapan, cuma versi programmernya punya aturan main supaya tidak refleksi terus selamanya.

aturan mainnya ada dua, dan keduanya wajib ada:

1. base case, kondisi berhenti yang mengembalikan nilai tanpa memanggil fungsi lagi
2. recursive case, bagian yang memanggil fungsinya sendiri dengan masalah yang makin kecil

kalau base case-nya lupa ditulis atau tidak pernah tercapai, Python lempar RecursionError karena panggilannya menumpuk di call stack sampai melebihi batas.

Analogi Sederhana: Menara Boks

bayangkan kalian diminta hitung ada berapa boks dalam tumpukan. caranya: ambil satu boks paling atas (hitung 1), lalu minta teman hitung sisanya. teman kalian lakukan hal yang sama, ambil satu, tanya teman lain. begitu tumpukan habis, orang terakhir bilang “0”, lalu jawaban dibalikkan ke atas: 0 + 1 + 1 + 1…

• ambil satu boks dan tanya lagi = recursive case
• tumpukan habis = base case

setiap panggilan fungsi di Python bekerja persis seperti itu, tersusun di call stack, dan jawaban dihitung mundur dari panggilan terdalam.

Contoh 1: Faktorial

faktorial adalah contoh klasiknya. 5! = 5 x 4 x 3 x 2 x 1 = 120:

def faktorial(n):
    if n <= 1:          # base case
        return 1
    return n * faktorial(n - 1)  # recursive case

print(faktorial(5))  # Output: 120

cara bacanya: faktorial(5) menunggu hasil faktorial(4), yang menunggu faktorial(3), dan seterusnya sampai faktorial(1) mengembalikan 1. setelah itu penghitungan naik lagi: 2*1, 3*2, 4*6, 5*24 = 120.

Contoh 2: Fibonacci

deret Fibonacci punya aturan: dua bilangan pertama adalah 0 dan 1, bilangan berikutnya adalah jumlah dua sebelumnya:

def fibonacci(n):
    if n <= 1:          # base case
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(10):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34

rekursi ini memang elegan, tapi ada biayanya. fibonacci(30) sudah ribuan panggilan berulang, dan fibonacci(50) tanpa bantuan bisa bikin laptop duduk diam lama. solusinya ada di bagian memoization di bawah.

Contoh 3: FPB (Faktor Persekutuan Terbesar)

FPB pakai algoritma Euclid, dan ini contoh rekursi yang benar-benar efisien karena jumlah panggilannya sangat sedikit:

def fpb(x, y):
    if y == 0:          # base case
        return x
    return fpb(y, x % y)

print(fpb(12, 18))  # Output: 6

fpb(12, 18) jadi fpb(18, 12), lalu fpb(12, 6), fpb(6, 0), selesai. tiga langkah saja untuk bilangan sekalipun besar.

Contoh 4: Traversal Folder

ini contoh rekursi yang paling kepakai di pekerjaan nyata: menyapu seluruh isi folder beserta subfoldernya. struktur folder itu tree, dan tree itu memang alam rekursi:

import os

def cari_file(folder, ekstensi):
    hasil = []
    for item in os.listdir(folder):
        path = os.path.join(folder, item)
        if os.path.isdir(path):
            hasil.extend(cari_file(path, ekstensi))  # recursive case
        elif item.endswith(ekstensi):
            hasil.append(path)                       # base case: file cocok
    return hasil

for file in cari_file("D:/project", ".py"):
    print(file)

bayangkan menulis logika ini pakai loop biasa. kalian harus ngatur antrian folder manual, panjang, dan rawan bug. rekursi menyelesaikannya dalam sepuluh baris.

Rekursi vs Loop: Kapan Pakai yang Mana?

aturan praktis dari pengalaman saya: kalau masalahnya linear (menjumlahkan list, hitung rata-rata), pakai loop. kalau masalahnya bercabang (folder, tree, JSON bersarang), rekursi hampir selalu menang dari sisi kerapian.

Mengatasi RecursionError

dua penyebab paling umum dan solusinya:

1. base case tidak pernah tercapai. contohnya faktorial(n) tanpa cek n <= 1, atau parameter yang tidak mengecil. cek dulu apakah tiap panggilan membawa masalah yang lebih kecil.

2. kedalaman melebihi batas. default Python membatasi 1000 panggilan. untuk kasus yang butuh lebih, naikkan batasnya:

import sys

print(sys.getrecursionlimit())  # Output: 1000
sys.setrecursionlimit(3000)     # hati-hati, terlalu besar bisa crash interpreter

jangan jadikan ini kebiasaan. kalau butuh kedalaman ribuan, biasanya masalahnya sebaiknya ditulis ulang pakai loop.

Mempercepat Rekursi dengan Memoization

kembali ke masalah Fibonacci yang lambat. @lru_cache menyimpan hasil setiap panggilan, jadi fibonacci(48) tidak dihitung ulang ribuan kali:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(50))  # Output: 12586269025, seketika

satu dekorator, dan performanya lompat drastis. teknik ini namanya memoization, dan jadi jawaban standar kalau ditanya cara bikin rekursi Python lebih cepat.

Kesimpulan

• fungsi rekursif adalah fungsi yang memanggil dirinya sendiri, dengan syarat wajib punya base case dan recursive case
• contoh kepakaiannya: faktorial, Fibonacci, FPB, dan traversal folder
• RecursionError muncul karena base case tidak tercapai atau kedalaman melebihi 1000; solusinya rapikan base case atau sesuaikan sys.setrecursionlimit()
• pakai @lru_cache untuk mempercepat rekursi yang banyak hitung ulang
• rekursi untuk struktur bercabang, loop untuk masalah linear

setelah paham rekursi di Python, coba bandingkan dengan implementasinya di bahasa lain biar kelihatan beda perilaku call stack-nya. prosesnya mirip, tapi rasanya beda.

Baca Juga Mengenai :

• belajar python function dan lambda
• contoh rekursif di cpp