Aplikasi rekursif dalam bahasa programan faktorial,perkalian,fitonacci dan Binary Search

PENGERTIAN REKURSI

                                Rekursi merupakan teknik pemrograman yang menyebabkan suatu fungsi/prosedur memanggil dirinya sendiri. Pemanggilan diri sendiri ini berlangsung terus menerus sampai batas terkecil yang nilai dari fungsi tersebut disebutkan secara eksplisit. Salah satu contoh dari penerapan rekursi adalah perhitungan faktorial. Dalam faktorial, n! = n*(n-1)! dengan pengecualian 0! = 1. Berikut contoh perhitungannya:

     0! = 1
1! = 1          = 1*(0!) = 1
2! = 2*1       = 2*(1!) = 2
3! = 3*2*1    = 3*(2!) = 6
4! = 4*3*2*1 = 4*(3!) = 24
dan seterusnya…

•      Dengan menggunakan pendekatan bahasa pemrograman, contoh perhitungan diatas dapat juga ditulis seperti berikut ini:

 faktorial(0) = 1
faktorial(1) = 1 * faktorial(0)
faktorial(2) = 2 * faktorial(1)
faktorial(3) = 3 * faktorial(2)
faktorial(4) = 4 * faktorial(3)

Atau lebih singkatnya yaitu:

       if (n == 0)
  faktorial(n) = 1;
else
  faktorial(n) = n * faktorial(n-1);

                               

                 Sampai disini sudah mulai terlihat jelas wujud dari penerapan rekursi. Fungsi faktorial(n) diatas adalah contoh dari rekursi.

Berikut ini contoh program menerapkan rekursi dalam  faktorial:

•      #include <stdio.h>

•      long int faktorial(int N);

•      main()

•      {

•      long int f;

•      int n;

•      clrscr();

•      printf("Program Menghitung Faktorial \n \n");

•      printf("Masukkan suatu bilangan bulat : ");

•      scanf("%d",&n);

•      if (n<0)

•      {

•      printf("Bilangan harus positif!");

•      } else {

•      f = faktorial(n);

•      printf("Nilai %d! adalah : %ld", n, f);

•      }

•      }

•      long int faktorial(int N)

•      {

•      long int F;

•      if (N<=1)

•      {

•      return(1);

•      } else {

•      F = N * faktorial(N-1);

•      return(F);

•      }

•      }

•       

Jika program tersebut dijalankan, hasilnya adalah sebagai berikut:
Program Menghitung Faktorial
Masukkan suatu bilangan bulat : 5
Nilai 5! adalah : 120

  
   Rekursif Perkalian

#include
#include
int perkalian(int, int);
void main()
{
int bil1, bil2;
puts("Menghitung perkalian dari 2 bilangan");
printf("Masukkan bilangan pertama: ");
scanf("%d", &bil1);
printf("Masukkan bilangan kedua: ");
scanf("%d", &bil2);
printf("Hasil perkalian %d dengan %d adalah: %d\n", bil1, bil2, perkalian(bil1, bil2));
getch();
}

int perkalian(int bilangan1, int bilangan2)
{
if(bilangan2==1)return bilangan1;
else return bilangan1+perkalian(bilangan1,bilangan2-1);

}

Program fibonacci rekursif

                               

 Berikut ini merupakan algoritma untuk menampilkan deret fibonaci dengan rekursif.

•      rumus fibonacci yaitu

•      fibonacci(n)

•      n=1 || n = 0  ->1

•      n>1  -> fibonacci (n-1) + fibonacci (n-2)

•      C/C++ dengan borland turbo C++

#include<iostream.h>
#include <conio.h>
void fibonaci(int n);

•      int main()
{
clrscr ( );
int jumlah;
cout<<"jumlah bilangan Fibonaci yang ingin ditampilkan";
cin >> jumlah;
for(int i=0; i<jumlah; i++)
{

•      fibonaci( jumlah);
}
return 0;

•      }
int fibonaci(int n)
{
if( n<=2)
{
return 1;
}
else
{
return (fibonaci(n-1) + fibonaci (n-2));
}
cout <<"\n";
getch();
}

