Algoritma Rekursif C++

Oke sahabat setia syarif soden, ketemu lagi di blog kesayangan kalian. Pada kesempatan kali ini Mimin akan membahas tentang Algoritma Rekursif pada bahasa pemrograman C++.

Untuk para programmer pemula kalian wajib menguasai materi ini agar bisa membuat program yang utuh dan bagus.

Oke kita langsung ke materi pembahasan.

         Definisi Rekursif C++
Sebuah objek dikatakan rekursif jika ia didefinisikan menjadi lebih sederhana dalam terminology dirinya sendiri. Nicklaus Wirth mendefinisikan rekursif  sebagai “sebuah objek dikatakan rekursif jika sebagian terdiri atau didefinisikan dalam hal itu sendiri” (diartikan menggunakan google translate).

Dalam kehidupan sehari-hari banyak terdapat objek yang rekursif di alam.

Daya guna rekursif terletak pada kemampuannya mendefinisikan sekumpulan objek yang tidak terbatas dengan sebuah pernyataan terbatas. Sebuah perhitungan yang tidak terhingga misalnya, dapat digambarkan dengan algoritma rekurif, seolah-olah algoritma tersebut mengandung perulangan yang tidak terlihat secara eksplisit.

Algoritma rekursif untuk menghitung n! sebagai berikut:

Function Fak(n : integer) =>integer
{mengembalikan nilai n! Algoritma rekursif.
Basis : jika n = 0, maka 0! = 1
Rekurens : jika n > 0, maka n! = n x (n-1)!
}
DEKLARASI
-
ALGORITMA
If n = 0 then
Return 1
Else
Return n*Fak(n-1)
End if

Proses Rekursif C++
Banyak objek di dalam matematika yang didefinisikan dengan cara  menyatakan suatu proses yang menghasilkan objek tersebut. Yang pasti, proses tersebut harus berhenti dengan memberikan hasil yang didefinisikan. Sebagai contoh, π diperoleh dengan membagi keliling lingkaran (K) dengan diameternya (D). Algoritmanya sebagai berikut:

1. Baca keliling lingkaran, K
2. Baca diameter  lingkaran, D
3. Hitung π = K/D

Contoh objek lain yang diperoleh dari suatu proses adalah factorial. Factorial dari bilangan bulat tak-negatif n didefinisikan sebagai berikut:

Sebagai contoh,
0! = 1
1! = 1
2! = 1x2
3! = 1x2x3
4! = 1x2x3x4

Algoritma menghitung factorial

