Struktur Data Tentang Rekursif Dan Iteratif
A. Rekursif
Rekursif berarti bahwa suatu proses bisa memanggil dirinya sendiri. Menurut definisi dalam Microsoft Bookshelf, Rekursif adalah kemampuan suatu rutin untuk memanggil dirinya sendiri. Dalam Rekursif sebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil lewat pemanggil prosedur dan fungsi. Rekursif merupakan teknik pemrograman yang penting dan beberapa bahasa pemrograman mendukung keberadaan proses rekursif ini. class="fullpost"> Dalam prosedur dan fungsi, pemanggilan ke dirinya sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir.
Contoh paling sederhana dari proses rekursif ini adalah proses menghitung nilai factorial dari suatu bilangan bulat positif dan mencari deret Fibbonacci dari suatu bilangan bulat.
- Nilai factorial secara rekursif dapat ditulis sebagai berikut :
0 ! = 1
N ! = N x (N-1) !
yang secara pemrograman dapat ditulis sebagai
Faktorial(0) = 1 (1)
Faktorial(N) = N*Faktorial(N-1) (2)
Persamaan (2) di atas adalah contoh hubungan rekurens (recurrence relation), yang berarti bahwa nilai suatu fungsi dengan argumen tertentu bisa dihitung dari fungsi yang sama dengan argumen yang lebih kecil. Persamaan (1) tidak bersifat rekursif, disebut nilai awal atau basis. Setiap fungsi rekursif paling sedikit mempunyai satu nilai awal, jika tidak fungsi tersebut tidak bisa dihitung secara eksplisit.
2. Bilangan Fibbonacci didefinisikan sebagai berikut
BARISAN BILANGAN FIBBONACI → 1, 1, 2, 3, 5, 8, 13, 21, . . .
Teknik Rekursif pada algoritma untuk menentukan suku ke-n dari barisan bilangan Fibbonaci, adalah sebagai berikut :
Procedure F(n : integer) : integer
If n ≤ 2 then F(n) = 1
else F(n) = F(n-1) + F(n-2)
Endif
End
Contoh Lain Rekursif :
Teknik Rekursif pada algoritma untuk menghitung faktorial dari bilangan bulat positif n, adalah sebagai berikut :
Function FAK (n : integer) : integer
If n := 0 then FAK := 1
Else FAK := n * FAK(n-1)
Permainan menara hanoi
Contoh paling umum dari penggunaan rekursif adalah pada permainan menara Hanoi. Berdasarkan legenda, pertama kali dimainkan secara manual oleh seorang pendeta Budha di Hanoi, sehingga permainan ini disebut Menara Hanoi. Dalam permainan ini, akan dipindahkan sejumlah piringan yang tidak sama besarnya dari satu tonggak ke tonggak lainnya, dengan diperbolehkan menggunakan (melewati) sebuah tonggak bantuan. Aturan permainannya adalah semua piringan pada tonggak A akan dipindahkan ke tonggak C (dapat dengan melewati tonggak bantuan B), dengan ketentuan bahwa pemindahan piringan dilakukan satu per satu dan piringan yang lebih besar tidak boleh diletakan di atas piringan yang lebih kecil. Untuk jelasnya lihat gambar berikut :
B. ITERATIF
Iteratif merupakan suatu teknik pembuatan algoritma dengan pemanggilan procedure beberapa kali atau hingga suatu kondisi tertentu terpenuhi
Contoh :
Teknik Iteratif pada algoritma untuk menghitung faktorial dari bilangan bulat positif n, adalah sebagai berikut :
Function FAK (n : integer) : integer
FAK=1
For i = 1 TO n
FAK = FAK * i
NEXT i
END FAK
Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka : FAK = 1, kemudian
| i | FAK |
| 1 | 1 * 1 = 1 |
| 2 | 1 * 2 = 2 |
| 3 | 2 * 3 = 6 |
| 4 | 6 * 4 = 24 |
| 5 | 24 * 5 = 120 |
Contoh :
BARISAN BILANGAN FIBBONACI → 1, 1, 2, 3, 5, 8, 13, 21, . . .
Set x, y, n, i, f : integer
2. x ← 1 ; y ← 1
3. If n 〉 2 then
begin
4. for i ← 3 to n do
begin
5. F ← x + y
6. x ← y
7. y ← F
end
else
8. F ← x
9. Write (F)
End
Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka :
x=1, y=1, kemudian
| i | F | x | y |
| 3 | 1 + 1 = 2 | 1 | 2 |
| 4 | 1 + 2 = 3 | 2 | 3 |
| 5 | 2 + 3 = 5 | 3 | 5 |
C. Perbedaan Rekursif Dan Iteratif
|
INTERATIF |
REKURSIF |
| Tidak ada variabel lokal baru | Ada variabel lokal baru |
| Program tidak sederhana | Program menjadi lebih sederhana |
Mau Lebih Lengkap Lagi Download di Bawah ini :
Download
