Rekursif : Faktorial, Fibonacci, Deret.

Rekursif

Salah satu konsep paling dasar dalam ilmu komputer dan pemrograman adalah pengunaan fungsi sebagai abstraksi untuk kode-kode yang digunakan berulang kali. Kedekatan ilmu komputer dengan matematika juga menyebabkan konsep-konsep fungsi pada matematika seringkali dijumpai. Salah satu konsep fungsi pada matematika yang ditemui pada ilmu komputer adalah fungsi rekursif: sebuah fungsi yang memanggil dirinya sendiri.

Kode berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari dua bilangan:

def kali(a, b):
    return a if b == 1 else a + kali(a, b - 1)

Bagaimana cara kerja fungsi rekursif ini? Sederhananya, selama nilai b bukan 1, fungsi akan terus memanggil perintah a + kali(a, b - 1), yang tiap tahapnya memanggil dirinya sendiri sambil mengurangi nilai b. Mari kita coba panggil fungsi kali dan uraikan langkah pemanggilannya:

kali(2, 4)
  -> 2 + kali(2, 3)
  -> 2 + (2 + kali(2, 2))
  -> 2 + (2 + (2 + kali(2, 1)))
  -> 2 + (2 + (2 + 2))
  -> 2 + (2 + 4)
  -> 2 + 6
  -> 8

Perhatikan bahwa sebelum melakukan penambahan program melakukan pemanggilan fungsi rekursif terlebih dahulu sampai fungsi rekursif mengembalikan nilai pasti (2$2$). Setelah menghilangkan semua pemanggilan fungsi, penambahan baru dilakukan, mulai dari nilai kembalian dari fungsi yang paling terakhir. Mari kita lihat contoh fungsi rekursif lainnya, yang digunakan untuk melakukan perhitungan faktorial:

def faktorial(n):
    return n if n == 1 else n * faktorial(n - 1)

Fungsi faktorial memiliki cara kerja yang sama dengan fungsi kali. Mari kita panggil dan lihat langkah pemanggilannya:

faktorial(5)
  -> 5 * faktorial(4)
  -> 5 * (4 * faktorial(3))
  -> 5 * (4 * (3 * faktorial(2)))
  -> 5 * (4 * (3 * (2 * faktorial(1))))
  -> 5 * (4 * (3 * (2 * 1)))
  -> 5 * (4 * (3 * 2))
  -> 5 * (4 * 6)
  -> 5 * 24
  -> 120

Dengan melihat kemiripan cara kerja serta kode dari fungsi faktorial dan kali, kita dapat melihat bagaimana fungsi rekursif memiliki dua ciri khas:

1. Fungsi rekursif selalu memiliki kondisi yang menyatakan kapan fungsi tersebut berhenti. Kondisi ini harus dapat dibuktikan akan tercapai, karena jika tidak tercapai maka kita tidak dapat membuktikan bahwa fungsi akan berhenti, yang berarti algoritma kita tidak benar.
2. Fungsi rekursif selalu memanggil dirinya sendiri sambil mengurangi atau memecahkan data masukan setiap panggilannya. Hal ini penting diingat, karena tujuan utama dari rekursif ialah memecahkan masalah dengan mengurangi masalah tersebut menjadi masalah-masalah kecil.

Bilangan Fibonacci

Dalam matematika, bilangan Fibonacci adalah barisan yang didefinisikan secara rekursif sebagai berikut:

Penjelasan: barisan ini berawal dari 0 dan 1, kemudian angka berikutnya didapat dengan cara menambahkan kedua bilangan yang berurutan sebelumnya. Dengan aturan ini, maka barisan bilangan Fibonaccci yang pertama adalah:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946...

Barisan bilangan Fibonacci dapat dinyatakan sebagai berikut:

F_n = (x₁ⁿ – x₂ⁿ)/ sqrt(5)

dengan

• F_n adalah bilangan Fibonacci ke-n
• x₁ dan x₂ adalah penyelesaian persamaan x² – x – 1 = 0.

Perbandingan antara F_n+1 dengan F_n hampir selalu sama untuk sebarang nilai n dan mulai nilai n tertentu, perbandingan ini nilainya tetap. Perbandingan itu disebut rasio emas yang nilainya mendekati 1,618.

Deret 

Deret adalah jumlah dari elemen-elemen  dalam suatu urutan. Urutan dan deret finit (atau terhingga) mempunyai elemen pertama dan terakhir yang terdefinisi, sedangkan Urutan dan deret infinit (atau tak terhingga) berlangsung terus menerus tak terbatas.

Dalam matematika, jika ada suatu urutan bilangan infinite { a_n }, maka suatu deret secara informal adalah hasil dari penambahan semua elemen-elemen itu bersama-sama: a₁ + a₂ + a₃ + · · ·. Ini dapat ditulis lebih singkat menggunakan simbol summation ∑. Contohnya adalah deret terkenal dari Paradoks Zeno dan representasi matematikanya:

${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\cdots .}$

Elemen-elemen dalam suatu deret sering diproduksi menurut kaidah tertentu, misalnya dengan suatu rumus, atau melalui suatu algoritme. Mengingat tidak terbatasnya jumlah elemen, hasilnya sering disebut deret tak terhingga (infinite series). Berbeda dengan finite summations, deret tak terhingga membutuhkan bantuan dari analisis matematika, dan secara khusus limit, untuk dapat dipahami dan dimanipulasi secara penuh. Selain jumlahnya yang banyak dalam matematika, deret tak terhingga juga sering digunakan dalam bidang-bidang kuantitatif lain seperti fisika, sains komputer, dan finansial.

Contoh Program dalam Java :

Hasil Program dalam Java :