Panduan Python untuk Deret Fibonacci

Deret Fibonacci adalah deret bilangan bulat yang cukup terkenal. Urutannya muncul secara alami dalam banyak soal dan memiliki definisi rekursif yang bagus. Mempelajari cara menghasilkannya merupakan langkah penting dalam perjalanan programmer pragmatis menuju penguasaan rekursi. Dalam tutorial ini, Anda akan fokus mempelajari apa itu deret Fibonacci dan cara menghasilkannya menggunakan Python.

Dalam tutorial ini, Anda akan mempelajari cara:

Hasilkan deret Fibonacci menggunakan algoritme rekursif

Optimalkan algoritma Fibonacci rekursif menggunakan memoisasi

Hasilkan deret Fibonacci menggunakan algoritme berulang

Untuk mendapatkan hasil maksimal dari tutorial ini, Anda harus mengetahui dasar-dasar notasi Big O, pemrograman berorientasi objek, metode khusus Python, pernyataan kondisional, fungsi, dan struktur data dasar seperti daftar, antrian, dan tumpukan. Pemahaman terhadap konsep-konsep ini akan sangat membantu Anda memahami konsep-konsep baru yang akan Anda jelajahi dalam tutorial ini.

Mari selami!

Leonardo Fibonacci adalah seorang matematikawan Italia yang mampu dengan cepat menghasilkan jawaban atas pertanyaan yang diajukan oleh Kaisar Frederick II dari Swabia: “Berapa pasang kelinci yang diperoleh dalam setahun, tidak termasuk kasus kematian, seandainya setiap pasangan melahirkan yang lain. berpasangan setiap bulan dan pasangan termuda sudah dapat bereproduksi pada bulan kedua kehidupannya?”

Jawabannya adalah urutan berikut:

Polanya dimulai setelah dua angka pertama, 0 dan 1, dimana setiap angka pada barisan tersebut selalu merupakan jumlah dari dua angka sebelumnya. Matematikawan India telah mengetahui deret ini sejak abad keenam, dan Fibonacci memanfaatkannya untuk menghitung pertumbuhan populasi kelinci.

F(n) digunakan untuk menunjukkan jumlah pasangan kelinci yang ada pada bulan n, sehingga urutannya dapat dinyatakan seperti ini:

Dalam terminologi matematika, Anda menyebutnya relasi perulangan, artinya setiap suku barisan (di luar 0 dan 1) merupakan fungsi dari suku sebelumnya.

Ada juga versi barisan yang dua angka pertamanya sama-sama 1, seperti:

Dalam versi alternatif ini, F(0) secara implisit masih 0, namun Anda memulai dari F(1) dan F(2) sebagai gantinya. Algoritmenya tetap sama karena Anda selalu menjumlahkan dua angka sebelumnya untuk mendapatkan angka berikutnya dalam barisan tersebut.

Untuk keperluan tutorial ini, Anda akan menggunakan versi urutan yang dimulai dengan 0.

Menghasilkan deret Fibonacci adalah masalah rekursif klasik. Rekursi adalah ketika suatu fungsi merujuk pada dirinya sendiri untuk memecah masalah yang coba dipecahkannya. Dalam setiap pemanggilan fungsi, masalahnya menjadi lebih kecil hingga mencapai kasus dasar, yang kemudian akan mengembalikan hasilnya ke setiap pemanggil perantara hingga mengembalikan hasil akhir ke pemanggil awal.

Jika Anda ingin menghitung bilangan Fibonacci F(5), Anda perlu menghitung pendahulunya, F(4) dan F( 3), pertama. Dan untuk menghitung F(4) dan F(3), Anda perlu menghitung pendahulunya. Pengelompokan F(5) menjadi submasalah yang lebih kecil akan terlihat seperti ini:

Setiap kali fungsi Fibonacci dipanggil, fungsi tersebut akan dipecah menjadi dua submasalah yang lebih kecil karena itulah cara Anda mendefinisikan relasi perulangan. Ketika mencapai kasus dasar F(0) atau F(1), ia akhirnya dapat mengembalikan hasil ke pemanggilnya.

Untuk menghitung angka kelima dalam deret Fibonacci, selesaikan soal yang lebih kecil namun identik hingga Anda mencapai kasus dasar, tempat Anda dapat mulai mengembalikan hasilnya:

Submasalah berwarna pada diagram ini mewakili solusi berulang untuk masalah yang sama. Jika Anda melangkah lebih jauh, Anda akan menemukan lebih banyak solusi berulang ini. Artinya, untuk menghasilkan deret Fibonacci secara rekursif, Anda harus menghitung banyak bilangan perantara berulang kali. Ini adalah salah satu masalah mendasar dalam pendekatan rekursif pada deret Fibonacci.

Algoritme yang paling umum dan minimal untuk menghasilkan deret Fibonacci mengharuskan Anda membuat kode fungsi rekursif yang memanggil dirinya sendiri sebanyak yang diperlukan hingga ia menghitung bilangan Fibonacci yang diinginkan:

Di dalam fibonacci_of(), Anda terlebih dahulu memeriksa kasus dasarnya. Anda kemudian mengembalikan jumlah nilai yang dihasilkan dari pemanggilan fungsi dengan dua nilai n sebelumnya. Pemahaman daftar di akhir contoh menghasilkan deret Fibonacci dengan lima belas angka pertama.

Fungsi ini dengan cepat masuk ke dalam masalah pengulangan yang Anda lihat di bagian atas. Perhitungannya menjadi semakin mahal seiring dengan semakin besarnya n. Waktu yang dibutuhkan bertambah secara eksponensial karena fungsi tersebut menghitung banyak submasalah identik berulang kali.

Catatan: Jangan mencoba fungsi ini di rumah dengan angka lebih dari 50. Tergantung pada perangkat keras Anda, Anda mungkin harus menunggu lama sebelum melihat hasilnya—jika Anda berhasil mencapai akhir.

Untuk menghitung F(5), fibonacci_of() harus memanggil dirinya sendiri lima belas kali. Untuk menghitung F(n), kedalaman maksimum pohon panggilan adalah n, dan karena setiap pemanggilan fungsi menghasilkan dua pemanggilan fungsi tambahan, maka kompleksitas waktu dari fungsi rekursif ini adalah O(2n).

Sebagian besar panggilan tersebut mubazir karena Anda sudah menghitung hasilnya. F(3) muncul dua kali, dan F(2) muncul tiga kali. F(1) dan F(0) adalah kasus dasar, jadi boleh saja memanggilnya berkali-kali. Anda mungkin ingin menghindari pengulangan yang sia-sia ini, yang merupakan topik pada bagian berikut.

Setidaknya ada dua teknik yang dapat Anda gunakan untuk membuat algoritme yang menghasilkan deret Fibonacci lebih efisien—dengan kata lain, menghemat waktu komputasi. Teknik-teknik ini memastikan bahwa Anda tidak terus-menerus menghitung nilai yang sama, yang membuat algoritme asli menjadi sangat tidak efisien. Itu disebut memoisasi dan iterasi.

Seperti yang Anda lihat pada kode di atas, fungsi Fibonacci memanggil dirinya sendiri beberapa kali dengan input yang sama. Alih-alih melakukan panggilan baru setiap saat, Anda dapat menyimpan hasil panggilan sebelumnya dalam sesuatu seperti cache memori. Anda dapat menggunakan daftar Python untuk menyimpan hasil perhitungan sebelumnya. Teknik ini disebut memoisasi.

Memoisasi mempercepat eksekusi fungsi rekursif yang mahal dengan menyimpan hasil perhitungan sebelumnya dalam cache. Dengan cara ini, ketika masukan yang sama muncul lagi, fungsi hanya perlu mencari hasil yang sesuai dan mengembalikannya tanpa harus menjalankan komputasi lagi. Anda dapat menyebut hasil ini sebagai cache atau memoized:

