Matematika Diskrit : Rekursi

Definisi Rekursi

Sebuah objek dikatakan rekursif (recursive) jika ia didefinisikan dalam terminologi dirinya sendiri.

Proses mendefinisikan objek dalam terminologi dirinya sendiri disebut rekursi (recursion).

Perhatikan gambar berikut ini.


Fungsi Rekursif

Fungsi rekursif didefinisikan oleh dua bagian:

Basis

Bagian yang berisi nilai fungsi yang terdefinisi secara eksplisit.

Bagian ini juga sekaligus menghentikan rekursif (dan memberikan sebuah nilai yang terdefinisi pada fungsi rekursif).

Rekurensi

Bagian ini mendefinisikan fungsi dalam terminologi dirinya sendiri.

Berisi kaidah untuk menemukan nilai fungsi pada suatu input dari nilai-nilai lainnya pada input yang lebih kecil.


Contoh 1:

Misalkan f didefinsikan secara rekusif sebagai berikut

\[ n!=\begin{cases} 3 \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space ,n=0 \space \space \space \space \space \space (basis) \\ 2f(n-1) + 4 \space \space , n> 0 \space \space \space \space \space \space (rekurensi) \\ \end{cases} \]

Tentukan nilai f(4)!

Penyelesaian:

f(4) = 2f(3) + 4
= 2(2f(2) + 4) + 4
= 2(2(2f(1) + 4) + 4) + 4
= 2(2(2(2f(0) + 4) + 4) + 4) + 4
= 2(2(2(2โ€ข3 + 4) + 4) + 4) + 4
= 2(2(2(10) + 4) + 4) + 4
= 2(2(24) + 4) + 4
= 2(52) + 4
= 108

Penyelesaian lain:

f(0) = 3
f(1) = 2f(0) + 4 = 2 โ€ข 3 + 4 = 10
f(2) = 2f(1) + 4 = 2 โ€ข 10 + 4 = 24
f(3) = 2f(2) + 4 = 2 โ€ข 24 + 4 = 52
f(4) = 2f(3) + 4 = 2 โ€ข 52 + 4 = 108
Jadi, f(3) = 108


Contoh 2:

Nyatakan n! dalam definisi rekursif

\[ n! = \underbrace{1\times 2 \times 3 \times … \times (n-1)}_n \times n = (n-1)! \times n \]

Penyelesaian:
Misalkan f(n) = n! maka

\[ n!=\begin{cases} 1 \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space ,n=0 \space \space \space \space \space \space \\ nโ€ข(n-1)! \space \space , n> 0 \space \space \space \space \space \space \\ \end{cases} \]

Penghitungan 5! secara rekursif:

5! = 5 โ€ข 4! = 5 โ€ข 4 โ€ข 3! = 5 โ€ข 4 โ€ข 3 โ€ข 2!

5! = 5 โ€ข 4 โ€ข 3 โ€ข 2 โ€ข 1! = 5 โ€ข 4 โ€ข 3 โ€ข 2 โ€ข 1 โ€ข 0!

5! = 5 โ€ข 4 โ€ข 3 โ€ข 2 โ€ข 1 โ€ข 1 = 120


Contoh 3:

Barisan Fibonacci 0, 1, 1, 2, 3, 5, 8, 11, 19, โ€ฆ.

Dapat dinyatakan secara rekursif sebagai berikut:

\[ f(n)=\begin{cases} 0 \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space , n = 0\\ 1 \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space , n = 1\\ f_{n-1} + f_{n-2} \space \space \space , n > 1 \\ \end{cases} \]

Contoh 4:

Fungsi (polinom) Chebysev dinyatakan sebagai berikut :

\[ T(n,x) =\begin{cases} 1 \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space , n = 0 \\ x \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space , n=1 \\ 2x โ€ข T(n-1,x)- T(n-2,x) \space \space \space \space , n > 1 \\ \end{cases} \]

Contoh 5:

Deret

\[ \sum_{k=0}^{n}a_{k} \]

didefinisikan secara rekursif sebagai berikut:

\[ \sum_{k=0}^{n}a_{k} = a_{0} + a_{1} + a_{2} + … + a_{n-1} + a_{n} \\ = (a_{0} + a_{1} + a_{2} + … + a_{n-1}) + a_{n} \\ = ( \sum_{k=0}^{n-1}a_{k} ) + a_{n} \]

Sehingga

\[ \sum_{k=0}^{n}a_{k} = \begin{cases} a_{0} & ,n=0 \\ \sum_{k=0}^{n-1}a_{k} ) + a_{n} & ,n>0 \\ \end{cases} \]

Barisan Rekursif

Perhatikan barisan bilangan berikut ini:

1, 2, 4, 8, 16, 64, โ€ฆ

Setiap elemen ke-n untuk n = 0, 1, 2, โ€ฆ merupakan hasil perpangkatan 2 dengan n atau an = 2n.

