Belajar Matematika Diskrit Live #15

Relasi Rekurens

Relasi rekurens adalah suatu persamaan matematika yang mendefinisikan suatu urutan (sequence) berdasarkan satu atau lebih nilai dalam urutan tadi, dengan kata lain ini bisa kita katakan seperti layaknya rekursif

Nilai ke N dari suatu deret nanti akan didefinisikan secara rekursif menggunkan nilai sebelumnya.

Rumus relasi rekurens: \(T(n)=f(T(n-1),T(n-2),\dots ,T(0))\)
Dengan kondisi awal atau base case ketika T sudah mencapai dengan 0 atau T sudah mencapai nilainya 1

Contoh: hitung jumlah cara untuk menaiki tangga dengan dari si n anak tangga,
peraturan: kita hanya boleh naik 1 atau 2 tangga sekaligus.
jika n = 3, maka cara yang memungkinkan untuk naik tangganya,
1. 1 -> 1 -> 1
2. 1 -> 2
3. 2 -> 1
berarti ada total 3 cara naik tangga, jika n = 3.
dengan model matematika, misal F(n) = jumlah cara menaiki n anak tangganya,
dari anak tangga ke (n - 1), lalu naik 1 langkah atau anak tangga ke (n - 2), lalu kita naik 2 langkah
F(n) = F(n - 1) + F(n - 2)
F(0) = 1 (ada 1 cara yakni tidak ngapa-ngapain atau tidak naik tangga, dengan target tercapai tetap berada tangga 0 )
F(1) = 1 (ada 1 cara yakni dengan melangkah naik 1 tangga, dengan target tercapai berada di tangga 1)

Penerapan dengan python

def naik_tangga(n: int) -> int:
    if n == 0 or n == 1:
        return 1
    return naik_tangga(n - 1) + naik_tangga(n - 2)

if __name__ == "__main__":
    anak_tangga: int = 3
    print(naik_tangga(anak_tangga))