Memahami Formula Recursion dan Recursive

Pengulangan

Pengulangan adalah pengulangan proses. Seorang pelajar yang pergi ke sekolah mengulangi proses pergi ke sekolah setiap hari sehingga tamat pengajian. Kami pergi ke kedai runcit sekurang-kurangnya sekali atau dua kali sebulan untuk membeli produk. Kami mengulangi proses ini setiap bulan. Dalam matematik, urutan Fibonacci mengikuti sifat pengulangan tugas juga. Mari kita pertimbangkan urutan Fibonacci di mana dua nombor pertama adalah 0 dan 1, semua nombor lain adalah jumlah dari dua nombor sebelumnya.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

Langkah-langkah Pengulangan

Rumus Fibonacci boleh 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 mengembalikan nombor Fibonacci nth.

Pengulangan

Setiap kali kita mendapat nombor Fibonacci baru (nombor nth) bahawa nombor n sebenarnya (n - 1) nombor th ketika kita menjumpai (n + 1) Fibonacci sebagai Fibonacci ke-seterusnya kita. Seperti yang kita lihat langkah lelaran yang disebutkan di atas: jika n = 2 maka
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1

Sekarang, kita mahu menghasilkan fibonacci (3), iaitu n = 3.

Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Ini bermaksud, setiap kali n meningkat nilai arus (n - 1) ke-3 dan (n - 2) fibonacci juga meningkat. Tetapi melelahkan untuk mengikuti jejak (n - 1) dan (n - 2) fibonacci untuk setiap n. Bagaimana dengan menulis kaedah yang memanggil dirinya untuk mengulangi tugas lelaran dengan sendirinya?

Kaedah yang memanggil dirinya dinamakan sebagai kaedah rekursif. Kaedah rekursif mesti mempunyai kes asas di mana program berhenti memanggil dirinya sendiri. Sarung asas kami untuk siri Fibonacci adalah fibonacci (0) = 0 dan fibonacci (1) = 1. Jika tidak, kaedah Fibonacci menyebut dirinya dua kali - fibonacci (n - 1) dan fibonacci (n - 2). Kemudian ia menambahkan mereka untuk mendapatkan fibonacci (n). Kaedah rekursif untuk mencari Fibonacci boleh ditulis sebagai -

Sekiranya kita melihat dengan teliti, rekursi mengikuti sifat timbunan. Ia menyelesaikan masalah yang lebih kecil untuk mendapatkan penyelesaian masalah. Untuk n> 1, ia melaksanakan baris terakhir. Jadi, jika n = 6, Fungsi 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 berterusan sehingga 6 mencapai nilai kes asasnya iaitu fibonacci (0) = 0 atau fibonacci (1) = 1. Setelah mencapai kes asas, ia menambah dua nilai asas dan naik sehingga ia mendapat nilai fibonacci ( 6). Di bawah ini adalah gambaran pengulangan pokok.

Pokok rekursi

Seperti yang kita lihat, betapa kuatnya pengulangan. Hanya satu baris kod yang membuat pokok di atas (baris terakhir kod di atas termasuk kes asas). Recursion mengekalkan timbunan dan ia akan menjadi lebih dalam sehingga mencapai casing asas. Pengaturcaraan Dinamik (DP): Rekursi mudah difahami dan dikodkan tetapi mungkin mahal dari segi masa dan memori. Lihatlah pokok rekursi di bawah. Subtree kiri yang bermula dengan fib (4) dan subtree kanan yang bermula dengan fib (4) sama persis. Mereka menghasilkan hasil yang sama iaitu 3 tetapi melakukan tugas yang sama dua kali. Sekiranya n adalah bilangan yang besar (contoh: 500000) maka pengulangan dapat menjadikan program menjadi sangat lambat kerana akan memanggil sub tugas yang sama berulang kali.

rekursi Pohon-bulat

Untuk mengelakkan masalah ini pengaturcaraan dinamik boleh digunakan. Dalam pengaturcaraan dinamik, kita dapat menggunakan subtugas yang diselesaikan sebelumnya untuk menyelesaikan tugas masa depan dengan jenis yang sama. Ini adalah cara untuk mengurangkan tugas untuk menyelesaikan masalah asal. Mari kita susun serat [] di mana kita menyimpan penyelesaian subtugas yang pernah diselesaikan. Kita sudah tahu bahawa fib [0] = 0 dan fib [1] = 1. Mari kita simpan dua nilai ini. Sekarang, berapakah nilai gentian [2]? Oleh kerana fib [0] = 0 dan fib [1] = 1 telah disimpan, kita hanya perlu mengatakan fib [2] = fib [1] + fib [0] dan itu sahaja. Kita boleh menghasilkan fib [3], fib [4], fib [5], ……, fib [n] dengan cara yang sama. Subtugas yang diselesaikan sebelumnya dipanggil untuk mendapatkan subtugas seterusnya sehingga tugas asalnya belum diselesaikan, sehingga mengurangkan pengiraan berlebihan.