Rekursi (recursion) adalah istilah yang digunakan dalam bidang matematika dan ilmu komputer, yang artinya adalah fungsi yang mendeskripsikan fungsi itu sendiri. Contoh dari rekursi dalam kehidupan sehari-hari adalah pada saat di dalam elevator ataupun sebuah ruangan yang memiliki cermin di dua sisi yang saling berhadapan 180⁰. Kedalaman rekursi ini tidaklah terbatas, maka dari itu dinamakan rekursi tak terbatas (Infinite Recursion).

Figure 1 Droste effect. Dalam gambar ini ada gambar ini lagi yang di dalamnya ada gambar ini lagi dan seterusnya sampai kedalaman tak terbatas

Dalam bidang komputer, atau lebih tepatnya ke bidang pemrograman, metode rekursi digunakan untuk menghitung suatu bilangan yang memiliki rumus berulang. Contohnya adalah faktorial sebuah bilangan. Bilangan tersebut akan dikalikan dengan bilangan sebelumnya sampai mencapai angka satu. Untuk itu, akan dipanggil rumus = N =N*(N-1) sampai N-1 adalah satu.

Faktorial dari 5

Faktorial dari 6

Contoh lain dari penggunaan metode rekursi dalam ilmu komputer adalah solusi Tower of Hanoi, penghitungan deret fibbonacci, fungsi Ackermann, dan lain-lain.

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; }

Potongan kode sumber di atas adalah penggunaan rekursi dalam mencari faktorial dari sebuah bilangan. Dalam kode di atas adalah faktorial dari 5 (5!).

Rekursi juga dapat bercabang-cabang. Jika dapat digambarkan, maka akan terlihat seperti pohon. Di mana cabang pertama terhubung dengan cabang kedua pada pangkalnya, lalu terhubung lagi ke cabang ketiga, dan seterusnya. Rekursi yang bercabang ini dapat kita gunakan untuk mencari kombinasi dari beberapa karakter atau apapun. Dalam fungsi rekursifnya terdapat perulangan yang menentukan berapa panjang dari kombinasi yang kita inginkan asal tidak melebihi panjang asal.