Recursion

Sebuah function bisa memanggil function lain — dan tidak ada larangan untuk memanggil dirinya sendiri. Teknik ini bernama recursion: masalah besar diselesaikan dengan menyelesaikan versi kecil dari dirinya, berulang sampai tersisa kasus paling kecil yang bisa dijawab langsung. Recursion adalah cara berpikir yang cocok untuk data yang bentuknya juga bersarang — struktur folder di dalam folder, menu di dalam menu. Chapter ini membahas anatomi recursion yang benar dan akibatnya bila kita lupa memberhentikannya.

Dua Bagian Wajib: Base Case dan Recursive Case #

Setiap function rekursif yang sehat memiliki dua bagian:

1. Base case: kondisi paling kecil yang dijawab langsung tanpa memanggil ulang function — titik berhenti recursion.
2. Recursive case: pemanggilan function itu sendiri dengan masukan yang makin mendekati base case.

Contoh paling mudah diamati adalah hitung mundur peluncuran roket:

def hitung_mundur(n):
    if n == 0:
        print("Lepaskan roket!")
        return
    print(n)
    hitung_mundur(n - 1)

hitung_mundur(3)

Output yang Dihasilkan:

3
2
1
Lepaskan roket!

Mari kita telaah apa yang terjadi pada baris-baris kode di atas:

1. Baris 2 (if n == 0:): base case. Ketika hitungan mencapai nol, function mencetak pesan akhir dan berhenti — tidak ada pemanggilan ulang.
2. Baris 4 (print(n)): recursive case mencetak angka saat ini lebih dulu.
3. Baris 5 (hitung_mundur(n - 1)): function memanggil dirinya dengan n - 1 — masukan yang satu langkah lebih dekat ke base case. Rangkaian pemanggilannya: hitung_mundur(3) → hitung_mundur(2) → hitung_mundur(1) → hitung_mundur(0).

Contoh Klasik: Faktorial #

Faktorial dari n (ditulis n!) adalah hasil kali n × (n-1) × ... × 2 × 1. Definisi ini memuat rekursi di dalam matematikanya sendiri: 5! = 5 × 4!, dan 4! = 4 × 3!, sampai 1! = 1:

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

print(faktorial(5))

Output yang Dihasilkan:

120

Alur perhitungannya rapi: faktorial(5) menunggu hasil faktorial(4), yang menunggu faktorial(3), dan seterusnya sampai faktorial(1) mengembalikan 1 lewat base case. Nilai tersebut kemudian naik kembali sambil dikalikan: 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24, 5 × 24 = 120.

Tanpa Base Case: RecursionError #

Hilangkan base case, dan recursion menjadi putaran tanpa akhir. Python menghentikannya dengan paksa melalui RecursionError:

import sys

def panggil_terus():
    return panggil_terus()

try:
    panggil_terus()
except RecursionError:
    print("Program berhenti: RecursionError")

print("Batas recursion:", sys.getrecursionlimit())

Output yang Dihasilkan:

Program berhenti: RecursionError
Batas recursion: 1000

Interpreter Python membatasi kedalaman pemanggilan function untuk melindungi memori stack. Function sys.getrecursionlimit() menunjukkan angkanya: 1000 — nilai bawaan pada Python 3.12. Setiap pemanggilan function yang belum selesai menempati satu slot stack; recursion yang salah arah (base case tak tercapai, atau malah menjauh darinya) menghabiskan seluruh slot tersebut, lalu program dihentikan.

Recursion atau Iteration? #

Hampir semua masalah rekursif bisa juga ditulis dengan loop. Faktorial versi loop:

def faktorial_rekursif(n):
    if n <= 1:
        return 1
    return n * faktorial_rekursif(n - 1)

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

print(faktorial_rekursif(6))
print(faktorial_iteratif(6))

Output yang Dihasilkan:

720
720

Keduanya menghasilkan jawaban yang sama, jadi pilihan ditentukan oleh kejelasan dan biaya:

Untuk masalah datar seperti faktorial atau penjumlahan, loop adalah pilihan yang lebih hemat dan tidak berisiko menghantam batas recursion. Recursion memperoleh nilai sebenarnya pada masalah yang bentuk pohon: menjelajahi direktori yang berisi direktori, memproses menu yang berisi submenu, atau membandingkan struktur JSON bersarang — kode rekursifnya sering lebih pendek dan lebih jelas daripada versi loop-nya.