REKURSIF - MATEMATIKA DISKRIT

• Fungsi f dikatakan fungsi rekursif jika definisi fungsinya mengacu pada dirinya sendiri
• nama lain dari fungsi rekursif adalah relasi rekursif (recurrence relation), fungsi adalah bentuk khusus dari relasi.

Fungsi Rekursif

Fungsi rekursif didefinisikan oleh dua bagian :

a. 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).

b. Rekurens

- 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 sbb

Tentukan nilai f(4) dari fungsi tersebut

Cara lain menghitungnya:

                                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(4) = 108. 

Contoh 2:

                                               

Nyatakan n! dalam definisi rekursif

• Algoritma menghitung faktorial:

function Faktorial (input  n :integer)®integer

{ mengembalikan nilai n!;

  basis   : jika n = 0, maka 0! = 1

  rekurens: jika n > 0, maka n! = n ´ (n-1)!

}

DEKLARASI

- ALGORITMA:

    if n = 0 then

       return 1                { basis }

    else

       return  n * Faktorial(n – 1)  { rekurens }

    end

Contoh 3: Barisan Fibonacci  0, 1, 1, 2, 3, 5, 8, 11, 19, …. Dapat dinyatakan secara rekursif sebagai berikut:

Contoh 4: Fungsi (polinom) Chebysev dinyatakan sebagai

Contoh Soal : 

1.Definisikan an secara rekursif , yang dalam hal ini a adalah bilangan riil tidak-nol dan n adalah bilangan bulat tidak-negatif.

2.Nyatakan a ´ b secara rekursif, yang dalam hal ini a dan b adalah bilangan bulat positif.