Secara rekursif, setiap elemen ke-n merupakan hasil kali elemen sebelumnya dengan 2 atau an = 2an โ€“ 1

  • Basis: a0 = 1
  • Rekurens: an = 2an โ€“ 1

Contoh 1:

Koloni bakteri dimulai dari lima buah bakteri. Setiap bakteri membelah diri menjadi dua bakteri baru setiap satu jam. Berapa jumlah bakteri baru sesudah 4 jam?

Penyelesaian:

Misalkan an = jumlah bakteri setelah n jam, yang dapat dinyatakan dalam relasi rekursif sebagai berikut:

\[ a_{n}=\begin{cases} 5 \space \space \space \space \space \space \space \space \space \space ,n=0 \\ 2a_{n-1} \space \space , n > 0 \\ \end{cases} \]

n = 1 โ†’ jumlah bakteri = a1 = 2 a0 = 2 โ€ข 5 = 10

n = 2 โ†’ jumlah bakteri = a2 = 2 a1 = 2 โ€ข 10 = 20

n = 3 โ†’ jumlah bakteri = a3 = 2 a2 = 2 โ€ข 20 = 40

n = 4 โ†’ jumlah bakteri = a4 = 2 a3 = 2 โ€ข 40 = 80

Jadi, setelah 4 jam terdapat 80 buah bakteri


Relasi Rekurensi

Barisan (sequence) a0, a1, a2, โ€ฆ, an dilambangkan dengan {an}

Elemen barisan ke-n, yaitu an, dapat ditentukan dari suatu persamaan.

Bila persamaan yang mengekspresikan an dinyatakan secara rekursif dalam satu atau lebih term elemen sebelumnya, yaitu a0, a1, a2, โ€ฆ, an-1, maka persamaan tersebut dinamakan relasi rekurensi.

Contoh:

an = 2anโ€“1 + 1
an = anโ€“1 + 2anโ€“2
an = 2anโ€“1 โ€“ an-2


Kondisi Awal

Kondisi awal (initial conditions) suatu barisan adalah satu atau lebih nilai yang diperlukan untuk memulai menghitung elemen-elemen selanjutnya.

Contoh:

an = 2anโ€“1 + 1; a0 = 1
an = anโ€“1 + 2anโ€“2 ; a0 = 1 dan a1 = 2

Karena relasi rekurensi menyatakan definisi barisan secara rekursif, maka kondisi awal merupakan langkah basis pada definisi rekursif tersebut.

Contoh: Barisan Fibonacci 0, 1, 1, 2, 3, 5, 8, 13, โ€ฆ dapat dinyatakan dengan relasi rekurensi
fn = fnโ€“1 + fnโ€“2; f0 = 0 dan f1 = 1

Kondisi awal secara unik menentukan elemen-elemen barisan. Kondisi awal yang berbeda akan menghasilkan elemen-elemen barisan yang berbeda pula.


Solusi dari Sebuah Relasi Rekurensi

Solusi dari sebuah relasi rekurensi adalah sebuah formula yang tidak melibatkan lagi term rekursif. Formula tersebut memenuhi relasi rekurens yang dimaksud.

Contoh 1:

Misalkan {an} adalah barisan yang memenuhi relasi rekurensi berikut:

an = 2anโ€“1 โ€“ anโ€“2; a0 = 1 dan a1 = 2

Periksa apakah an = 3n merupakan solusi relasi rekurensi tersebut.

Penyelesaian:

2anโ€“1 โ€“ anโ€“2 = 2[3(n โ€“ 1)] โ€“ 3(n โ€“ 2)
= 6n โ€“ 6 โ€“ 3n + 6
= 3n = an
Jadi, an = 3n merupakan solusi dari relasi rekurensi tersebut.


Contoh 2:

Apakah an = 2n merupakan solusi relasi rekurensi an = 2anโ€“1 โ€“ anโ€“2; a0 = 1 dan a1 = 2?

Penyelesaian:

2anโ€“1 โ€“ anโ€“2 = 2โ€ข2nโ€“1 โ€“ 2nโ€“2

= 2nโ€“1 + 1 โ€“ 2nโ€“2

= 2n โ€“ 2nโ€“2 โ‰  2n

Jadi, an = 2n bukan merupakan solusi relasi rekurensi tersebut.

Penyelesaian dengan cara lain:

Karena a0 = 1 dan a1 = 2, maka dapat dihitung

a2 = 2a1 โ€“ a0 = 2โ€ข2 โ€“ 1 = 3

Dari rumus an = 2n dapat dihitung

a0 = 20 = 1

a1 = 21 = 2

a2 = 22 = 4

Karena 3 โ‰  4, maka an = 2n bukan merupakan solusi dari relasi rekurensi tersebut.


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Matematika Diskrit – Rekursi, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up