Rekursi

Rekursi adalah teknik menyusun prosedur yang memanggil dirinya sendiri untuk menyelesaikan masalah yang lebih kecil daripada masalah semula. Setiap prosedur rekursif bertumpu pada dua bagian, yaitu kasus dasar (base case) yang berhenti tanpa memanggil lagi, dan langkah rekursif yang memanggil dirinya dengan masukan yang mendekati kasus dasar. Topik ini membahas pembentukan kedua bagian itu, contoh faktorial dan penjumlahan digit beserta jejak panggilannya, risiko kehilangan kasus dasar, dan pembandingnya berupa versi perulangan.

Kasus dasar dan langkah rekursif#

Kasus dasar adalah kondisi paling sederhana yang jawabannya diketahui tanpa perlu pemanggilan lagi, dan langkah rekursif adalah rumus yang menyatakan masalah besar dengan bantuan masalah yang lebih kecil. Untuk faktorial, kasus dasarnya adalah $n \le 1$ yang hasilnya 1, sedangkan langkah rekursifnya menyatakan $n!$ dengan bantuan $(n-1)!$.

Dua bagian itu diterjemahkan hampir kata demi kata ke dalam kode. Percabangan If menampung kasus dasar dan segera menjalankan Return, sedangkan baris sesudahnya memuat langkah rekursif yang memanggil fungsi itu sendiri dengan n - 1. Kunci keberhentiannya ada pada argumen yang selalu berkurang, karena tanpa pengurangan itu, pemanggilan berikutnya tidak pernah mendekati kasus dasar.

' tidak-dijalankan
Function Faktorial(n As Integer) As Integer
    If n <= 1 Then
        Return 1              ' kasus dasar
    End If
    Return n * Faktorial(n - 1)   ' langkah rekursif
End Function

Faktorial dan penjumlahan digit#

Program berikut memuat dua fungsi rekursif, yaitu Faktorial dan JumlahDigit, ditambah satu versi perulangan sebagai pembanding. Fungsi JumlahDigit memisahkan digit terakhir dengan n Mod 10 dan memproses sisanya dengan n \ 10, sehingga angka 4271 diurai menjadi 1, 7, 2, dan 4. Jalankan dengan dotnet run dan cocokkan angkanya secara manual, karena nilainya sengaja kecil.

Module Program
    Function Faktorial(n As Integer) As Integer
        If n <= 1 Then
            Return 1
        End If
        Return n * Faktorial(n - 1)
    End Function

    Function FaktorialPerulangan(n As Integer) As Integer
        Dim hasil As Integer = 1
        For i As Integer = 2 To n
            hasil *= i
        Next
        Return hasil
    End Function

    Function JumlahDigit(n As Integer) As Integer
        If n < 10 Then
            Return n
        End If
        Return (n Mod 10) + JumlahDigit(n \ 10)
    End Function

    Sub Main()
        For n As Integer = 1 To 6
            Console.WriteLine($"{n}! = {Faktorial(n)}")
        Next
        Console.WriteLine($"Jumlah digit 4271: {JumlahDigit(4271)}")
        Console.WriteLine($"Perulangan 5!    : {FaktorialPerulangan(5)}")
    End Sub
End Module

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
Jumlah digit 4271: 14
Perulangan 5!    : 120

Keluaran menunjukkan deret faktorial 1 sampai 6 sesuai perhitungan manual, yaitu 1, 2, 6, 24, 120, dan 720. Penjumlahan digit 4271 menghasilkan 14 karena $4 + 2 + 7 + 1 = 14$, dan versi perulangan menghasilkan 120 yang sama persis dengan versi rekursifnya untuk $5!$. Kedua hasil terakhir itu menjadi bukti bahwa masalah yang sama dapat dipecahkan dengan dua gaya berbeda.

Jejak pemanggilan#

Setiap pemanggilan prosedur mendapat satu bingkai (frame) sendiri pada tumpukan panggilan (call stack), berisi salinan parameternya dan posisi eksekusinya. Pada Faktorial(4), lima bingkai terbentuk secara berurutan, dan bingkai terakhir yang menemukan kasus dasar menjadi bingkai pertama yang selesai. Hasilnya kemudian naik kembali satu per satu, dari 1, lalu $2 \times 1 = 2$, lalu $3 \times 2 = 6$, sampai $4 \times 6 = 24$.

Diagram berikut menggambarkan urutan turun dan naik itu. Arah ke bawah adalah pembentukan bingkai, sedangkan arah ke atas adalah pengembalian nilainya.

Kedalaman tumpukan sebanding dengan banyaknya pemanggilan yang belum selesai, sehingga Faktorial(1000) membutuhkan sekitar seribu bingkai sekaligus. Batas kedalaman ini terasa pada masukan yang besar, dan itulah salah satu alasan versi perulangan tetap relevan.

