Penjelasan rekursi: cara kerja dan contoh di Python

Masalah apa yang diselesaikan rekursi

Sebagian masalah didefinisikan dengan dirinya sendiri. Sebuah folder berisi file dan folder lain. Node tree punya sub-tree sebagai anak. Faktorial n adalah n dikali faktorial n − 1. Menulis semua itu dengan perulangan biasa sering kali membutuhkan stack eksplisit untuk pekerjaan yang tertunda; dengan rekursi, bahasa pemrograman yang menyimpan stack itu untuk Anda.

Fungsi rekursif punya dua bagian:

• Base case: input terkecil yang dijawab langsung. Untuk faktorial, 0! = 1.
• Kasus rekursif: perkecil masalahnya, panggil fungsi pada bagian yang lebih kecil, lalu gabungkan hasilnya. Untuk faktorial, n! = n × (n − 1)!.

def factorial(n):
    if n == 0:                  # base case
        return 1
    return n * factorial(n - 1) # recursive case
print(factorial(5))   # 120

Call stack, ditelusuri langkah demi langkah

Setiap pemanggilan mendapat frame sendiri di call stack, berisi salinan n miliknya sendiri. Pemanggilan turun sampai base case, lalu hasilnya naik kembali dalam urutan terbalik.

Kedalaman stack di sini adalah n + 1 frame, sehingga ruang tambahannya O(n) meskipun tidak ada list yang dibuat.

Rekursi pada data bersarang

Rekursi paling berguna ketika bentuk datanya sendiri rekursif. Fungsi ini menjumlahkan semua angka dalam list yang mungkin berisi list lain, pada kedalaman berapa pun.

def deep_sum(items):
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)   # same problem, smaller piece
        else:
            total += x
    return total
print(deep_sum([1, [2, 3], [4, [5, [6]]]]))   # 21

Pola yang sama dipakai untuk menelusuri pohon direktori, dokumen JSON, DOM HTML, atau binary tree: tangani node saat ini, lalu lakukan rekursi ke setiap anaknya.

def power_set(items):
    if not items:
        return [[]]
    rest = power_set(items[1:])
    return rest + [[items[0]] + s for s in rest]
print(power_set([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Kompleksitas fungsi rekursif

Perkirakan biayanya sebagai (jumlah pemanggilan) × (pekerjaan per pemanggilan). Ruang minimal sebesar kedalaman stack maksimum.

Rekurensi divide-and-conquer seperti T(n) = 2T(n/2) + O(n) pada merge sort menghasilkan O(n log n). Fungsi yang memanggil dirinya dua kali pada n − 1 tumbuh secara eksponensial.

Memoization: berhenti mengulang pekerjaan

Fungsi Fibonacci yang naif menghitung ulang nilai yang sama berkali-kali: fib(5) memanggil fib(3) dua kali dan fib(2) tiga kali. Menyimpan setiap hasil di cache saat pertama kali dihitung mengubah waktu eksponensial menjadi linear. functools.lru_cache di Python (atau functools.cache, Python 3.9+) melakukannya dengan satu decorator.

from functools import lru_cache
def fib_slow(n):
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib_slow(20))   # 6765, about 22,000 calls
print(fib(90))        # 2880067194370816120, 91 distinct calls

Rekursi dengan memoization adalah bentuk top-down dari dynamic programming. Bentuk bottom-up mengisi tabel dengan perulangan.

Batas rekursi dan mengubahnya menjadi perulangan

Anda bisa menaikkan batas dengan sys.setrecursionlimit(), tetapi rekursi yang sangat dalam tetap bisa membuat interpreter crash. Untuk input yang mungkin dalam, seperti linked list berisi sejuta node atau tree yang degenerate, tulis ulang fungsinya dengan perulangan dan stack eksplisit.

def deep_sum_iter(items):
    total, stack = 0, [items]
    while stack:
        current = stack.pop()
        for x in current:
            if isinstance(x, list):
                stack.append(x)
            else:
                total += x
    return total
print(deep_sum_iter([1, [2, 3], [4, [5, [6]]]]))   # 21

Kesalahan umum

• Base case hilang atau tidak pernah tercapai, misalnya factorial(-1) dengan kode di atas tidak pernah mencapai 0 dan berakhir dengan RecursionError.
• Kasus rekursif yang tidak memperkecil input, seperti memanggil f(n) dari dalam f(n).
• Lupa return hasil rekursif: factorial(n - 1) tanpa return menghasilkan None.
• Menyalin data pada setiap pemanggilan. items[1:] menyalin list, sehingga rekursi pada slice dari list panjang berbiaya waktu O(n²); kirim indeks sebagai gantinya.
• Memakai argumen default yang mutable seperti def f(x, seen=[]) untuk membawa state antar pemanggilan; list yang sama dipakai bersama oleh setiap pemanggilan fungsi.

Kapan memakai rekursi

Pakai rekursi ketika data atau masalahnya memang rekursif: tree, graf (depth-first search), struktur bersarang, parsing ekspresi, backtracking (permutasi, N-Queens, sudoku), dan divide and conquer (merge sort, quicksort, binary search). Pakai perulangan ketika masalahnya berupa urutan sederhana, atau ketika kedalamannya bisa tumbuh mengikuti ukuran input di Python.

Dalam wawancara kerja, pertanyaan rekursi biasanya menguji apakah Anda bisa menyebutkan base case, kasus rekursif, biaya waktu dan ruang termasuk stack, serta kapan memoization membantu.