Rekursi

Rekursi adalah teknik menyelesaikan masalah dengan fungsi yang memanggil dirinya sendiri pada masukan yang lebih kecil. Setiap fungsi rekursif bertumpu pada dua bagian, yaitu kasus dasar yang menghentikan pemanggilan dan langkah rekursif yang mempersempit masalah. Topik ini membangun tiga contoh klasik, yaitu faktorial, perpangkatan, dan Fibonacci, lalu menilai harga yang dibayarkan atas kejelasan tersebut.

Dua bagian fungsi rekursif#

Kasus dasar adalah masukan terkecil yang jawabannya sudah diketahui tanpa pemanggilan lagi, sedangkan langkah rekursif menyatakan jawaban masukan besar berdasarkan jawaban masukan yang lebih kecil. Definisi faktorial memuat keduanya secara alami:

Baris pertama adalah kasus dasar, sedangkan baris kedua adalah langkah rekursif yang memanggil $n-1$. Setiap pemanggilan fungsi menyimpan parameternya sendiri pada stack frame, sehingga nilai n pada satu tingkat tidak tercampur dengan tingkat lain. Pemanggilan terus menumpuk sampai kasus dasar tercapai, lalu nilai kembali naik lapis demi lapis hingga pemanggil pertama menerima hasil akhirnya.

Menelusuri rekursi dengan tangan adalah keterampilan yang sepadan dengan menulisnya. Untuk faktorial(3), penelusuran menghasilkan bentuk 3 * (2 * 1) setelah kasus dasar faktorial(1) mengembalikan 1. Mulailah selalu dari kasus terkecil, tuliskan nilai kembaliannya, lalu naikkan satu tingkat dengan substitusi. Kebiasaan ini membuat urutan menurun dan menaik terlihat jelas sebelum program dijalankan.

Faktorial#

Definisi di atas diterjemahkan hampir kata demi kata menjadi fungsi C. Kasus dasar ditulis sebagai pernyataan if yang langsung return, sedangkan langkah rekursif menjadi pernyataan return yang memanggil dirinya sendiri.

#include <stdio.h>

unsigned long long faktorial(int n)
{
    if (n <= 1) {
        return 1;                /* kasus dasar */
    }
    return n * faktorial(n - 1); /* langkah rekursif */
}

int main(void)
{
    printf("0!  = %llu\n", faktorial(0));
    printf("5!  = %llu\n", faktorial(5));
    printf("10! = %llu\n", faktorial(10));
    return 0;
}

0!  = 1
5!  = 120
10! = 3628800

Jalur pemanggilan faktorial(3) bergerak dalam dua arah, yaitu menurun ketika fungsi terus memanggil dirinya dan menaik ketika hasil dioper kembali berlapis-lapis. Diagram berikut menelusuri kedua arah itu beserta nilai yang dioper pada setiap tingkat.

Tipe unsigned long long dipilih karena hasil faktorial tumbuh sangat cepat, sehingga 13! saja sudah melampaui kapasitas tipe int 32 bit. Dengan tipe yang lebih lebar, faktorial(20) masih muat, sedangkan faktorial(21) meluap tanpa pesan apa pun. Perhitungan yang meluap tidak menghentikan program, sehingga pemilihan tipe kembali menjadi bagian dari desain fungsi rekursif. Tipe yang lebih besar hanya berbiaya kecil dibandingkan hasil yang salah tanpa terdeteksi.

Perpangkatan#

Definisi rekursif perpangkatan mengikuti pola yang sama, yaitu kasus dasar $b^0 = 1$ dan langkah rekursif $b^e = b \times b^{e-1}$. Eksponen berkurang satu pada setiap tingkat, sehingga kasus dasar pasti dicapai untuk setiap eksponen tak negatif.

#include <stdio.h>

long pangkat(int basis, int eksponen)
{
    if (eksponen == 0) {
        return 1;                /* kasus dasar */
    }
    return basis * pangkat(basis, eksponen - 1);
}

int main(void)
{
    printf("2 pangkat 10 = %ld\n", pangkat(2, 10));
    printf("3 pangkat 4  = %ld\n", pangkat(3, 4));
    printf("5 pangkat 0  = %ld\n", pangkat(5, 0));
    return 0;
}

2 pangkat 10 = 1024
3 pangkat 4  = 81
5 pangkat 0  = 1

Fungsi ini melakukan satu perkalian per tingkat, sehingga jumlah pekerjaannya berbanding lurus dengan eksponen. Definisi rekursifnya hampir identik dengan definisi matematisnya, dan itulah kekuatan utama rekursi. Eksponen negatif perlu ditolak di luar fungsi, karena eksponen yang terus berkurang dari nilai negatif tidak pernah mengenai kasus dasar.

Fungsi pangkat juga memperlihatkan dua jenis parameter yang bekerja berdampingan. Parameter basis tetap dioper apa adanya ke setiap tingkat, sedangkan parameter eksponen bergerak turun menuju kasus dasar. Parameter yang diam seperti ini lazim muncul pada fungsi rekursif, dan penelusurannya cukup mengikuti satu parameter yang bergerak.

