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:
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 .py menggunakan IDE / Teks Editor favorit kalian. Bebas saja, kalau saya pribadi sih menggunakan vscode karena lebih universal.
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 print secara berurutan:
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 menggabungkan dua buah list menjadi satu dengan operator +.
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 n itu sendiri.
Kalau dibongkar, ia melakukan penjumlahan list sebanyak n + 1:
[0] + [1] + [2] + [3] + [4] + [5]
# hasil [0, 1, 2, 3, 4, 5]
Kita menginputkan n dengan nilai 5, dan yang kita dapatkan adalah 6 item (karena perulangannya kita buat dari 0).
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 return dari fungsi fibonacci dari yang awalnya gini:
return fibonacci(n - 1) + [n]
Menjadi:
listSebelumN = fibonacci(n - 1)
return listSebelumN + [n]
Hal ini membuat kita bisa “ngapa-ngapain” dulu dengan list sebelum n. Misal n sekarang sama dengan 5, berarti kita bisa melakukan hal-hal tertentu dengan list 1-4 terlebih dahulu.
Dan di dalam kasus di atas, yang kita lakukan adalah mengambil dua buah angka dari list sebelumnya lalu menyimpannya dalam variabel angka1 dan angka2.
Kalau kita perhatikan, kita juga melakukan sebuah percabangan satu baris:
angka1 = listSebelumN[-2] if len(listSebelumN) > 2 else 0
angka2 = listSebelumN[-1] if len(listSebelumN) > 2 else 1
Jika dijalankan, program di atas akan menghasilkan output:
listSebelumN [0]
angka1: 0, angka2: 1
listSebelumN [0, 1]
angka1: 0, angka2: 1
listSebelumN [0, 1, 2]
angka1: 1, angka2: 2
listSebelumN [0, 1, 2, 3]
angka1: 2, angka2: 3
listSebelumN [0, 1, 2, 3, 4]
angka1: 3, angka2: 4
[0, 1, 2, 3, 4, 5]
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 return yang ini:
return listSebelumN + [n]
Menjadi:
return listSebelumN + [angka1 + angka2]
Jalankan kembali aplikasi, maka kita akan mendapatkan output sebagai berikut:
listSebelumN [0]
angka1: 0, angka2: 1
listSebelumN [0, 1]
angka1: 0, angka2: 1
listSebelumN [0, 1, 1]
angka1: 1, angka2: 1
listSebelumN [0, 1, 1, 2]
angka1: 1, angka2: 2
listSebelumN [0, 1, 1, 2, 3]
angka1: 2, angka2: 3
[0, 1, 1, 2, 3, 5]
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 print dan membuat perintah input agar panjang deret fibonacci bisa ditentukan oleh user.
Berikut ini hasil akhirnya:
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
return listSebelumN + [angka1 + angka2]
panjang = int(input('Masukkan panjang deret:'))
# kita kurangin satu agar tidak kelebihan :D
print(fibonacci(panjang - 1))
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
printuntuk 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! 😁
