Rekursi dan Mengapa Python (Tidak) Menyukainya 🌀

Jika dalam wawancara Anda diminta menulis faktorial atau bilangan Fibonacci menggunakan rekursi — tulislah. Tetapi jika Anda sering menggunakannya dalam kenyataan...
Ya, rekursi secara konseptual indah, matematis elegan, tetapi jika berlebihan, Anda bisa menjatuhkan produksi dan memenuhi seluruh RAM dengan bingkai tumpukan.

Mari kita bahas apa yang terjadi di balik layar dan mengapa Python, tidak seperti bahasa fungsional, kurang menyukai rekursi.

1️⃣ Harganya: tumpukan panggilan
Setiap panggilan fungsi tidaklah gratis. Ini menciptakan bingkai tumpukan baru di memori. Bingkai ini menyimpan variabel lokal dan alamat kembali.
Bayangkan boneka bersarang, di mana setiap boneka berikutnya memiliki berat yang sama dengan yang sebelumnya. Di Python, "beban" ini membebani RAM.
Perulangan while atau for menggunakan satu blok memori. Rekursi menghabiskan memori secara linear (atau eksponensial) sebanding dengan kedalaman panggilan.

2️⃣ Mengapa tidak ada optimasi panggilan ekor
Dalam bahasa seperti Haskell atau C++, kompiler pintar. Jika panggilan rekursif adalah tindakan terakhir dalam fungsi (rekursi ekor), ia menggantinya dengan lompatan biasa (GOTO), tanpa membuat bingkai baru. Ini disebut Tail Call Optimization (TCO).

Di Python TCO tidak ada dan tidak akan ada. Guido van Rossum (BDFL) pada prinsipnya menentang TCO di Python. Argumennya sederhana: "Kami ingin melihat jejak kesalahan yang lengkap". Jika tumpukan diciutkan, Anda tidak akan pernah tahu pada putaran rekursi mana semuanya gagal.
Oleh karena itu, batas 1000 panggilan (default) bukanlah bug, melainkan pengaman dari luapan tumpukan. Bisakah ditingkatkan melalui sys.setrecursionlimit? Bisa. Tetapi jika Anda membutuhkannya, 99% kemungkinan Anda salah dengan arsitektur.

3️⃣ Kapan rekursi jahat, dan kapan diperlukan?
❌ Struktur linear (misalnya, daftar): Menghitung faktorial, bilangan Fibonacci, atau melintasi daftar datar. Perulangan iteratif while/for akan selalu lebih cepat dan lebih hemat memori (memori O(1) vs O(N)).
✅ Struktur bercabang (pohon, graf, dict bersarang): Parsing JSON, melintasi sistem file, pohon DOM, atau algoritma Divide and Conquer (QuickSort, MergeSort). Di sini rekursi mengurangi beban kognitif dan membuat kode mudah dibaca.

4️⃣ Obat untuk kelambatan: @lru_cache
Contoh klasik kebodohan adalah menghitung Fibonacci secara "brute force". Kompleksitas O(2^n). Artinya, untuk menghitung angka ke-50, program akan mati sebelum selesai.
Solusinya — Memoization.
Dekorator @functools.lru_cache menyimpan hasil panggilan. Jika fungsi sudah dipanggil dengan argumen ini, Python hanya akan mengambil nilai yang sudah jadi dari tabel hash. Ini mengubah kengerian eksponensial menjadi kompleksitas linear O(N).

Kesimpulan: Python bukan Haskell atau Lisp. Di sini, rekursi adalah warga kelas dua. Gunakan untuk pohon dan graf, tetapi untuk yang lainnya ada perulangan.

#anatomi_python