PERULANGAN REKURSIF DAN PERULANGAN ITERATIF

PERULANGAN REKURSIF DAN PERULANGAN ITERATIF

Rekursif adalah suatu proses yang bisa memanggil dirinya sendiri.
Perulangan Rekursif merupakan salah satu metode didalam pemrograman yang mana dalam sebuah fungsi terdapat instruksi yang memanggil fungsi itu sendiri, atau lebih sering disebut memanggil dirinya sendiri.
Perulangan iteratif merupakan perulangan yang melakukan proses perulangan terhadap sekelompok instruksi. perulangan dilakukan dalam batasan syarat tertentu. ketika syarat tersebut tidak terpenuhi lagi maka perulangan akan terhenti.

Persamaan:

• Iteratif dan rekursif merupakan metode atau teknik didalam perulangan (looping)
• Sama-sama memiliki bagian yang berfungsi sebagai batas dalam sebuah perulangan

Perbedaan:

• Iteratif dalam melakukan perulangan membutuhkan suatu instruksi program seperti for, repeat until dan while do, sedangkan rekursi tidak memakai instruksi program seperti itu. cukup dengan fungsi tersebut

Contoh penggunaan proses 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
3. lakukan prosedur 1 dan 2 untuk sisa potongannya

CONTOH FUNGSI REKURSIF
1. fungsi pangkat

• Menghitung 10 pangkat n dengan menggunakan konsep rekursif
• Secara notasi pemrograman dapat dituliskan sebagai berikut :

2. Faktorial

• 0! =1
• N! = N X (N-1)! untuk N>0
• Secara notasi pemrograman dapat dituliskan sebagai berikut :

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;

misalnya :
Hitung 5! dapat dihitung dengan cara rekursif sebagai berikut :
5! = 5*4 !
secara rekursif nilai dari 4! dapat dihitung kembali dengan cara : 4*3 !
sehingga 5! menjadi 5!= 5*4*3 !
secara rekursif nilai dari 3! dapat dihitung kembali dengan cara : 3*2 !
sehingga 5! menjadi 5!= 5*4*3*2 !
secara rekursif nilai dari 2! dapat dihitung kembali dengan cara : 2*1
sehingga 5! menjadi 5!= 5*4*3*2*1


3. Deret Fibonacci

• Deret fibonacci : 0, 1, 1, 2, 3, 5, 8, 13,...
• Secara notasi pemrograman dapat dituliskan sebagai berikut :

1. FIBO(1) = 0 dan FIBO (2) = 1 .....................................(1)
2. 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) -----> nilai awal

4. Konsep Menara Hanoi

• tujuan permainan ini adalah memindahkan n buah balok dari tonggak asal A melalui tonggak bantu B menuju tonggak C. dengan aturan balok yang lebih kecil tidak boleh berada di bawah balok yang lebih besar

bayangkan keadaan berikut :
ada 3 tiang (a, b, c) tempat balok dengan ukuran yang bervariasi dapat ditumpuk. pada mulanya semua balok ada di "A". Tugasnya adalah meindahkan semua balok ke "C" degan aturan sebagai berikut :

• Pada satu saat hanya boleh memindah 1 balok
• setiap perpindahan berupa pengambilan balok teratas dari satu tiang dan memasukkannya ketiang lain, diatas balok lain yang mungkin sudah ada pada tiang tersebut.
  
• tidak boleh meletakkan balok diatas balok lain yang lebih kecil
• pada setiap akhir pemindahan semua balok harus berada di tiang.

Dalam notasi algoritma dapat dituliskan sebagai berikut :

• jika n= 1, maka langsung pindahkan saja balok dari tiang A ke tiang C dan selesai
• pindahkan n-1 balok yang paling atas dari tiang A ke Tiang B
• pindahkan balok ke n (balok terakhir) dari tiang A ke tiang C
• pindahkan n-1 balok dari tiang B ke tiang C