Pengulangan
Iterasi adalah pengulangan suatu proses. Seorang siswa yang bersekolah mengulangi proses pergi ke sekolah setiap hari hingga lulus. Kami pergi ke toko grosir setidaknya sekali atau dua kali sebulan untuk membeli produk. Kami mengulangi proses ini setiap bulan. Dalam matematika, deret Fibonacci mengikuti properti pengulangan tugas juga. Mari kita pertimbangkan deret Fibonacci di mana dua angka pertama adalah 0 dan 1, semua angka lainnya adalah jumlah dari dua angka sebelumnya.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Langkah Iterasi
Rumus Fibonacci dapat ditulis sebagai,
F (n) = F (n - 1) + F (n - 2)
fibonacci (0) = 0
fibonacci (1) = 1
Fibonacci (2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
fibonacci (3) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
fibonacci (4) = fibonacci (3) + fibonacci (2) = 2 + 1 = 3
fibonacci (5) = fibonacci (4) + fibonacci (3) = 3 + 2 = 5
fibonacci (6) = fibonacci (5) + fibonacci (4) = 5 + 3 = 8
Algoritma yang diberikan di bawah ini mengembalikan angka Fibonacci ke-n.
Pengulangan
Setiap kali kita mendapatkan angka Fibonacci baru (angka ke-n), angka ke-n sebenarnya adalah angka (n - 1) ketika kita menemukan Fibonacci (n + 1) sebagai Fibonacci ke-n berikutnya. Seperti yang kita lihat langkah-langkah iterasi yang disebutkan di atas: jika n = 2 maka
Fibonacci (2) = Fibonacci (2-1) + Fibonacci (2-2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
Sekarang, kami ingin menghasilkan fibonacci (3), yaitu n = 3.
Fibonacci (3) = Fibonacci (3-1) + Fibonacci (3-2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Artinya, setiap kali n meningkatkan nilai arus (n - 1) th dan (n - 2) fibonacci juga meningkat. Tetapi melelahkan untuk melacak (n - 1) th dan (n - 2) fibonacci untuk setiap n. Bagaimana jika menulis metode yang memanggil dirinya sendiri untuk mengulangi tugas iterasi dengan sendirinya?
Metode yang memanggil dirinya sendiri disebut sebagai metode rekursif. Metode rekursif harus memiliki kasus dasar di mana program berhenti memanggil dirinya sendiri. Kasus dasar kami untuk deret Fibonacci adalah fibonacci (0) = 0 dan fibonacci (1) = 1. Jika tidak, metode Fibonacci menyebut dirinya dua kali - fibonacci (n - 1) dan fibonacci (n - 2). Kemudian menambahkannya untuk mendapatkan fibonacci (n). Metode rekursif untuk menemukan Fibonacci ke-n dapat ditulis sebagai -
Jika kita perhatikan dengan cermat, rekursi mengikuti properti tumpukan. Ini memecahkan submasalah yang lebih kecil untuk mendapatkan solusi dari suatu masalah. Untuk n> 1, ini mengeksekusi baris terakhir. Jadi, jika n = 6, Fungsi tersebut memanggil dan menambahkan fibonacci (6 - 1) dan fibonacci (6 - 2). fibonacci (6 - 1) atau fibonacci (5) memanggil dan menambahkan fibonacci (5 - 1) dan fibonacci (5 - 2). Rekursi ini berlanjut hingga 6 mencapai nilai kasus dasarnya yaitu fibonacci (0) = 0 atau fibonacci (1) = 1. Setelah menyentuh kasus dasar, ia menambahkan dua nilai dasar dan naik hingga mendapatkan nilai fibonacci ( 6). Di bawah ini adalah representasi pohon rekursi.
Pohon rekursi
Seperti yang bisa kita lihat, betapa kuatnya rekursi. Hanya satu baris kode yang membuat pohon di atas (baris terakhir kode di atas termasuk kasus dasar). Rekursi mempertahankan tumpukan dan masuk lebih dalam hingga mencapai kasus dasar. Pemrograman Dinamis (DP): Rekursi mudah dipahami dan dikodekan tetapi mungkin mahal dalam hal waktu dan memori. Lihatlah pohon rekursi di bawah ini. Subpohon kiri dimulai dengan fib (4) dan subtree kanan dimulai dengan fib (4) adalah sama persis. Mereka menghasilkan hasil yang sama yaitu 3 tetapi melakukan tugas yang sama dua kali. Jika n adalah angka besar (contoh: 500000) maka rekursi dapat membuat program menjadi sangat lambat karena akan memanggil sub tugas yang sama beberapa kali.
rekursi Dilingkari pohon
Untuk menghindari masalah ini, pemrograman dinamis dapat digunakan. Dalam pemrograman dinamis kita dapat menggunakan subtugas yang telah diselesaikan sebelumnya untuk menyelesaikan tugas masa depan dengan tipe yang sama. Ini adalah cara untuk mengurangi tugas untuk memecahkan masalah asli. Mari kita memiliki array fib [] tempat kita menyimpan solusi subtugas yang diselesaikan sebelumnya. Kita sudah tahu bahwa fib [0] = 0 dan fib [1] = 1. Mari kita simpan kedua nilai ini. Sekarang, berapa nilai dari fib [2]? Karena fib [0] = 0 dan fib [1] = 1 telah disimpan, kita hanya perlu mengatakan fib [2] = fib [1] + fib [0] dan itu saja. Kita bisa menghasilkan fib [3], fib [4], fib [5], ……, fib [n] dengan cara yang sama. Subtugas yang sebelumnya diselesaikan dipanggil untuk mendapatkan subtugas berikutnya hingga tugas asli belum diselesaikan, sehingga mengurangi penghitungan yang berlebihan.