Dengan memoisasi, Anda hanya perlu menelusuri pohon panggilan dengan kedalaman n satu kali setelah kembali dari kasus dasar, saat Anda mengambil semua nilai yang dihitung sebelumnya yang disorot dengan warna kuning, F (2) dan F(3), dari cache tadi.

Jalur oranye menunjukkan bahwa tidak ada masukan ke fungsi Fibonacci yang dipanggil lebih dari satu kali. Hal ini secara signifikan mengurangi kompleksitas waktu algoritme dari O(2n) eksponensial menjadi O(n).

Bahkan untuk kasus dasar, Anda dapat mengganti pemanggilan F(0) dan F(1) hanya dengan mengambil nilai langsung dari cache pada indeks 0 dan 1, sehingga Anda akhirnya memanggil fungsi tersebut hanya enam kali, bukan lima belas!

Berikut kemungkinan terjemahan optimasi ini ke dalam kode Python:

Dalam contoh ini, Anda menggunakan kamus Python untuk menyimpan angka Fibonacci yang dihitung dalam cache. Awalnya, cache berisi nilai awal deret Fibonacci, 0 dan 1. Di dalam fungsi, pertama-tama Anda memeriksa apakah bilangan Fibonacci untuk nilai masukan n saat ini sudah di cache. Jika sudah, barulah Anda mengembalikan nomor yang ada.

Jika tidak ada bilangan Fibonacci untuk nilai n saat ini, maka Anda menghitungnya dengan memanggil fibonacci_of() secara rekursif dan memperbarui cache. Langkah terakhir adalah mengembalikan angka Fibonacci yang diminta.

Bagaimana jika Anda bahkan tidak perlu memanggil fungsi Fibonacci rekursif sama sekali? Anda sebenarnya dapat menggunakan algoritme berulang untuk menghitung angka pada posisi n dalam deret Fibonacci.

Anda mengetahui bahwa dua bilangan pertama dalam barisan tersebut adalah 0 dan 1 dan setiap bilangan berikutnya dalam barisan tersebut adalah jumlah dari dua bilangan pendahulunya. Jadi, Anda cukup membuat perulangan yang menjumlahkan dua angka sebelumnya, n - 1 dan n - 2, untuk mencari angka pada posisi n secara berurutan.

Angka ungu yang dicetak tebal pada diagram di bawah mewakili angka baru yang perlu dihitung dan ditambahkan ke cache di setiap langkah berulang:

Untuk menghitung angka Fibonacci pada posisi n, Anda menyimpan dua angka pertama dari deret tersebut, 0 dan 1, di cache. Lalu, hitung angka berikutnya secara berurutan hingga Anda dapat mengembalikan cache[n].

Sekarang setelah Anda mengetahui dasar-dasar cara menghasilkan deret Fibonacci, sekarang saatnya mempelajari lebih dalam dan mengeksplorasi lebih jauh berbagai cara untuk mengimplementasikan algoritme dasar dengan Python. Di bagian berikut, Anda akan mempelajari cara menerapkan berbagai algoritme untuk menghasilkan deret Fibonacci menggunakan rekursi, pemrograman berorientasi objek Python, dan juga iterasi.

Pendekatan pertama Anda untuk menghasilkan deret Fibonacci akan menggunakan kelas Python dan rekursi. Keuntungan menggunakan kelas dibandingkan fungsi rekursif memo yang Anda lihat sebelumnya adalah bahwa kelas menjaga status dan perilaku (enkapsulasi) tetap bersama dalam objek yang sama. Namun dalam contoh fungsi, cache adalah objek yang benar-benar terpisah, jadi Anda tidak memiliki kendali terhadapnya.

Di bawah ini adalah kode yang mengimplementasikan solusi berbasis kelas Anda:

