Rekursi

Rekursi adalah pemanggilan fungsi yang dilakukan berulang-ulang dari dalam fungsi itu sendiri. Saat sebuah fungsi melakukan rekursi, fungsi tersebut membutuhkan percabangan atau perulangan untuk menghentikan rekursi tersebut. Rekursi bisa menjadi seperti "perulangan bercabang" yang memiliki parameter. Jika tidak maka program akan mengalami error karena kekurangan memori. Program di bawah ini tidak akan terhenti sebelum mengalami error atau program dihentikan paksa.
#include <stdio.h>

int ulang(){
    printf("ulangi\n");
    ulang();
    return 0;
} 

int main(){
    ulang();
    return 0; 
}
Jangan compile kode program tersebut!
Program akan error setelah fungsi ulang memanggil "tiruan dari dirinya sendiri" tanpa henti. Jika fungsi melakukan pemanggilan tanpa pernah berhenti maka akan terjadi error karena fungsi membutuhkan ruang di memori untuk menyimpan nilai dari variabel dan parameternya. Rekursi berbeda dengan perulangan menggunakan for atau while yang hanya mengulang-ulang tanpa membutuhkan memori baru. Rekursi selalu membutuhkan memori baru tiap memanggil "tiruan dari dirinya sendiri".

Rekursi memerlukan perulangan atau percabangan yang menggunakan parameter sebagai bagian dari kondisinya. Kondisi dari percabangan atau perulangan diperlukan untuk menentukan syarat dari pemanggilan function. Contoh penggunaan rekursi yang tepat bisa kalian lihat di bawah ini.
#include <stdio.h>

int ulang(int angka){
    if(angka < 5){
        printf("ulangi\n");
        ulang(angka+1);
    }
    return 0;
}

int main(){
    ulang(0);
    return 0;
}
Parameter angka pada function dalam program di atas akan "ditambah satu" dan hasilnya digunakan sebagai parameter pada pemanggilan function berikutnya. Ini seolah-olah sama dengan perulangan, tapi kenyataannya ini adalah cara yang sangat berbeda. Pada perulangan, kita mengganti nilai dari "satu variabel" dan mengecek nilainya hingga kondisi untuk menghentikan perulangan terpenuhi.

Dalam rekursi, function seolah-olah memanggil dirinya sendiri. Tapi, sebenarnya function yang dipanggil hanya tiruan yang sama tugasnya saja. Parameter pada setiap pemanggilan function selalu disimpan di dalam lokasi memori yang berbeda walaupun tugasnya tetap sama.

Rekursi mungkin bisa dianalogikan seperti beberapa orang yang saling bergantian untuk melakukan tugas yang sama. Walaupun tugasnya sama, parameternya selalu diubah setiap pelaku sebelumnya menyampaikan tugas pada orang berikutnya.
#include <stdio.h>

unsigned int ulang(unsigned int angka){
    if(angka < 5){
            printf("memori : %u; ", &angka);
            printf("nilai : %u\n", angka);
            ulang(angka+1);
    }
    return 0;
}

int main(){
unsigned int angka;
    printf("\nPerulangan\n");
    for(angka=0;angka<5;angka++){
        printf("memori : %u; ", &angka);
        printf("nilai : %u\n", angka);
    }
    printf("\nRekursi\n");
    ulang(0);
    return 0;
}

Kode program diatas menunjukkan nilai dan alamat di mana kita menyimpan nilai dalam memori komputer. Pada perulangan, lokasi memori yang digunakan sama sekalipun nilainya berubah. Tapi, pada rekursi, lokasi memori dari parameter yang bernama sama dalam kode program akan berubah setiap ada pemanggilan yang berbeda.

Rekursi akan sangat berguna dalam pengurutan dan pencarian karena dalam satu function kita bisa memanggil beberapa function secara bercabang dan bergantian dengan syarat tertentu. Kita juga bisa juga menyelipkan perulangan dalam function yang menggunakan rekursi.

Sebelum saya akhiri pembahasan ini, saya akan memberi satu contoh lagi tentang penggunaan rekursi, yaitu Algoritma Euclidean yang bisa digunakan untuk mencari FPB dari dua bilangan.
#include <iostream>
using namespace std;

int FPB(int a, int b){
    if(b!=0)a=FPB(b, a % b);
    return a;
}

int main(){
int fpb, a, b;
    cin >> a;
    cin >> b;
    fpb=FPB(a, b);
    cout << "FPB : " << fpb;
    return 0;
}
Silahkan coba program di atas dan ganti input atau parameternya dupaya kalian bisa menganalisanya. Untuk bisa memahami sesuatu saya selalu menggunakan gunakan prinsip "trial, error, and analyze". Beranilah untuk mencoba dan belajarlah dari kesalahan.