Faktorial dari 5 ditulis 5! = 5 × 4 × 3 × 2 × 1, dan definisinya memang berulang pada ukuran yang lebih kecil: 5! = 5 × 4!. Masalah yang definisinya merujuk dirinya sendiri paling natural diselesaikan oleh method yang memanggil dirinya sendiri. Method dengan perilaku seperti itu disebut recursive method (method rekursif).

Dua Syarat Rekursi #

Setiap recursive method wajib memiliki dua bagian:

  1. Base case: kondisi yang menghentikan panggilan berikutnya dan mengembalikan nilai langsung tanpa memanggil diri sendiri.
  2. Recursive case: cabang yang memanggil method itu sendiri dengan masukan yang mendekati base case pada setiap langkah.

Tanpa base case, panggilan akan menumpuk terus dan program berhenti dengan galat.

Contoh Lengkap #

csharp 
static class Rekursi
{
    public static int HitungFaktorial(int n)
    {
        if (n <= 1)
        {
            return 1;
        }
        return n * HitungFaktorial(n - 1);
    }

    public static void HitungMundur(int n)
    {
        if (n < 1)
        {
            return;
        }
        Console.WriteLine($"Detik {n}");
        HitungMundur(n - 1);
    }
}

int hasil = Rekursi.HitungFaktorial(5);
Console.WriteLine($"5! = {hasil}");
Rekursi.HitungMundur(3);

Output yang Dihasilkan:

text 
5! = 120
Detik 3
Detik 2
Detik 1

Mari kita telusuri alur HitungFaktorial(5):

  1. Baris 5-8 (base case): selama n masih di atas 1, kondisi ini dilewati; kondisi baru terpenuhi ketika n mencapai 1, yang langsung mengembalikan 1 tanpa panggilan baru.
  2. Baris 9 (recursive case): HitungFaktorial(5) menunggu hasil HitungFaktorial(4), yang menunggu HitungFaktorial(3), dan seterusnya hingga HitungFaktorial(1).
  3. Setelah base case mengembalikan 1, hasil dikembalikan berlapis: 1 × 2 = 2, lalu 2 × 3 = 6, 6 × 4 = 24, dan 24 × 5 = 120.
  4. Baris 12-20 (HitungMundur): rekursi bertipe void; base case memakai return; tanpa nilai untuk berhenti, dan setiap tingkat mencetak pesannya sebelum memanggil diri dengan n - 1.

Setiap panggilan menyimpan satu frame di call stack — memori untuk melacak titik kembali. Frame bertumpuk selama rekursi berjalan dan terkuras satu per satu saat hasil mulai dikembalikan.

Cara membaca rekursi yang paling ringkas: percayai bahwa panggilan untuk ukuran lebih kecil mengembalikan hasil yang benar, lalu pastikan langkah saat ini benar. Untuk HitungFaktorial, keyakinannya berbunyi: HitungFaktorial(n - 1) mengembalikan (n-1)!, sehingga n * HitungFaktorial(n - 1) menjadi n!. Melacak seluruh panggilan di kepala justru membuat rekursi terasa sulit.

Banyak persoalan berulang sebenarnya lebih ringan diselesaikan dengan loop. Rekursi paling bermanfaat ketika struktur masalahnya memang berlapis, misalnya menelusuri struktur bertingkat.