Berikut rincian apa yang terjadi pada kode:

Baris 3 mendefinisikan kelas Fibonacci.

Baris 4 mendefinisikan penginisialisasi kelas, .__init__(). Ini adalah metode khusus yang dapat Anda gunakan untuk menginisialisasi instance kelas Anda. Metode khusus terkadang disebut sebagai metode dunder, kependekan dari metode garis bawah ganda.

Baris 5 membuat atribut instance .cache, yang berarti setiap kali Anda membuat objek Fibonacci, akan ada cache untuk objek tersebut. Atribut ini awalnya berisi angka pertama dalam deret Fibonacci.

Baris 7 mendefinisikan metode khusus lainnya, .__call__(). Metode ini mengubah instance Fibonacci menjadi objek yang dapat dipanggil.

Baris 9 dan 10 memvalidasi nilai n dengan menggunakan pernyataan kondisional. Jika n bukan bilangan bulat positif, maka metode akan memunculkan ValueError.

Baris 13 mendefinisikan pernyataan kondisional untuk memeriksa angka Fibonacci yang telah dihitung dan tersedia di .cache. Jika nomor pada indeks n sudah ada di .cache, maka baris 14 mengembalikannya. Jika tidak, baris 17 akan menghitung angkanya, dan baris 18 menambahkannya ke .cache sehingga Anda tidak perlu menghitungnya lagi.

Baris 20 mengembalikan angka Fibonacci yang diminta.

Untuk mencoba kode ini, silakan simpan ke dalam fibonacci_class.py. Kemudian jalankan kode ini di shell interaktif Anda:

Di sini, Anda membuat dan memanggil instance kelas Fibonacci dengan nama fibonacci_of. Panggilan pertama menggunakan 5 sebagai argumen dan mengembalikan 5, yang merupakan angka Fibonacci keenam karena Anda menggunakan indeks berbasis nol.

Implementasi algoritma deret Fibonacci ini cukup efisien. Setelah Anda memiliki instance kelas, atribut .cache menyimpan nomor yang sudah dihitung dari panggilan ke panggilan.

Anda dapat secara efektif memahami bagaimana setiap panggilan ke fungsi Fibonacci rekursif ditangani menggunakan representasi tumpukan panggilan. Cara setiap panggilan dimasukkan ke dalam tumpukan dan dikeluarkan mencerminkan dengan tepat bagaimana program berjalan. Ini dengan jelas menunjukkan bagaimana penghitungan angka besar akan memakan waktu lama jika Anda tidak mengoptimalkan algoritmanya.

Dalam tumpukan panggilan, setiap kali suatu fungsi mengembalikan hasil, bingkai tumpukan yang mewakili pemanggilan fungsi akan dikeluarkan dari tumpukan. Setiap kali Anda memanggil suatu fungsi, Anda menambahkan bingkai tumpukan baru ke bagian atas tumpukan. Secara umum, operasi ini memiliki kompleksitas ruang O(n) karena tidak ada lebih dari n frame tumpukan pada tumpukan panggilan pada saat yang bersamaan. satu kali.

Catatan: Ada editor kode ramah pemula bernama Thonny yang memungkinkan Anda memvisualisasikan tumpukan panggilan fungsi rekursif dalam cara grafis. Anda dapat melihat Thonny: Editor Python Ramah Pemula untuk mempelajari lebih lanjut.

Untuk memvisualisasikan algoritma Fibonacci rekursif yang dimo, Anda akan menggunakan serangkaian diagram yang mewakili tumpukan panggilan. Nomor langkah ditunjukkan dengan label biru di bawah setiap tumpukan panggilan.

Katakanlah Anda ingin menghitung F(5). Untuk melakukan ini, Anda memasukkan panggilan pertama ke fungsi tersebut ke tumpukan panggilan:

