Algoritma Rekursif

Yosh Kali ini kami akan membahas tentang Materi Pembahasan 3 Algoritma Rekursif. Langsung saja simak yuk ^_^




1. Menara Hanoi

Menara Hanoi adalah istilah yang digunakan untuk menggambarkan suatu tumpukan balok yang tersusun seperti sebuah piramida.

Prinsip kerjanya :
a. Pindahkan sejumlah n-1 balok yang pertama, dari A ke C dengan pertolongan posisi B sebagai transit sementara.
b. Memindahkan balok A ke B.
c. Memindahkan n-1 balok dari C ke B dengan bantuan posisi A sebagai transit sementara.

Algoritmanya :
A ← A
B ← B
C ← C 
 pindahBalok(n, A, B, C) // n : banyaknya balok, A : menara asal, B : menara
                                       // tujuan, C : menara bantuan
if(n = 1) then // statement akan menghentikan rekursif
  A ← B
else
 pindahBalok(n-1, A, C, B) // menjadi tujuan sementara ( transit )
  A ← B
  pindahBalok(n-1, C, B, A) // dari C diteruskan ke B sebagai tujuan
                                           // posisi n akan mengurang terus sampai n = 1 dimana balok A dapat di set
                                              balok B
end

T(n) = 1+ 2T(n −1)
= 1+2(1+2T(n-2)) = 1+2+2²T(n-2)
= 1+2+2²(1+2T(n-3)) = 1+2+2²+2³T(n-3)
= ...
= (1+2+2²+.....+2^n-2)+2^n-1T(1)
= 1+2+2²+.....+2^n-1.1
= 2ⁿ−1
  

2. Menghitung Faktorial

Algoritmanya :

Mencari T(n) :

T( ) n = 1 + T ( n − 1 )
= 1 + 1 + T( ) n − 2 = 2 + T ( n − 2 )
= 2 + 1 + T( ) n − 3 = 3 + T ( n − 3 )
= …..
= n + T(0)
= n + 0
Jadi T(n) = n → O(n)


3. Persoalan Minimum dan Maksimum

Algoritmanya :

T(n) = 3n/2-2

Referensi : http://www.academia.edu/5177971/Beberapa_contoh_algoritma_rekursif