Rekursi

Rekursi (recursion) adalah teknik menyusun metode yang memanggil dirinya sendiri pada masukan yang lebih sederhana sampai titik henti tercapai. Topik ini membahas struktur kasus dasar (base case) dan langkah rekursif, kemudian mempraktikkannya pada faktorial dan deret Fibonacci. Setelah topik ini, masalah yang bentuknya berulang dan menyempit dapat dinyatakan sebagai metode rekursif beserta kasus dasar dan batas amannya.

Program faktorial dan Fibonacci#

Program berikut menghitung faktorial untuk nilai 0 sampai 6 dan deret Fibonacci untuk indeks 0 sampai 10 dengan dua metode rekursif. Keduanya dipilih karena definisi matematisnya memang sudah berbentuk rekursif, sehingga terjemahannya ke kode dapat diperiksa baris demi baris. Salin programnya ke berkas Program.cs, lalu jalankan dengan dotnet run --file Program.cs.

// Rekursi: metode memanggil dirinya sendiri dengan masukan yang menyempit.

for (int n = 0; n <= 6; n++)
{
    Console.WriteLine($"{n}! = {Faktorial(n)}");
}

int[] barisan = new int[11];
for (int i = 0; i <= 10; i++)
{
    barisan[i] = Fibonacci(i);
}
Console.WriteLine(string.Join(" ", barisan));

// Kasus dasar: 0! = 1 dan 1! = 1 menghentikan pemanggilan.
// Langkah rekursif: n! = n dikali (n-1)!.
static int Faktorial(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    return n * Faktorial(n - 1);
}

// Kasus dasar: Fibonacci(0) = 0 dan Fibonacci(1) = 1.
// Langkah rekursif: F(n) = F(n-1) + F(n-2).
static int Fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
0 1 1 2 3 5 8 13 21 34 55

Metode Faktorial berhenti pada n <= 1 dengan hasil 1, sedangkan metode Fibonacci berhenti pada kondisi yang sama dengan hasil n itu sendiri. Keduanya menyempitkan masukan pada setiap pemanggilan, yaitu n - 1 untuk faktorial dan n - 1 serta n - 2 untuk Fibonacci, sehingga setiap rantai pemanggilan selalu bergerak menuju kasus dasarnya. Deret Fibonacci dikumpulkan ke dalam array terlebih dahulu, lalu dicetak sekaligus dengan string.Join, sehingga keluarannya menjadi satu baris yang mudah dibaca.

Kasus dasar dan langkah rekursif#

Metode rekursif selalu tersusun atas dua bagian, yaitu kasus dasar yang menjawab masukan paling sederhana tanpa pemanggilan lagi, dan langkah rekursif yang menyatakan masukan besar melalui pemanggilan metode itu sendiri pada masukan yang lebih kecil. Jejak pemanggilan berikut memperlihatkan kedua arah tersebut, yaitu arah turun menuju kasus dasar dan arah kembali merangkai hasilnya.

Console.WriteLine("Mulai");
Console.WriteLine(Turun(3));

// Jejak pemanggilan memperlihatkan arah turun dan arah kembali rekursi.
static string Turun(int n)
{
    Console.WriteLine($"Masuk n = {n}");
    if (n == 0)
    {
        Console.WriteLine("Kasus dasar tercapai");
        return "0";
    }
    string hasil = $"{n} -> {Turun(n - 1)}";
    Console.WriteLine($"Kembali dari n = {n}");
    return hasil;
}

Mulai
Masuk n = 3
Masuk n = 2
Masuk n = 1
Masuk n = 0
Kasus dasar tercapai
Kembali dari n = 1
Kembali dari n = 2
Kembali dari n = 3
3 -> 2 -> 1 -> 0

Pemanggilan Turun(3) menelusuri Turun(2), Turun(1), dan Turun(0) sebelum ada hasil yang bisa dirangkai. Setiap pemanggilan menempati satu bingkai pada stack (stack) pemanggilan, yaitu catatan runtime untuk urutan metode yang sedang berjalan, dan bingkai itu dilepas ketika return tercapai. Pada arah kembali, hasil kasus dasar dirangkai dari dalam ke luar hingga menjadi teks 3 -> 2 -> 1 -> 0, sehingga kedalaman rekursi berbanding lurus dengan pemakaian memorinya.

Faktorial menunjukkan kesesuaian yang hampir satu banding satu antara rumus matematika dan metode rekursifnya.

