31
Sebagai
contoh,
barisan
Fibonacci
didefinisikan
sebagai
berikut:
fib(0)
=
fib(1)
=
1,
fib(n)
=
fib(n-1)
+
fib(n-2).
Maka
pseudocode
dari
suatu
fungsi
yang
digunakan untuk
menghitung barisan Fibonacci akan berbentuk sebagai berikut:
Function fib(n)
If n = 0 or n = 1
Then return 1
Else return fib(n-1) + fib(n-2)
Perhatikan
bahwa
jika
kita
memanggil fib(5),
proses
rekursif
yang
berjalan
akan
memanggil fungsi fib() dengan angka yang sama berulang kali:
fib(5) = fib(4) + fib(3) = (fib(3) + fib(2)) + (fib(2) + fib(1))
=
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
=
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0))
+
fib(1))
Pada
khususnya,
fib(2)
akan
dihitung
dari
awal
sebanyak tiga
kali,
dan
fib(3)
sebanyak
dua kali. Untuk
nilai
n
yang
lebih besar,
maka akan
terdapat jauh
lebih banyak
nilai
fib() pada
subproblem-subproblem
yang
akan
dihitung
ulang,
sehingga
waktu
eksekusi
algoritma
ini
akan
meningkat secara eksponensial terhadap n.
Misalkan terdapat sebuah
array
x,
yang
menyimpan setiap
nilai
fib()
yang telah dihitung
kedalamnya. Maka dengan
mengimplementasikan penggunaan array tersebut ke dalam
fungsi di
atas
seperti
pada
pseudocode
di
bawah
ini
akan
didapatkan
algoritma
dengan
waktu
eksekusi
yang linear terhadap n.
 |