Setiap fungsi rekursif pada topik ini juga memiliki padanan iteratif yang menghasilkan keluaran sama persis. Versi iteratif menggunakan perulangan dengan variabel penghitung, sedangkan versi rekursif menyerahkan penghitungan itu kepada tumpukan pemanggilan. Pilihan di antara keduanya biasanya menimbang kejelasan definisi dengan jumlah memori yang dipakai.

Fibonacci dan biaya rekursi#

Deret Fibonacci didefinisikan dengan dua kasus dasar sekaligus, yaitu $F_0 = 0$ dan $F_1 = 1$, sedangkan suku berikutnya memenuhi $F_n = F_{n-1} + F_{n-2}$. Definisi ini langsung menjadi fungsi rekursif bercabang dua.

#include <stdio.h>

int fibonacci(int n)
{
    if (n <= 1) {
        return n;                /* kasus dasar: F(0) = 0, F(1) = 1 */
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(void)
{
    int n;

    for (n = 0; n <= 10; n = n + 1) {
        printf("F(%d) = %d\n", n, fibonacci(n));
    }
    return 0;
}

F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

Kejelasan definisinya memang sulit ditandingi, tetapi ada harga yang harus dibayar. Perhatikan bahwa F(2) adalah pemanggilan pertama yang benar-benar menjalankan penjumlahan, karena F(0) dan F(1) langsung berhenti pada kasus dasar. Setiap pemanggilan fibonacci(n) menumbuhkan dua pemanggilan baru, dan banyak nilai dihitung berulang-ulang, misalnya fibonacci(5) dihitung dua kali selama penelusuran fibonacci(6). Penggandaan ini tumbuh eksponensial, sehingga fibonacci(40) sudah menuntut miliaran pemanggilan meskipun jawabannya hanya satu angka.

Iterasi dengan dua variabel penghitung menghitung deret yang sama dalam waktu berbanding lurus dengan n. Karena itu, rekursi bercabang dua lebih tepat dipandang sebagai latihan struktur daripada solusi yang efisien. Cara paling sederhana menghilangkan penghitungan ulang adalah menghitung deret dari suku terkecil dan menyimpan setiap hasil pada variabel penampung. Teknik menyimpan hasil semacam ini dikenal sebagai memoization, dan kuncinya adalah tidak menghitung ulang suku yang sudah selesai. Dengan penyimpanan itu, jumlah pekerjaan kembali berbanding lurus dengan n tanpa mengubah definisi deretnya.

Kesalahan umum#

Kegagalan rekursi biasanya bersifat total, berupa program yang berhenti mendadak, sehingga pencegahannya jauh lebih murah daripada perbaikannya. Pesan errornya pun jarang menunjuk baris rekursifnya, sehingga kebiasaan menguji kasus terkecil menjadi pertahanan utama.

• Lupa kasus dasar atau salah arah langkah rekursif. Pemanggilan tidak pernah berhenti, stack penuh, dan program berakhir dengan error segmentasi. Uji kasus terkecil terlebih dahulu, misalnya faktorial 0 dan 1, sebelum menguji masukan besar.
• Memanggil dengan masukan yang melampaui batas tipe kembali. faktorial(21) meluap tanpa pesan dan menyisakan angka yang salah. Perbesar tipe kembali atau batasi rentang masukan yang sah, dan pemeriksaan masukan selalu lebih murah daripada mencari hasil yang salah.
• Memakai rekursi bercabang dua untuk deret yang panjang. Biaya eksponensial Fibonacci muncul dari penghitungan berulang, bukan dari rekursi itu sendiri. Simpan hasil yang sudah dihitung atau ubah menjadi iterasi.

Bentuk paling ringkas dari kesalahan pertama adalah fungsi yang langkah rekursifnya tidak pernah berhenti.

// tidak-dijalankan
unsigned long long faktorial_tanpa_henti(int n)
{
    return n * faktorial_tanpa_henti(n - 1);  /* tidak pernah berhenti */
}

Ringkasan#

• Fungsi rekursif selalu memuat kasus dasar dan langkah rekursif yang mempersempit masukan menuju kasus dasar tersebut.
• Setiap pemanggilan menumpuk stack frame sendiri, sehingga parameter pada tiap tingkat bersifat independen dan nilai kembali naik lapis demi lapis.
• Rekursi memperjelas definisi, tetapi cabang yang tumbuh dua arah seperti Fibonacci membawa biaya eksponensial yang diperbaiki dengan iterasi atau penyimpanan hasil.

Referensi#

• Functions — cppreference.com — Aturan pemanggilan fungsi, termasuk pemanggilan fungsi terhadap dirinya sendiri.
• Recursion (computer science) — Wikipedia — Ikhtisar kasus dasar, langkah rekursif, dan biaya komputasi fungsi rekursif.