Cara menggunakan fibonacci python recursion

A Fibonacci sequence is a sequence of integers which first two terms are 0 and 1 and all other terms of the sequence are obtained by adding their preceding two numbers.

For example: 0, 1, 1, 2, 3, 5, 8, 13 and so on...

See this example:

Output:

Pada part kedua ini, kita akan melanjutkan proses pemecahan masalah fibonacci pada part pertama yang lalu.

Sekedar mengingatkan, pada pertemuan yang lalu kita telah memecahkan kasus deret fibonacci dengan 2 buah solusi non-rekursif; solusi pertama adalah menggunakan list, dan solusi yang kedua adalah menggunakan variabel bantuan.

Pada kesempatan kali ini, kita akan mencoba untuk memecahkan deret bilangan fibonacci menggunakan fungsi rekursif.

Apa itu Fibonacci?

Buat kalian yang belum tahu, fibonacci adalah suatu deret bilangan yang mana tiap angkanya adalah hasil penjumlahan dari dua angka sebelumnya.

Dan dua anggota pertama dari deret fibonacci selalu 0 dan 1.

Contoh:

0 1 1 2 3 5 8 13 21 34

Persiapan

Salah satu tujuan dari pembahasan ini adalah untuk memperdalam pemahaman kita terhadap fungsi rekursif. Maka sebelum mulai, pastikan bahwa kalian telah mengetahui dasar-dasar python, terlebih 2 pembahasan berikut:

• Fungsi pada python
• dan Fungsi rekursif pada python

Karena jika tidak, kalian akan menemukan kesulitan dalam mengikuti tutorial ini.

1. Buat File

Kita langsung mulai saja proses ngoding-nya. Silakan buat file baru berekstensi

def fibonacci(n):
  return [n]

2. Buat Simulasi Rekursif

Seperti biasa, kita mulai proses ngoding kita step-by-step. Langkah demi langkah. Tidak langsung keseluruhan kode program.

Kenapa?

Karena jika seperti itu, kita tidak akan tahu bagaimana proses berpikir dalam memecahkan sebuah permasalahan pemrograman.

Pada langkah-langkah awal, tujuan kita adalah:

• membuat fungsi rekursif yang mengembalikan sebuah list

Maka kita simulasikan dulu, setiap iterasi pemanggilan fungsi harus mengembalikan setidaknya satu list dengan satu anggota.

Tulis kode program berikut:

def fibonacci(n):
  return [n]

Panggil dan

def fibonacci(n):
  return [n]

print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))

Output yang kita dapat:

[1]
[2]
[3]
[4]

Sedangkan output yang kita inginkan adalah:

[1, 2, 3, 4]

Kita bisa menjadi satu dengan operator

def fibonacci(n):
  return [n]

Sehingga kode program kita akan terlihat seperti ini:

def fibonacci (n):
  if n < 1:
    return [n]

  return fibonacci(n - 1) + [n]

print(fibonacci(5))

Output:

[0, 1, 2, 3, 4, 5]

Penjelasan

Secara singkat, fungsi rekursif di atas akan mengembalikan list sebelum n ditambah dengan list yang berisi

print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))

Kalau dibongkar, ia melakukan penjumlahan list sebanyak

print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))

[0] + [1] + [2] + [3] + [4] + [5]

# hasil [0, 1, 2, 3, 4, 5]

Kita menginputkan

print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))

2. Persiapan Variabel

Kita berhasil membuat fungsi rekursif yang mengembalikan sebuah list. Ini adalah pondasi alur kita.

Langkah berikutnya agar alur program menjadi lebih mudah untuk dipahami, mari kita buat beberapa variabel.

def fibonacci (n):
  if n < 1:
    return [n]

  listSebelumN = fibonacci(n - 1)
  angka1 = listSebelumN[-2] if len(listSebelumN) > 2 else 0
  angka2 = listSebelumN[-1] if len(listSebelumN) > 2 else 1

  print('listSebelumN', listSebelumN)
  print(f'angka1: {angka1}, angka2: {angka2}')

  return listSebelumN + [n]

Kalau kita perhatikan, kita telah mengubah proses

print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))

print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))

return fibonacci(n - 1) + [n]

Menjadi:

def fibonacci(n):
  return [n]

Hal ini membuat kita bisa “ngapa-ngapain” dulu dengan list sebelum n. Misal

print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))

Dan di dalam kasus di atas, yang kita lakukan adalah mengambil dua buah angka dari list sebelumnya lalu menyimpannya dalam variabel

print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))

print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))

Kalau kita perhatikan, kita juga melakukan sebuah :

def fibonacci(n):
  return [n]

Jika dijalankan, program di atas akan menghasilkan output:

def fibonacci(n):
  return [n]

3. Proses Inti Fibonacci

Sampai sini, sebenarnya kita telah melakukan progress lebih dari 80%. Kita telah mengetahui:

• list sebelum n
• dua angka sebelum n

Yang perlu kita lanjutkan untuk menggenapkan proses fibonacci hanya satu saja!

Yaitu:

• menentukan nilai n berdasarkan hasil penjumlahan 2 angka sebelumnya.

Sehingga, kita hanya perlu mengubah satu baris aja yaitu bagian

print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))

def fibonacci(n):
  return [n]

Menjadi:

def fibonacci(n):
  return [n]

Jalankan kembali aplikasi, maka kita akan mendapatkan output sebagai berikut:

def fibonacci(n):
  return [n]

Sampai sini kita telah berhasil memecahkan proses fibonacci dengan cara rekursif 😁

Nggak nyangka kan?

Finishing

Langkah berikutnya adalah finishing. Tidak perlu aneh-aneh, kita hanya perlu menghapus beberapa

def fibonacci(n):
  return [n]

[1]
[2]
[3]
[4]

Berikut ini hasil akhirnya:

def fibonacci(n):
  return [n]

Kesimpulan

Dari pertemuan kali ini kita bisa menyimpulkan beberapa poin:

• Untuk menyelesaikan sebuah kasus pemrograman, kita perlu memulai dari langkah yang paling sederhana dulu. Setelah itu, kita akan semakin mudah untuk memikirkan langkah-langkah selanjutnya.
• Kita bisa memanfaatkan variabel dan fungsi

  def fibonacci(n):
    return [n]
  

  8 untuk mempermudah proses penyelesaian masalah.

Kode Program Lengkap

Sebenarnya kode program lengkapnya sudah tertuang di sini. Akan tetapi, jika ingin yang lebih step-by-step, kalian bisa mengaksesnya pada link ini.

Pertemuan Selanjutnya

Insyaallah pada pertemuan selanjutnya dari seri Latihan Logika Python, kita akan mempelajari bagaimana cara mencetak dan memeriksa bilangan prima dengan python.

Stay tune!

Jika ada pertanyaan atau sesuatu yang ingin didiskusikan, atau bahkan request tutorial, jangan sungkan-sungkan untuk berkomentar, ya! 😁