Hasil jika dijalankan 
 

Binary Search

A. Pengertian Binary Search
               

                Binary Search adalah algoritma pencarian yang lebih efisien daripada algorima Sequential Search. Hal ini dikarenakan algoritma ini tidak perlu menjelajahi setiap elemen dari tabel. Kerugiannya adalah algoritma ini hanya bisa digunakan pada tabel yang elemennya sudah terurut baik menaik maupun menurun. Binary search, Pencarian secara biner, digunakan ketika sebuah komputer harus mencari posisi sebuah simbol dalam daftar urut. Komputer akan mencari simbol dari tengah daftar sampai data terakhir, dan membandingkannya dengan simbol yang sedang dicari. Apabila simbol tersebut sudah ditemukan, pencarian pada setengah daftar sisanya akan dihentikan. Secara umum binary searh adalah sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (array) linear, dengan menghilangkan setengah data pada setiap langkah, dipakai secara luas tetapi tidak secara ekslusif dalam ilmu komputer.

Ø Konsep langkah binary search
Contoh :
a) Mencari bilangan 4 dari bilangan 1,2,3,4,5,6,7
1) Mencari titik tengah dari bilangan 1,2,3,4,5,6,7
2) Nilai titik tengah dari bilangan 1,2,3,4,5,6,7 adalah 4, maka nilai yang dicari bisa langsung di temukan dan proses di hentikan.
b) Mencari bilangan 6 dari bilangan 1,2,3,4,5,6,7
1) Mencari nilai titik tengah dari bilangan yang tersedia yaitu 1,2,3,4,5,6,7
2) Nilai titik tengahnya adalah 4
3) Dari nilai yang dicari (6) apakah sama, kurang dari, atau lebih dari, dari nilai titik tengah
4) Karena nilai yang di cari adalah 6, yaitu lebih dari dari nilai titik tengah (4) maka proses dilanjutkan kekanan/keatas yaitu mencari titik tengah dari 5,6,7
5) Dari bilangan 5,6,7 nilai titik tengahnya adalah 6, maka bilangan yang dicari ditemukan dan proses dihentikan
6) Apabila nilai yang dicari belum ditemukan maka proses akan dilanjutkan sampai bilngan tersebut sudah dicari titik tengahnya semua kemudian proses berhenti.

Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik

•      Algoritma
Kamus
     
 Const N : integer = 8 { misalkan jumlah elemen array maksimum = 8 }
Type A = array [ 1 .. N ] of integer
Cari, BatasAtas, BatasBawah, Tengah : Integer
Ketemu : boolean
ALGORITMA
Input (cari) { meminta nilai data yang akan dicari}
1 { indeks array dimulai dari 1 }¬BatasAtas
N¬BatasBawah
False¬Ketemu
While (BatasAtas < (BatasAtas +¬BatasBawah) and (not ketemu) do Tengah true Else If ( A¬BatasBawah) div 2 If A [Tengah] = cari then Ketemu [Tengah] sortedArray[tengah])
awal = tengah + 1; // Mencari di setengah bagian atas.
else if (key < sortedArray[tengah])
akhir = tengah – 1; // Mencari di setengah bagian bawah.
else
return tengah; // Ketemu. Tunjukkan posisinya.
}
return -(awal + 1); // Gagal menemukan Key yang dicari.

Contoh program binary Search:
Contoh Program Array 
Menghitung banyak bilangan yang muncul
scriptnya:
#include <iostream.h>
int main ()
{
int n, i, j, tot=0, A[50];
cout << “Masukan berapa banyak bilangan :”;
cin >> n;
for (i=0; i<n; i++)
{
cout << “Masukan nilai ke “<< i+1 <<” : “;
cin >> A[i];
}
cout << “Masukan angka yang akan di hitung : “;
cin >> A[i];

for (j=0; j<n; j++)
{
if (A[j]==A[i])
{
tot=tot+1;
}
}
cout << “Maka banyaknya tersebut adalah :” <<tot;
return 0;
}

Hasil jika dijalakan