Rekursi

Fungsi yang memanggil dirinya sendiri, base case, call stack, dan kapan rekursi jadi lambat.

Rekursi adalah teknik menyelesaikan masalah dengan memecahnya menjadi versi yang lebih kecil dari masalah yang sama, lalu memanggil fungsi yang sama untuk menyelesaikannya.

Setiap fungsi rekursif yang benar punya dua bagian:

Base case: kasus paling sederhana yang jawabannya langsung diketahui, tanpa memanggil diri sendiri.
Recursive case: memanggil diri sendiri dengan input yang lebih dekat ke base case.

Contoh: faktorial

Secara matematis $n! = n \times (n-1)!$ dengan $0! = 1$ . Definisinya sudah rekursif, jadi kodenya hampir sama persis:

Call stack

Setiap pemanggilan fungsi membuat frame baru di call stack. faktorial(4) menunggu faktorial(3), yang menunggu faktorial(2), dan seterusnya. Setelah base case tercapai, hasilnya “mengalir balik” ke atas.

Rekursi bercabang: Fibonacci

$F(n) = F(n-1) + F(n-2)$ dengan $F(0)=0, F(1)=1$ . Versi naif memanggil dua cabang setiap kali, sehingga banyak nilai yang dihitung berulang-ulang. Kompleksitasnya eksponensial, sekitar $O(1{,}6^n)$ .

Dengan memoization (menyimpan hasil yang sudah dihitung), Fibonacci menjadi $O(n)$ . Ide ini adalah pintu masuk ke dynamic programming yang dibahas di Analisis dan Strategi Algoritma.

Rekursi vs iterasi

Semua rekursi bisa diubah menjadi iterasi (dengan loop, kadang dibantu stack eksplisit), dan sebaliknya.

Rekursi cocok untuk struktur yang memang rekursif: tree, divide and conquer, backtracking.
Iterasi biasanya lebih hemat memori karena tidak menumpuk frame di call stack.

Ikuti frame saat turun dan kembali

Prediksi nilai yang dikembalikan sebelum memajukan visual. Urutan stack ditulis dari bawah ke atas.

Call stack bertambah lalu kembali

	Frame aktif	Nilai kembali
Atas	f(1)	·
Tengah	f(2)	·
Bawah	f(3)	·

1/3Turun dari 3. Setiap panggilan menunggu hasil dari n yang lebih kecil.f(3) → f(2) → f(1)

Latihan: Pangkat Cepat, Fibonacci.