Sulhansubs: MATERI LOGIKA DAN ALGORITMA PERTEMUAN KE-6

MATERI LOGIKA DAN ALGORITMA PERTEMUAN KE-6

STRUKTUR REKURSIF

Rekursif adalah suatu proses yang bisa memanggil dirinya sendiri.

Contoh konsep penggunaan Rekursif

Masalah :
Memotong Roti tawar tipis-tipis sampai habis

Algoritma :
1.Jika roti sudah habis atau potongannya sudah paling tipis maka pemotongan roti selesai.
2.Jika roti masih bisa dipotong, potong tipis dari tepi roti tersebut, lalu lakukan prosedur 1 dan 2 untuk sisa potongannya.

Contoh Fungsi Rekursif
a. Fungsi pangkat
b. Faktorial
c. Fibonancy
d. Menara Hanoi

Fungsi Pangkat
Menghitung 10 pangkat n dengan menggunakan konsep rekursif.

Secara Notasi pemrograman dapat ditulis :
10^0 = 1 …………………………..(1 )
10^n = 10 * 10 n-1 ........................( 2 )

Contoh :
10^3 = 10 * 10^2
10^2 = 10 * 10^1
10^1 = 10 * 10^0
10^0 = 1

Faktorial
0! = 1
N! = N x (N-1)! Untuk N > 0
Scr notasi pemrograman dapat ditulis sebagai :
FAKT (0) = 1 .............................................. (1)
FAKT(N) = N * FAKT (N-1)...................... (2)

Contoh :
FAKT(5) = 5 * FAKT(4)
FAKT(4) = 4 * FAKT(3)
FAKT(3) = 3 * FAKT(2)
FAKT(2) = 2 * FAKT(1)
FAKT(1) = 1 * FAKT(0)
Nilai Awal

hitung 5!, maka dapat dilakukan secara rekursif dgn cara :
5! = 5 * 4!

Scr rekursif nilai dr 4! Dpt dihitung kembali dgn 4 * 3!,
shg 5! Menjadi :5! = 5 * 4 * 3!

Scr rekursif nilai dr 3! Dpt dihitung kembali dgn 3 * 2!,
shg 5! Menjadi : 5! = 5 * 4 * 3 * 2!

Scr rekursif nilai dr 2! Dpt dihitung kembali dgn 2 * 1,
shg 5! Menjadi : 5! = 5 * 4 * 3 * 2 * 1 = 120.

Contoh Listing Faktorial
#include <iostream.h>
#include <iomanip.h>
Unsigned long faktorial (unsigned long);
Int main()
{
for (int i=0; i:<=10; i++)
cout << setw(2) << i << “! Faktorial(i) << endl;
return 0;
}
// recursive definition of function factorial
Unsigned long factorial (unsigned long number)
{
if (number <=1) // base case
return 1;
else
return number * factorial(number – 1);
}

Fibonancy
Deret Fibonancy : 0,1,1,2,3,5,8,13,.........

Secara notasi pemrograman dapat ditulis sebagai :
Fibo (1) = 0 & Fibo (2) = 1 ....................................... (1)
Fibo (N) = Fibo (N-1) + Fibo (N-2) .......................... (2)

Contoh :
Fibo(5) = Fibo(4) + Fibo(3)
Fibo(4) = Fibo(3) + Fibo(2)
Fibo(3) = Fibo(2) + Fibo(1)

Deret Fibonancy

A[1] = 1;
A[2] = 2;
For (i=3; i<=10; i++)
{
A[i] = A[i-1] + A[i-2];
}

Konsep Menara Hanoi

Jika n=1, maka langsung pindahkan saja piringan dr tiang A ke tiang C & selesai.
Pindahkan n-1 piringan yg paling atas dr tiang A ke tiang B.
Pindahkan piringan ke n (piringan terakhir) dr tiang A ketiang C
Pindahkan n-1 piringan dari tiang B ke tiang C.

Langkah pemindahan tsb diatas dpt diubah dengan notasi sbb:

Menara (n,asal,bantu,tujuan)

Utk jml piringan n>1 dpt dibagi menjadi 3 notasi penyelesaian
Menara (n-1, Asal,Tujuan, Bantu);
Menara (n, Asal, Bantu, Tujuan);

Langkah Pemindahan Piringan