Function Faktorial(n : integer =>integer
{mengembalikan nilai n!}
DEKLARASI
I, F : integer
Algoritma
F <= 1
I <= 1
While I ≤ n do
F <= F*I
I < = I + 1
End while
{I > n}
Return F

Skema Umum Prosedur Dan Fungsi Rekursif C++
Algoritma rekursif adalah algoritma yang memanggil dirinya sendiri. Oleh karena itu, algoritma rekursif harus dinyatakan dalam prosedur atau fungsi, karena hanya prosedur dan fungsi yang dapat dipanggil di dalam sebuah program.

Secara umum, skema dasar fungsi rekursif adalah sebagai berikut:

Function F(x : x_type)=> function_type
{mengembalikan nilai F}
DEKLARASI
Y : y_type
ALGORITMA
If T(x) then
Return N(x) {basis}
Else
R1(x)
Return F(g(x))
R2(x)
End if

Peubah x adalah parameter pemanggil prosedur ( dapat berupa parameter by value atau parameter by reference), R1 dan R2 masing-masing adalah prosedur ( atau sekumpulan instruksi) yang dipanggil sebelum dan sesudah pemanggilan rekursif, g adalah fungsi yang mengubah nilai parameter x, T adalah fungsi untuk kasus basis, dan N adalah fungsi jika kasus basis tercapai. Perhatikanlah bahwa R1 dan R2 tidak selalu harus ada.

Bagaiman Program Rekursif C++ Bekerja?
Program dalam suatu bahasa pemrograman tertentu dikompilasi dan ditranslasi ke dalam bahasa mesin oleh program compiler. Memahami cara compiler menangani program rekursif dapat membantu kita untuk:

1. Meminimalkan jumlah parameter yang dilewatkan pada waktu pemanggilan.
2. Mengubah algoritma rekursif menjadi program iterative dengan cara meniru (simulasi) mekanisme pelaksanaan program rekursif.

Pertama-tama kita harus mengetahui mekanisme pemanggilan prosedur  atau fungsi yang ditangani oleh compiler c++. Ketika sebuah prosedur atau fungsi dipanggil, area data di memori dialokasikan untuk pemanggilan tersebut.

Area data ini akan menyimpan:

1. Parameter yang dilewatkan waktu pemanggilan.
2. Semua peubah local di dalam prosedur atau fungsi.
3. Alamat Kembali ( return address ), yaitu alamat instruksi berikutnya di dalam program pemanggil c++ setelah prosedur atau fungsi selesai dilaksanakan.

Setelah mengisi data area, kendali program c++ dipindahkan ke prosedur atau fungsi.
Semua acuan terhadap nilai parameter dan peubah local adalah nilai yang terdapat didalam data area. Bila prosedur atau fungsi selesai dilaksanakan, alamat kembalinya diambil dari area data, kendali program bercabang ke alamat tersebut, dan alokasi memori untuk area data dibebaskan.

Tiap compiler c++ berbeda-beda dalam mengimplementasikan area data, tetapi pada umumnya area data diimplementasikan dalam bentuk tumpukan (stack). Tumpukan (stack) adalah sekumpulan elemen di mana semua penambahan (insert) elemen atau penghapusan (delete) elemen hanya dapat dilakukan pada sebuah sisi yang disebut top.

Dengan menggunakan tumpukan, suatu prosedur atau fungsi tidak kehilangan kendali Ketika memanggil prosedur atau fungsi lainnya. Pada setiap kali pemanggilan, akan dialokasikan memori ( area data ) untuk elemen baru tumpukan, kemudian elemen ini di-push ke dalam tumpukan. Ketika prosedur atau fungsi selesai dilaksanakan, elemen di puncak tumpukan di-pop, alamat kembalinya diambil, dan alokasi memori untuk elemen tersebut dibebaskan.

Kapan Tidak Menggunakan Fungsi Rekursif C++?
Secara intuitif, algoritma rekursif sangat tepat diterapkan untuk persoalan yang alaminya memang rekursif, misalnya persoalan yang menggunakan struktur data rekursif seperti list dan pohon, aplikasi games, dan lain-lain. Persoalan seperti itu didefinisikan dalam hubungan rekursif, dan di sini Teknik pemrograman rekursif menunjukan kedayagunaannya.

Terdapat dua alasan mengapa kita harus mengubah algoritma rekursif menjadi algortma iterative. Pertama, bahasa pemrograman yang akan digunakan tidak mendukung pemanggilan rekursif. Hal ini terjadi pada bahasa pemrograman FORTRAN yang tidak memungkinkan menggunakan rekursifitas, sehingga menghalangi penyelesaian rekursif meskipun cara ini cocok untuk persoalan tertentu.
Kedua, dapat terjadi bentuk rekursif tidak mangkus, memiliki kerumitan yang tidak diperlukan, atau terlalu lambat.

Alas an kedua ditunjukan pada persoalan menentukan deret Fibonacci berikut:

0,1,1,2,3,5,8,13,16,18, …

     Rekursif Dalam Bahasa Pascal, Bahasa C Dan Bahasa C++
Tidak ada perbedaan antara pemanggilan prosedur rekursif dengan prosedur biasa ( tanpa rekursif ) didalam bahasa pascal, bahasa C, maupun bahasa C++. Ketiga bahasa pemrograman ini mendukung rekursifitas.

Contoh program C++ Rekursif

Program rekursif c++ dengan batas akhir

Algoritma pemanggilan fungsi hitungDeret

1. Mulai
2. Inisialisasi x = 3
3. Panggil rekursi (x)
4. Selesai

Kode Program C++ Rekursif
#include <iostream>
#include <stdio.h>
void Rekursif (int n);
int main ()
{
int x=3;
Rekursif(x);
}
void Rekursif (int n)
{
static int j=0;
if (n<=0) return;
printf("rekursif Ke-D\n", ++j);
Rekursif(n-1);
}

Program Faktorial Rekursif C++
Kode Program
#include <iostream>
using namespace std;

long Rekursif_Faktorial(int b)
{
    if (b == 0)
        return 1;
    else
        cout<<"faktorial"<<endl;
        return b * Rekursif_Faktorial(b-1);

}
int main()
{
    int x;

    cout<<"Masukan Angka yang akan difaktorialkan : ";
    cin>>x;
    cout << x <<"! = " << Rekursif_Faktorial(x) <<endl;
    return 0;
}

Hasil Output

Program Rekursif C++ Menulis Angka Dari 0 Ke n
Kode program
#include<iostream>
using namespace std;
int i;
int angka(int n )
{
    cout<<"MASUKKAN ANGKA :";
    cin>>n;
     for (i=0; i<n; i++)
    {
        cout<<"Rekursi Dari 0 Ke N : "<<i;
        cout<<endl;
    }
    return n;
}

int main ()
{
    int n;
    int i;
    cout<<angka(i);
}

Hasil output

Program Rekursif C++ Untuk Membalikkan Kalimat
Kode program
#include<iostream>
#include<string.h>
#include<iomanip>
using namespace std;
char rubah[1000];
void rubah_kalimat( ){
int i,n,p;
cout<<"KATA SETELAH DIBALIK : ";
n=strlen(rubah);
for(i=n-1; i>=0; i--)
{
cout<<rubah[i];
}
}
int main(){
cout<<"MASUKKAN KATA     : "; cin>>rubah;
rubah_kalimat();
}

Hasil output