Fungsi Rekursif

Pengertian dan arti kata rekursi atau rekursif sendiri belum ada di dalam KBBI. Kata ini berasal dari bahasa Inggris yakni recursive. Fungsi rekursif secara sederhana adalah fungsi yang memanggil dirinya sendiri. Fungsi jenis ini tidak hanya muncul pada bidang komputer, namun juga pada bidang matematika.

Kita akan melihat contoh fungsi matematis yang merupakan rekursif dan mengubahnya menjadi algoritma rekursif yang dapat dibaca oleh komputer.

Contoh Fungsi Rekursif

Contoh fungsi rekursif dapat kita temui pada fungsi Bilangan Fibonacci. Bilangan ini namanya berasal dari nama seorang matematikawan bernama Leonardo da Pisa, yang mempopulerkan bilangan ini di dunia barat.

Bilangan Fibonacci adalah barisan bilangan yang dihasilkan dengan cara menambahkan dua bilangan sebelumnya pada barisan tersebut. Jika masih bingung, mari kita lihat pola barisan fibonacci tersebut:

0 1 1 2 3 5 8 13 21 34 ...

Dapat kamu lihat bahwa bilangan ketiga pada baris tersebut jumlahnya sama dengan bilangan pertama ditambah bilangan kedua yakni 0 + 1 = 1. Kemudian bilangan keempat adalah 1 + 1 = 2.

Sehingga, untuk menentukan nilai-nilai yang ada pada barisan fibonacci dapat dirumuskan sebagai berikut ini,

Untuk bilangan urutan pertama, bernilai 0

Untuk bilangan urutan kedua, bernilai 1

Untuk bilangan urutan ke N: bernilai bilangan urutan N-1, ditambah bilangan urutan N-2.

Atau, secara matematis barisan bilangan fibonacci dapat dibuat rumus matematikanya menjadi,

Seperti yang kamu dapat lihat, untuk mendapatkan bilangan Fibonacci yang ke N, perlu memanggil fungsi Fib untuk menemukan nilai bilangan pada posisi N-1 dan N-2.

Fungsi yang seperti inilah yang disebut sebagai fungsi rekursif.

Uji Pemahamanmu

Barisan bilangan berikut yang bukan barisan fibonacci adalah,

a. 1, 2, 3, 5, 8

b. 2, 2, 4, 6, 10

c. 2, 3, 5, 8, 13

d. 1, 3, 3, 6, 9

Algortima Rekursif pada Pemrograman

Di dalam pemrograman, kita juga dapat membuat sebuah fungsi rekurif seperti pada deretan bilangan Fibonacci di atas.

Berikut ini adalah contoh program rekursif yang menghasilkan bilangan Fibonacci. Contoh fungsi rekursif ini dapat kamu lihat dalam bahasa C++, Python, dan Javascript.

• Javascript
• Python
• C++

function fib(n) {
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return fib(n-1) + fib(n-2);
}

def fib(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  return fib(n-1) + fib(n-2)

int fib(int n) {
  if (n == 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  return fib(n-1) + fib(n-2);
}

Dengan memanggil fungsi fib(n) pada kode diatas, kamu dapat menemukan nilai bilangan pada baris ke N.

Tapi, fungsi ini sangatlah lambat! Coba kamu masukkan angka yang besar, fungsi ini akan sangat lama untuk memprosesnya. Bisakah kamu membuatnya menjadi lebih cepat? (Petunjuk: Dynamic Programming).

Info Menarik Terkait Rekursif

Google Search: Recursion

Coba kalian cari kata kunci recursion pada pencarian di Google. Kalian akan menemukan Google memberi saran untuk mencari kata recursion lagi! Inilah yang disebut rekursif yang tidak akan pernah berhenti. Kalau kamu klik link pada bagian “Did you mean” tersebut, kamu akan kembali ke halaman yang sama.

Membuat Gambar Pohon

Dengan fungsi rekurif, sebuah program dapat membuat gambar pohon yang cukup realistis. Gambar dibawah ini merupakan hasil dari fungsi rekursif. Setiap batang pohonnya merupakan versi kecil dari batang pohon sebelumnya.