Matematika Diskrit : Relasi Rekursif dalam Ilmu Komputer

Mengubah Relasi Rekurensi menjadi Rumus Eksplisit

Nilai suku barisan ke-n (a_n) dapat dihitung secara langsung.

Contoh:

a_k = a_k-1 + 2 dengan a₀ = 1

Rumus eksplisit yang bersesuaian dengan relasi tersebut:

a_k = 1 + 2k.

Untuk mencari suku barisan ke-n (a_n), yang harus dilakukan :

membaca harga n dan membuat statemen penugasan a_n = 1 + 2n

Menggunakan Struktur Perulangan (Looping)

Contoh:

untuk menghitung suku ke-n barisan Fibonacci yang memenuhi relasi :

F_n = F_n-1 + F_n-2 dengan F₀ = 1 dan F₁ = 1,

maka dibuat struktur program sebagai berikut:

Depan := 1
Tengah := 1
For i := 2 to n
    Akhir := Depan + Tengah
    Depan := Tengah
    Tengah := Akhir
{end For}
Write (Akhir)

Menggunakan Prosedur Fungsi yang dipanggil Secara Rekursif

Relasi rekursif a_n dibuat dalam suatu prosedur/fungsi dengan n sebagai salah satu parameternya. Fungsi/prosedur ini secara rekursif memanggil dirinya sendiri dengan nilai parameter yang menurun.

Jika barisan Fibonacci diselesaikan dengan cara ini, maka programnya adalah (dalam struktur pascal) sebagai berikut:

Function Fib (n : Integer) : Integer;
    Begin
    If ((n=0) or (n=1)) Then Fib := 1
    Else Fib := Fib (n-1) + Fib (n-2)
    End;

Program yang dihasilkan lebih pendek, bentuknya mirip dengan relasi mula-mula, hanya saja waktu prosesnya jauh lebih lama terutama untuk n yang cukup besar.

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