Rekursi atau recursion dalam matematika dan ilmu komputer diartikan sebagai fungsi yang dalam definisinya mengimplementasikan dirinya sendiri. Untuk lebih mudahnya, bisa dikatakan bahwa rekursi adalah fungsi yang memanggil dirinya sendiri.

Namun demikian, rekursi tidaklah hanya merupakan istilah eksak semata. Jika kita mau memperhatikan lagi dengan lebih teliti, ternyata ada banyak contoh rekursi di sekeliling kita. Rekursi dalam dunia nyata bisa terjadi salah satunya adalah jika kita meletakkan dua cermin secara berhadapan dan sejajar. Bayangan yang terjadi pada kedua cermin itulah rekursi. Contoh lain dari rekursi di dunia nyata adalah seperti yang diperlihatkan gambar-gambar di bagian akhir tulisan ini.

Dalam dunia matematika dan komputer, rekursi khususnya digunakan untuk menyelesaikan perhitungan yang rumit dan kompleks. Prinsip rekursi sebenarnya sederhana, yaitu memecah masalah menjadi masalah-masalah yang lebih kecil. Dengan memecah masalah menjadi bagian-bagian yang lebih kecil tersebut, masalah yang sangat kompleks dan rumit sekalipun akan lebih mudah untuk diselesaikan.

Contoh paling populer implementasi rekursi adalah penyelesaian perhitungan faktorial dari suatu bilangan bulat (integer number). Dalam matematika, faktorial didefinisikan sebagai berikut:

dan

Sehingga didapat misalnya nilai faktorial dari bilangan 5 dan 6 adalah sebagai berikut:

dan

Perhatikan contoh source code yang ditulis dalam bahasa pemrograman C++ berikut. Source code berikut adalah contoh penyelesaian komputasi faktorial tanpa menggunakan teknik rekursi.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
typedef unsigned int UINT;
 
long Factorial(UINT aNumber)
{
    if (aNumber == 0)
    {
        return 1;
    }
 
    long result = 1;
    for (UINT i = 0; i < aNumber; i++)
    {
        result = result*(i + 1);
    }
 
    return result;
}
 
int main()
{
    std::cout << Factorial(6);
    return 0;
}

Sedangkan contoh penyelesaian komputasi faktorial dengan teknik rekursi adalah seperti contoh berikut.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iostream>
typedef unsigned int UINT;
 
long Factorial(UINT aNumber)
{
    if (aNumber == 0)
        return 1;
 
    return aNumber*Factorial(aNumber-1);
}
 
int main()
{
    std::cout << Factorial(5);
    return 0;
}

Seperti yang diperlihatkan contoh ke-dua, fungsi Factorial dalam implementasinya ternyata memanggil dirinya sendiri. Rekursi dapat dibayangkan sebagai proses berantai yang berjalan tanpa perulangan (looping) secara eksplisit dan prosesnya bisa jadi tak berhingga. Untuk menghindari infinite process (proses yang tidak berkesudahan), fungsi yang mengimplementasikan rekursi harus menambahkan syarat yang mendefinisikan kondisi di mana proses rekursi selesai dilakukan. Pada contoh ke-dua, syarat yang dimaksud ditunjukan seperti pada baris ke-enam dan ke-tujuh:

    if (aNumber == 0)
        return 1;

Dengan penambahan kondisi seperti di atas, maka proses komputasi pada fungsi factorial dengan rekursi tersebut akan berhenti jika nilai masukan dari fungsi telah sama dengan nol (0).

Semoga bermanfaat. ***