Rekursi Python: Base Case, Tracing Call Stack, dan RecursionError

Rekursi di Python adalah fungsi yang memanggil dirinya sendiri dengan input yang makin kecil sampai menyentuh base case, yaitu kondisi yang langsung mengembalikan nilai tanpa memanggil lagi. Contoh paling umum, faktorial dan Fibonacci, gampang ditulis tapi sering gagal dipahami karena orang tidak melihat apa yang terjadi di memori. Artikel ini menelusuri faktorial(4) frame demi frame di call stack, lalu menggambar fib(5) sebagai pohon pemanggilan berisi 15 pemanggilan, dan membahas tiga error yang paling sering muncul di tugas.

#Apa saja yang wajib ada di fungsi rekursif?

Setiap fungsi rekursif butuh dua bagian. Kalau salah satunya hilang atau salah, programnya tidak berhenti atau mengembalikan nilai yang keliru.

1. Base case. Kondisi berhenti yang menjawab langsung. Untuk faktorial, $0!=1$.
2. Langkah rekursif yang bergerak mendekati base case. Untuk faktorial, $n!=n\times (n-1)!$, dan argumennya berkurang satu tiap panggilan.

def faktorial(n):
    if n == 0:          # base case
        return 1
    return n * faktorial(n - 1)   # langkah rekursif

Perhatikan bahwa return muncul dua kali. Yang kedua sering terlupa, dan akibatnya dibahas di bagian kesalahan di bawah.

#Bagaimana tracing faktorial(4) di call stack?

Setiap kali fungsi dipanggil, Python membuat satu frame baru berisi variabel lokalnya sendiri (di sini n) dan menaruhnya di puncak call stack. Frame itu baru dibuang setelah fungsinya return. Jadi faktorial(4) tidak langsung menghitung apa pun. Ia menunggu faktorial(3), yang menunggu faktorial(2), dan seterusnya.

Tracing-nya terbagi dua fase.

Langkah 1 sampai 5 adalah fase turun (push). Tidak ada perkalian yang dikerjakan di fase ini. Langkah 6 sampai 9 adalah fase naik (pop), saat setiap frame menerima hasil dari frame di atasnya dan menyelesaikan perkaliannya. Kedalaman maksimum stack adalah 5 frame untuk input 4, atau $n+1$ secara umum.

Cara cepat mengecek tracing di kertas: setiap baris "menunggu" harus punya pasangan baris "selesai" dengan urutan terbalik. Kalau di lembar jawabanmu f(2) selesai sebelum f(1), urutannya salah.

#Kenapa fib(5) butuh 15 pemanggilan?

Fibonacci punya dua pemanggilan rekursif dalam satu baris, jadi bentuknya bukan tumpukan lurus melainkan pohon.

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

Python mengevaluasi fib(n - 1) sampai tuntas dulu, baru fib(n - 2). Jadi pohonnya ditelusuri dari cabang kiri paling dalam. Angka oranye di gambar adalah urutan pemanggilan sebenarnya.

Hitung simpulnya per argumen:

Hasil akhirnya $fib\left(5\right)=5$, tapi butuh 15 pemanggilan. Jumlah pemanggilan untuk fib(n) versi ini adalah $2\cdot fib(n+1)-1$. Untuk $n=5$, $2\cdot 8-1=15$. Untuk $n=30$, jumlahnya sudah 2.692.537 pemanggilan hanya untuk mendapat angka 832.040. Pertumbuhan ini kira-kira eksponensial, dan cara menghitung kompleksitas seperti itu dibahas di cara menghitung Big O dari kode.

Perhatikan juga: walaupun ada 15 pemanggilan, kedalaman stack maksimum hanya 5 frame (jalur f(5), f(4), f(3), f(2), f(1)). Pohon menunjukkan total kerja, sedangkan kedalaman pohon menunjukkan berapa banyak frame yang hidup bersamaan.

#Kesalahan yang paling sering di tugas rekursi

#Base case tidak pernah tercapai untuk input negatif

faktorial(-1) memanggil faktorial(-2), lalu faktorial(-3), dan tidak pernah sampai ke 0. Program berhenti dengan RecursionError. Mengubah base case menjadi n <= 1 memang menghentikan rekursinya, tapi diam-diam mengembalikan 1 untuk input negatif, yang secara matematis salah. Lebih jujur menolak input itu:

def faktorial(n):
    if n < 0:
        raise ValueError("faktorial tidak terdefinisi untuk bilangan negatif")
    if n == 0:
        return 1
    return n * faktorial(n - 1)

#Lupa return di langkah rekursif

def faktorial(n):
    if n == 0:
        return 1
    n * faktorial(n - 1)    # hasilnya dihitung lalu dibuang

Fungsi Python tanpa return mengembalikan None. Akibatnya faktorial(1) menghasilkan None, dan faktorial(2) langsung crash dengan TypeError: unsupported operand type(s) for *: 'int' and 'NoneType', karena mencoba menghitung 2 * None. Pesan error ini tidak menyebut kata "return" sama sekali, itu sebabnya sering membingungkan. Kesalahan sejenis, memakai print di tempat return, dibahas di fungsi Python: print vs return.

