Algoritma Fibonacci: Keindahan Deret dan Implementasinya

Dalam dunia pemrograman dan matematika, terdapat beberapa konsep yang begitu elegan dan seringkali muncul dalam berbagai konteks. Salah satu yang paling terkenal adalah algoritma Fibonacci. Deret Fibonacci, sebuah urutan angka di mana setiap angka adalah jumlah dari dua angka sebelumnya, telah memikat para matematikawan, ilmuwan, dan insinyur selama berabad-abad karena kemunculannya yang misterius di alam serta aplikasinya yang luas.

Asal-usul Deret Fibonacci

Deret ini dinamai dari Leonardo dari Pisa, yang lebih dikenal sebagai Fibonacci. Pada abad ke-13, dalam bukunya yang berjudul Liber Abaci, ia memperkenalkan deret ini melalui sebuah masalah sederhana tentang pertumbuhan populasi kelinci. Masalah tersebut berbunyi:

Misalkan ada sepasang kelinci yang baru lahir. Kelinci betina akan matang setelah satu bulan, dan setiap pasangan kelinci yang matang akan melahirkan sepasang kelinci baru setiap bulan berikutnya. Berapa banyak pasangan kelinci yang akan ada setelah satu tahun, jika tidak ada kelinci yang mati?

Dengan asumsi awal bahwa pasangan kelinci pertama lahir di bulan pertama dan mulai berkembang biak di bulan kedua, jumlah pasangan kelinci pada setiap bulan berturut-turut akan mengikuti pola: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. Jika kita memulai dengan angka 0, urutannya menjadi 0, 1, 1, 2, 3, 5, dan seterusnya.

Definisi Formal

Secara matematis, deret Fibonacci didefinisikan sebagai berikut:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2), untuk n > 1

Di mana F(n) adalah suku ke-n dalam deret Fibonacci.

Implementasi Algoritma Fibonacci

Ada beberapa cara untuk mengimplementasikan algoritma Fibonacci dalam pemrograman. Dua metode yang paling umum adalah menggunakan pendekatan rekursif dan iteratif.

1. Pendekatan Rekursif

Pendekatan rekursif secara langsung menerjemahkan definisi matematis ke dalam kode. Sebuah fungsi memanggil dirinya sendiri untuk menghitung suku-suku sebelumnya.

function fibonacciRecursive(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
        

Meskipun elegan dan mudah dipahami, pendekatan rekursif ini sangat tidak efisien untuk nilai n yang besar. Hal ini karena banyak perhitungan yang diulang. Misalnya, untuk menghitung F(5), kita perlu menghitung F(4) dan F(3). Untuk menghitung F(4), kita kembali perlu menghitung F(3) dan F(2). Perhatikan bahwa F(3) dihitung dua kali.

2. Pendekatan Iteratif

Pendekatan iteratif menggunakan loop untuk membangun deret dari awal hingga suku yang diinginkan. Metode ini jauh lebih efisien karena setiap suku hanya dihitung sekali.

function fibonacciIterative(n) {
  if (n <= 1) {
    return n;
  }

  let a = 0;
  let b = 1;
  let temp;

  for (let i = 2; i <= n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}
        

Pendekatan iteratif ini lebih disukai dalam praktik karena performanya yang lebih baik, terutama ketika berhadapan dengan nilai n yang besar. Efisiensi waktu kompleksitasnya adalah O(n).

3. Pendekatan dengan Memoization (Dynamic Programming)

Untuk mengatasi inefisiensi rekursif namun tetap mempertahankan strukturnya, kita dapat menggunakan teknik memoization. Ini adalah bentuk pemrograman dinamis di mana hasil dari pemanggilan fungsi yang mahal disimpan (di-cache) sehingga dapat dikembalikan ketika input yang sama muncul lagi.

function fibonacciMemoized(n, memo = {}) {
  if (n in memo) {
    return memo[n];
  }
  if (n <= 1) {
    return n;
  }
  memo[n] = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo);
  return memo[n];
}
        

Dengan memoization, kompleksitas waktu menjadi O(n), sama seperti pendekatan iteratif, namun dengan ruang tambahan untuk menyimpan hasil-hasil yang sudah dihitung (kompleksitas ruang O(n)).

Kehadiran Fibonacci di Alam Semesta

Salah satu aspek yang paling menarik dari deret Fibonacci adalah keberadaannya yang meluas di alam. Pola Fibonacci dapat ditemukan dalam:

• Bunga dan Tumbuhan: Jumlah kelopak bunga sering kali merupakan angka Fibonacci (misalnya, bunga lili memiliki 3 kelopak, buttercup 5, delphinium 8, dll.). Penataan daun pada batang, pola pertumbuhan cabang, dan susunan biji pada bunga matahari juga sering mengikuti urutan Fibonacci. Spiral biji bunga matahari, misalnya, sering kali memiliki jumlah spiral berlawanan arah yang merupakan dua angka Fibonacci berurutan (misalnya, 21 dan 34, atau 34 dan 55).
• Kulit Kerang: Bentuk spiral pada banyak cangkang kerang, seperti nautilus, sangat mendekati spiral Fibonacci atau spiral emas.
• Susunan Bintang dan Galaksi: Beberapa studi menunjukkan bahwa pola spiral pada lengan galaksi dan susunan bintang juga dapat menyerupai kurva Fibonacci.
• Proporsi Tubuh Manusia: Rasio emas, yang sangat terkait erat dengan deret Fibonacci, dipercaya sering muncul dalam proporsi estetika tubuh manusia.