Tanpa kasus dasar#

Kehilangan kasus dasar membuat pemanggilan tidak pernah berhenti, dan setiap panggilan baru menambah satu bingkai sampai memori tumpukan habis. Ketika batas itu terlampaui, runtime melempar StackOverflowException, dan pada .NET modern error ini menghentikan proses serta tidak dapat ditangani dengan blok Try/Catch. Program yang mengalami kejadian ini tidak menghasilkan keluaran yang bermakna, sehingga potongan berikut sengaja tidak dieksekusi di sandbox.

' tidak-dijalankan
Function TanpaHenti(n As Integer) As Integer
    Return n * TanpaHenti(n - 1)
End Function
' Setiap panggilan mengurangi n tanpa syarat berhenti,
' sehingga bingkai tumpukan bertambah terus sampai proses
' dihentikan oleh StackOverflowException.

Bentuk keliru lain mirip dengan di atas, yaitu kasus dasar ada tetapi tidak pernah tercapai. Syarat n = 0 pada fungsi yang dikirim n - 2 melompati angka 0 ketika mulai dari angka ganjil, dan pemanggilan terus melewati kasus dasarnya. Ujilah rekursi dengan masukan kecil terlebih dahulu, lalu periksa bahwa setiap cabang argumennya benar-benar mendekati syarat berhenti.

Rekursi dibanding perulangan#

Setiap rekursi dapat ditulis ulang menjadi perulangan, dan FaktorialPerulangan pada program di atas membuktikannya untuk kasus faktorial. Perulangan hanya menggunakan satu variabel akumulator, sehingga kebutuhan memorinya konstan, sedangkan rekursi menumpuk satu bingkai untuk setiap panggilan yang belum selesai. Untuk perhitungan beruntun sederhana, perulangan adalah bentuk yang lebih hemat.

Rekursi tetap unggul ketika struktur datanya memang mengulang dirinya sendiri, misalnya menelusuri isi folder yang di dalamnya berisi folder lagi, atau menghitung penjumlahan digit yang bagiannya adalah angka yang lebih pendek. Pada kasus semacam itu, versi rekursifnya lebih pendek dan lebih dekat dengan deskripsi masalahnya. Kriteria pilihannya sederhana, yaitu perulangan untuk perhitungan beruntun dan rekursi untuk struktur yang bersarang.

Kesalahan umum#

Kesalahan pertama adalah menguji rekursi langsung dengan masukan besar. Satu langkah logika yang keliru pada masukan 1000 sulit dibaca dari keluarannya, sedangkan pada masukan 4 atau 5 setiap tingkatan panggilan masih dapat dihitung manual. Mulailah dari kasus terkecil, lalu naikkan perlahan setelah jejaknya benar.

Kesalahan kedua adalah langkah rekursif yang tidak mengurangi masalah, misalnya memanggil diri dengan argumen yang sama atau yang bergerak menjauh dari kasus dasar. Gejalanya sama persis dengan hilangnya kasus dasar, yaitu tumpukan yang meluap. Pastikan setiap pemanggilan rekursif menggunakan nilai yang lebih dekat ke syarat berhenti, misalnya n - 1 untuk faktorial dan n \ 10 untuk penjumlahan digit.

Kesalahan ketiga adalah menempatkan pekerjaan setelah pemanggilan rekursif tanpa sadar. Baris sesudah Return n * Faktorial(n - 1) tidak pernah dijalankan karena Return langsung menutup panggilan. Rancang urutannya dengan jelas, yaitu kerjakan hitungan, simpan hasilnya, lalu kembalikan nilainya.

Ringkasan#

• Prosedur rekursif memuat kasus dasar yang berhenti tanpa memanggil lagi dan langkah rekursif yang memanggil dirinya dengan masukan yang mendekati kasus dasar.
• Setiap panggilan mendapat satu bingkai pada tumpukan panggilan, hasilnya naik kembali dari kasus dasar ke pemanggil terluar, dan kedalamannya sebanding dengan banyaknya panggilan yang belum selesai.
• Rekursi tanpa kasus dasar yang tercapai berakhir dengan StackOverflowException yang menghentikan proses, sedangkan versi perulangan dengan akumulator menjadi pembanding yang lebih hemat memori.

Referensi#

• Recursive Procedures — Microsoft Learn — Kondisi berhenti, penggunaan memori, dan pengujian prosedur rekursif.
• StackOverflowException Class — Microsoft Learn — Perilaku kelebihan tumpukan dan catatan bahwa exception ini tidak dapat ditangkap.
• Return Statement — Microsoft Learn — Perilaku Return yang langsung mengembalikan kendali ke pemanggil.