Untuk menghitung F(5), Anda harus menghitung F(4) seperti yang diuraikan oleh relasi perulangan Fibonacci, sehingga Anda menambahkan pemanggilan fungsi baru ke tumpukan:

Untuk menghitung F(4), Anda harus menghitung F(3), sehingga Anda menambahkan pemanggilan fungsi lain ke tumpukan:

Untuk menghitung F(3), Anda harus menghitung F(2), sehingga Anda menambahkan pemanggilan fungsi lain ke tumpukan panggilan:

Untuk menghitung F(2), Anda harus menghitung F(1), sehingga Anda menambahkannya ke tumpukan. Karena F(1) adalah kasus dasar, ia segera kembali dengan 1, dan Anda menghapus panggilan ini dari tumpukan:

Sekarang Anda mulai melepas hasilnya secara rekursif. F(1) mengembalikan hasilnya ke fungsi pemanggilnya, F(2). Untuk menghitung F(2), Anda juga perlu menghitung F(0):

Anda menambahkan F(0) ke tumpukan. Karena F(0) adalah kasus dasar, ia segera kembali, memberi Anda 0. Sekarang Anda dapat menghapusnya dari tumpukan panggilan:

Hasil pemanggilan F(0) dikembalikan ke F(2). Sekarang Anda memiliki apa yang Anda perlukan untuk menghitung F(2) dan menghapusnya dari tumpukan:

Hasil dari F(2) dikembalikan ke pemanggilnya, F(3). F(3) juga memerlukan hasil F(1) untuk menyelesaikan penghitungannya, jadi Anda menambahkannya kembali ke tumpukan:

F(1) adalah kasus dasar dan nilainya tersedia di cache, sehingga Anda dapat segera mengembalikan hasilnya dan menghapus F(1) dari tumpukan:

Anda dapat menyelesaikan perhitungan untuk F(3), yaitu 2:

Anda menghapus F(3) dari tumpukan setelah menyelesaikan penghitungannya dan mengembalikan hasilnya ke pemanggilnya, F(4). F(4) juga memerlukan hasil dari F(2) untuk menghitung nilainya:

Anda mendorong panggilan ke F(2) ke tumpukan. Di sinilah cache bagus berperan. Anda telah menghitungnya sebelumnya, jadi Anda cukup mengambil nilai dari cache, menghindari panggilan rekursif untuk menghitung hasil F(2) lagi. Cache mengembalikan 1, dan Anda menghapus F(2) dari tumpukan:

F(2) dikembalikan ke pemanggilnya, dan sekarang F(4) memiliki semua yang diperlukan untuk menghitung nilainya, yaitu 3:

Selanjutnya, Anda menghapus F(4) dari tumpukan dan mengembalikan hasilnya ke pemanggil terakhir dan asli, F(5):

F(5) sekarang memiliki hasil F(4) dan juga hasil dari F(3). Anda menekan panggilan F(3) ke dalam tumpukan, dan cache yang bagus kembali berfungsi. Anda sebelumnya menghitung F(3), jadi yang perlu Anda lakukan hanyalah mengambilnya dari cache. Tidak ada proses rekursif untuk menghitung F(3). Ia mengembalikan 2, dan Anda menghapus F(3) dari tumpukan:

Sekarang F(5) memiliki semua nilai yang diperlukan untuk menghitung nilainya sendiri. Anda mendapatkan 5 dengan menambahkan 3 dan 2, dan itulah langkah terakhir sebelum Anda mengeluarkan panggilan F(5) dari tumpukan. Tindakan ini mengakhiri rangkaian pemanggilan fungsi rekursif Anda:

Tumpukan panggilan kosong sekarang. Anda telah menyelesaikan langkah terakhir untuk menghitung F(5):

Mewakili panggilan fungsi rekursif menggunakan diagram tumpukan panggilan membantu Anda memahami semua pekerjaan yang terjadi di balik layar. Ini juga memungkinkan Anda melihat berapa banyak sumber daya yang dapat digunakan oleh fungsi rekursif.