Bentuk rekursifnya menyatakan $n!$ sebagai $n$ dikali $(n-1)!$, dengan kasus dasar $0! = 1$ dan $1! = 1$. Karena setiap baris kode bertindak sebagai terjemahan langsung dari definisi matematisnya, metode rekursif untuk rumus semacam ini lebih mudah dibaca daripada versi perulangannya.

Setiap rekursi pada prinsipnya dapat ditulis ulang sebagai perulangan, dan sebaliknya perulangan dapat ditulis ulang sebagai rekursi. Rekursi dipilih apabila bentuk masalahnya memang berlapis, misalnya penelusuran struktur bertingkat, sedangkan perulangan lebih diutamakan untuk deret yang berjalan lurus dari awal sampai akhir. Pemilihan keduanya adalah keputusan keterbacaan, bukan keharusan teknis.

Biaya rekursi naif#

Rekursi Fibonacci yang naif memanggil dirinya dua kali pada setiap langkah, sehingga jumlah pemanggilan bertumbuh eksponensial terhadap indeks. Menghitung Fibonacci(10) saja sudah memicu 177 pemanggilan metode, hampir dua kali lipat biaya Fibonacci(9) yang hanya 109 pemanggilan, dan menghitung Fibonacci(30) menuntut lebih dari dua juta pemanggilan dengan sebagian besar memanggilannya menghitung ulang nilai yang sama berulang kali. Teknik penyimpanan hasil antara, yang dikenal sebagai memoisasi (memoization), menghilangkan perhitungan ulang itu dengan mencatat setiap hasil pada struktur pasangan kunci dan nilai, lalu membacanya kembali apabila nilai yang sama diminta lagi.

Batas praktis lainnya ada pada ukuran hasil. Tipe int cukup untuk faktorial sampai $12!$, sedangkan tipe long mencapai $20!$, dan di atas itu hasilnya melebihi kapasitas kedua tipe tersebut tanpa bilangan titik mengambang. Batas ukuran ini bersifat terpisah dari batas kedalaman rekursi, karena satu berbicara tentang nilai, sedangkan yang lain berbicara tentang jumlah bingkai pada stack.

Kesalahan umum#

Perhatikan kesalahan yang paling sering menyerang metode rekursif.

• Kasus dasar yang hilang membuat pemanggilan berlanjut tanpa henti sampai stack habis, dan runtime menghentikan program dengan StackOverflowException, exception yang tidak dapat ditangkap blok catch.
• Langkah rekursif yang tidak menyempitkan masukan, misalnya memanggil metode dengan nilai n yang sama, menghasilkan akibat yang sama dengan kasus dasar yang hilang.
• Kasus dasar yang berhenti terlalu dini mengembalikan hasil untuk masukan yang seharusnya masih dihitung, sedangkan kasus dasar yang terlalu sempit membiarkan pemanggilan berlanjut tanpa arah pada masukan tertentu.

Cara pemeriksaan yang efektif adalah mencoba masukan kecil terlebih dahulu, misalnya memanggil metode faktorial untuk 0, 1, dan 2 sebelum masukan yang lebih besar dipakai. Masukan kecil memaksa kasus dasar dan langkah rekursifnya teruji sekaligus, sehingga cacat struktur terlihat sebelum program dipakai pada masukan yang menumpuk pemanggilannya.

Salinan blok berikut memperlihatkan bentuk paling berbahaya dari kesalahan di atas, yaitu metode rekursif tanpa kasus dasar. Blok ini sengaja tidak dieksekusi karena memang menghentikan program.

// tidak-dijalankan
// Memanggil HitungTurun(3) memicu pemanggilan tanpa henti hingga
// StackOverflowException menghentikan program.

static int HitungTurun(int n)
{
    return HitungTurun(n - 1);
}

Ringkasan#

• Metode rekursif terdiri atas kasus dasar dan langkah rekursif yang menyempitkan masukan pada setiap pemanggilan.
• Setiap pemanggilan menempati satu bingkai pada stack pemanggilan, sehingga kedalaman rekursi berbanding lurus dengan pemakaian memorinya.
• Rekursi Fibonacci naif bertumbuh eksponensial, dan memoisasi menghilangkan perhitungan ulangnya.

Referensi#

• StackOverflowException Class — Microsoft Learn — Dokumentasi exception yang menghentikan program saat stack pemanggilan habis dan tidak dapat ditangkap catch.
• ECMA-334 C# Language Specification — Ecma International — Spesifikasi resmi bahasa C# yang menjadi acuan definisi metode dan pemanggilannya.