#Base case Fibonacci yang kurang satu

def fib(n):
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Kelihatannya aman, tapi fib(2) memanggil fib(0), dan fib(0) tidak cocok dengan n == 1, jadi lanjut ke fib(-1), fib(-2), dan seterusnya. Setiap rumus rekursif yang memanggil n - 2 butuh dua base case, atau satu kondisi n < 2.

#Bagaimana memperbaiki RecursionError?

Pesan lengkapnya diawali RecursionError: maximum recursion depth exceeded. Python membatasi kedalaman stack, dan nilai bawaannya bisa dicek dengan sys.getrecursionlimit(), yang biasanya mengembalikan 1000. Karena beberapa frame sudah terpakai oleh interpreter, batas efektifnya sedikit di bawah itu. Di percobaan dengan batas bawaan, faktorial(997) masih jalan dan faktorial(998) sudah gagal, walau angka persisnya bisa bergeser antara versi dan lingkungan.

Urutan diagnosisnya:

1. Cek input yang kamu berikan. Kalau inputnya kecil (misalnya 5) dan tetap RecursionError, hampir pasti base case-nya tidak tercapai. Ini bug, bukan batas memori.
2. Tambahkan print(n) di baris pertama fungsi. Kalau angkanya terus turun melewati nol ke negatif, kamu sudah menemukan masalahnya.
3. Kalau inputnya memang besar (ribuan) dan logikanya benar, ubah ke versi iteratif. Menaikkan batas dengan sys.setrecursionlimit(10000) bisa membuat Python crash total kalau stack sistem operasi habis, jadi itu bukan perbaikan untuk tugas.

Error Python lain yang sering muncul di tugas pemrograman dasar dikumpulkan di error Python pemula dan cara memperbaikinya.

#Memoization: rekursi yang tidak menghitung ulang

Masalah utama fib versi polos adalah fib(3) dihitung dua kali, fib(2) tiga kali, dan seterusnya. Memoization menyimpan hasil yang sudah pernah dihitung sehingga pemanggilan berikutnya cukup mengambil dari tabel.

from functools import lru_cache

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

Dengan dekorator ini, badan fungsi hanya dijalankan sekali untuk setiap nilai $n$ dari 0 sampai 30, total 31 kali, untuk menghitung fib(30). Bandingkan dengan 2.692.537 kali di versi tanpa memo. Kalau dosen melarang lru_cache, versi manualnya memakai dictionary:

memo = {0: 0, 1: 1}

def fib(n):
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

#Kapan sebaiknya memakai versi iteratif?

Faktorial dan Fibonacci sebenarnya lebih alami ditulis dengan loop:

def faktorial_iter(n):
    hasil = 1
    for i in range(2, n + 1):
        hasil *= i
    return hasil

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Tracing fib_iter(5): pasangan $(a,b)$ berubah dari $(0,1)$ menjadi $(1,1)$, $(1,2)$, $(2,3)$, $(3,5)$, lalu $(5,8)$. Nilai a terakhir adalah 5, sama dengan versi rekursif.

Rekursi tetap pilihan terbaik untuk struktur yang memang bercabang, seperti pohon dan graf. Menelusuri pohon biner dengan rekursi jauh lebih pendek daripada dengan loop dan stack manual, seperti yang terlihat di traversal pohon biner preorder, inorder, postorder.

#FAQ

#Apa beda rekursi langsung dan tidak langsung?

Rekursi langsung terjadi saat fungsi A memanggil A. Rekursi tidak langsung terjadi saat A memanggil B dan B memanggil A lagi, misalnya fungsi genap(n) yang memanggil ganjil(n - 1). Keduanya tetap butuh base case yang pasti tercapai.

#Apakah Python mendukung tail recursion optimization?

Tidak. Walaupun pemanggilan rekursifnya ada di baris terakhir, Python tetap membuat frame baru untuk setiap panggilan. Karena itu fungsi rekursif ekor di Python tetap terkena batas rekursi, beda dengan beberapa bahasa fungsional.

#Berapa kedalaman stack untuk fib(n) polos?

Sekitar $n$ frame, karena jalur terpanjang adalah fib(n), fib(n-1), sampai fib(1). Jumlah pemanggilannya jauh lebih besar dari itu, tapi frame yang hidup bersamaan paling banyak sepanjang jalur terdalam.

#Kenapa fungsi rekursifku mengembalikan None?

Hampir pasti baris langkah rekursifnya tidak diawali return. Untuk input 0 hasilnya benar karena base case punya return. Untuk input 1, hasil perkalian dihitung lalu dibuang sehingga keluar None, dan untuk input 2 ke atas None itu ikut dikalikan sehingga muncul TypeError.

#Apakah setiap fungsi rekursif bisa diubah jadi iteratif?

Bisa. Caranya menyimpan sendiri apa yang biasanya disimpan call stack, misalnya dengan list yang dipakai sebagai stack. Untuk faktorial dan Fibonacci hasilnya sederhana, sedangkan untuk traversal pohon versi iteratif biasanya lebih panjang dan lebih rawan salah.