Matematika Diskrit : Rekursi

📋 Daftar Isi

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 a_n = 2ⁿ.

Secara rekursif, setiap elemen ke-n merupakan hasil kali elemen sebelumnya dengan 2 atau a_n = 2a_{n –}₁

Basis: a₀ = 1
Rekurens: a_n = 2a_n _–₁

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 a_n = 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 = a₁ = 2 a₀ = 2 • 5 = 10

n = 2 → jumlah bakteri = a₂ = 2 a₁ = 2 • 10 = 20

n = 3 → jumlah bakteri = a₃ = 2 a₂ = 2 • 20 = 40

n = 4 → jumlah bakteri = a₄ = 2 a₃ = 2 • 40 = 80

Jadi, setelah 4 jam terdapat 80 buah bakteri

Relasi Rekurensi

Barisan (sequence) a₀, a₁, a₂, …, a_n dilambangkan dengan {a_n}

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

Bila persamaan yang mengekspresikan an dinyatakan secara rekursif dalam satu atau lebih term elemen sebelumnya, yaitu a₀, a₁, a₂, …, a_n-1, maka persamaan tersebut dinamakan relasi rekurensi.

Contoh:

a_n = 2a_n_–1+ 1
a_n = a_n_–1 + 2a_n_–2
a_n = 2a_n_–1 – a_n_-2

Kondisi Awal

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

Contoh:

a_n = 2a_n_–1+ 1; a₀ = 1
a_n = a_n_–1 + 2a_n_–2 ; a₀ = 1 dan a₁= 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
f_n = f_n_–1 + f_n_–2; f₀ = 0 dan f₁ = 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 {a_n} adalah barisan yang memenuhi relasi rekurensi berikut:

a_n = 2a_n_–1 – a_n_–2; a₀ = 1 dan a₁ = 2

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

Penyelesaian:

2a_n_–1 – a_n_–2= 2[3(n – 1)] – 3(n – 2)
= 6n – 6 – 3n + 6
= 3n = a_n
Jadi, a_n= 3n merupakan solusi dari relasi rekurensi tersebut.

Contoh 2:

Apakah a_n = 2ⁿ merupakan solusi relasi rekurensi a_n = 2a_n_–1 – a_n_–2; a₀ = 1 dan a₁ = 2?

Penyelesaian:

2a_n_–1 – a_n_–2 = 2•2^n–1 – 2^n–2

= 2^{n–1 + 1} – 2^n–2

= 2ⁿ – 2^n–2 ≠ 2ⁿ

Jadi, a_n = 2ⁿ bukan merupakan solusi relasi rekurensi tersebut.

Penyelesaian dengan cara lain:

Karena a₀ = 1 dan a₁ = 2, maka dapat dihitung

a₂ = 2a₁ – a₀ = 2•2 – 1 = 3

Dari rumus a_n = 2ⁿ dapat dihitung

a₀ = 2⁰ = 1

a₁ = 2¹ = 2

a₂ = 2² = 4

Karena 3 ≠ 4, maka a_n = 2ⁿ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.

💡 Definisi Rekursi

✨ Penyelesaian dengan Iterasi

🧮 Penyelesaian dengan Persamaan Karakteristik

💻 Relasi Rekursi dalam Ilmu Komputer

Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Definisi Rekursi