Menggabungkan semua diagram ini memungkinkan Anda memvisualisasikan keseluruhan proses:

Anda dapat mengklik gambar di atas untuk memperbesar setiap langkah. Jika Anda tidak menyimpan angka Fibonacci yang dihitung sebelumnya dalam cache, beberapa tahapan tumpukan dalam diagram ini akan jauh lebih tinggi, yang berarti akan membutuhkan waktu lebih lama untuk mengembalikan hasilnya ke pemanggilnya masing-masing.

Contoh di bagian sebelumnya menerapkan solusi rekursif yang menggunakan memoisasi sebagai strategi optimasi. Di bagian ini, Anda akan membuat kode fungsi yang menggunakan iterasi. Kode di bawah ini mengimplementasikan versi berulang dari algoritma deret Fibonacci Anda:

Sekarang, daripada menggunakan rekursi di fibonacci_of(), Anda menggunakan iterasi. Implementasi algoritma deret Fibonacci ini berjalan dalam waktu linier O(n). Berikut rincian kodenya:

Baris 3 mendefinisikan fibonacci_of(), yang menggunakan bilangan bulat positif, n, sebagai argumen.

Baris 5 dan 6 melakukan validasi n seperti biasa.

Baris 9 dan 10 menangani kasus dasar di mana n adalah 0 atau 1.

Baris 12 mendefinisikan dua variabel lokal, sebelumnya dan fib_number, dan menginisialisasinya dengan dua angka pertama dalam deret Fibonacci.

Baris 13 memulai perulangan for yang melakukan iterasi dari 2 ke n + 1. Perulangan menggunakan garis bawah (_) untuk variabel perulangan karena merupakan variabel sekali pakai dan Anda tidak akan menggunakan nilai ini dalam kode.

Baris 15 menghitung bilangan Fibonacci berikutnya dalam deret tersebut dan mengingat bilangan sebelumnya.

Baris 17 mengembalikan angka Fibonacci yang diminta.

Untuk mencoba kode ini, kembali ke sesi interaktif Anda dan jalankan kode berikut:

Implementasi fibonacci_of() ini cukup minim. Ia menggunakan pembongkaran berulang untuk menghitung angka Fibonacci selama perulangan, yang cukup efisien dalam hal memori. Namun, setiap kali Anda memanggil fungsi dengan nilai n yang berbeda, ia harus menghitung ulang urutannya lagi. Untuk memperbaikinya, Anda dapat menggunakan penutupan dan membuat fungsi Anda mengingat nilai yang sudah dihitung di antara panggilan. Silahkan dan cobalah!

Deret Fibonacci dapat membantu Anda meningkatkan pemahaman Anda tentang rekursi. Dalam tutorial ini, Anda telah mempelajari apa itu Deret Fibonacci. Anda juga telah mempelajari beberapa algoritme umum untuk menghasilkan urutan dan cara menerjemahkannya ke dalam kode Python.

Deret Fibonacci dapat menjadi batu loncatan dan titik masuk yang sangat baik ke dalam dunia rekursi, yang merupakan keterampilan mendasar yang harus dimiliki sebagai seorang programmer.

Dalam tutorial ini, Anda mempelajari cara:

Hasilkan deret Fibonacci menggunakan algoritme rekursif

Optimalkan algoritme Fibonacci rekursif Anda menggunakan memoisasi

Hasilkan deret Fibonacci menggunakan algoritme berulang

Anda juga telah memvisualisasikan algoritme rekursif yang dimemo untuk mendapatkan pemahaman yang lebih baik tentang cara kerjanya di balik layar. Untuk melakukannya, Anda menggunakan diagram tumpukan panggilan.

Setelah Anda menguasai konsep-konsep dalam tutorial ini, keterampilan pemrograman Python Anda akan meningkat seiring dengan pemikiran algoritmik rekursif Anda.