Dengan kata mudah, rekursi adalah cara menyelesaikan masalah dengan mempunyai fungsi memanggilnya sendiri, Kata “ rekursif 'Berasal dari kata kerja Latin' berulang ', Yang bermaksud membuat semula sesuatu. Inilah yang dilakukan oleh fungsi rekursif, ia melakukan perkara yang sama berulang-ulang kali, iaitu mengingat semula. Dalam artikel ini, kita akan belajar mengenai rekursi pada ular sawa. Berikut adalah topik yang dibahas dalam blog ini:
- Apakah rekursi di Python?
- Keadaan Penamatan
- Had Pengulangan Python
- Meratakan Daftar Dengan Pengulangan
- Kelebihan Berulang
- Kekurangan Pengulangan
Apakah rekursi di Python?
Rekursi adalah proses menentukan sesuatu dari segi dirinya sendiri. Kita tahu bahawa di Python, fungsi apa pun boleh memanggil fungsi lain, fungsi juga boleh memanggil dirinya sendiri. Jenis fungsi yang memanggil dirinya sehingga keadaan tertentu tidak dipenuhi disebut sebagai fungsi rekursif.
mari kita ambil beberapa contoh untuk melihat bagaimana ia berfungsi, Sekiranya anda diberi bilangan bulat positif dan faktorialnya.
- n! = n * (n-1) * (n-2) dan sebagainya.
- 2! = 2 * (2-1)
- satu! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Menggantikan nilai di atas akan menghasilkan ungkapan berikut
- 4! = 4 * 3 * 2 * 1
Kita harus menentukan fungsi katakanlah fakta (n) yang mengambil bilangan bulat positif atau 0 sebagai parameternya dan mengembalikan faktorial ke-9, bagaimana kita dapat melakukannya dengan menggunakan pengulangan?
java cara mengklon objek
Mari kita lihat, untuk melakukannya menggunakan rekursi, kita perlu meneliti persamaan berikut
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! #kita boleh menulis semula pernyataan di atas seperti di baris ini
Sekarang di sini jika kita lulus 2 sebagai parameter kita akan mendapat:
2! = 2.1! = 2
Begitu juga, jika kita lulus 1 kita akan mendapat:
satu! = 1.0! = 1
Tetapi jika kita lulus 0, ia akan pecah
0! = 0. (- 1)! dan di sini faktorial untuk -1 tidak didefinisikan jadi ini berfungsi hanya untuk nilai> 0
Oleh itu, kita harus menulis dua kes
1. n! = n. (n-1)! jika n> = 1
2. 1 jika n = 0
Ini adalah penyelesaian lengkap untuk semua bilangan bulat positif dan 0.
tableau menggabungkan dua sumber data
Keadaan Penamatan
Fungsi rekursif harus memenuhi syarat penting untuk ditamatkan. Melangkah ke keadaan di mana masalah dapat diselesaikan tanpa berulang lagi, fungsi rekursif akan berakhir, meminimumkan masalah menjadi sub-langkah yang lebih kecil. Pengulangan boleh berakhir dalam gelung tanpa batas jika keadaan penamatan tidak dipenuhi dalam panggilan.
Keadaan faktorial:
- faktorial n = n * (n-1) selagi n lebih besar daripada 1.
- 1 jika n = 0
Kami akan menukar keadaan faktorial di atas dalam kod python:
fakta def (n): jika n == 1: kembali n lain: kembali n * fakta (n-1)
Mari kita ambil contoh, katakan kita mahu mencari faktor 4:
fakta (4) # ini akan mengembalikan fakta 4 * (3) dan seterusnya sehingga n == 1.
Pengeluaran: 24
Ia sering digunakan sebagai contoh untuk berulang kerana kesederhanaan dan kejelasannya. Menyelesaikan masalah yang lebih kecil pada setiap langkah yang disebut sebagai pengulangan dalam sains komputer.
Had Pengulangan Python
Dalam beberapa bahasa, anda boleh membuat gelung rekursif yang tidak terbatas tetapi, di Python, terdapat had berulang. Untuk memeriksa had jalankan fungsi berikut dari modul sys. yang akan memberikan had rekursi yang ditetapkan untuk python.
import sys sys.getrecursionlimit ()
Pengeluaran: 1000
Anda juga dapat mengubah had menggunakan fungsi setrecursionlimit modul sys () sesuai dengan keperluan anda, Sekarang mari kita buat fungsi yang memanggil dirinya secara berulang sehingga melebihi had dan memeriksa apa yang berlaku:
apa itu jurubahasa dalam java
def recursive (): recursive () if __name__ == '__main__': recursive ()
Sekiranya anda menjalankan kod di atas, anda akan mendapat pengecualian runtime: RuntimeError: kedalaman rekursi maksimum terlampaui. Python menghalang anda membuat fungsi yang berakhir dalam gelung rekursif yang tidak pernah berakhir.
Meratakan Daftar Dengan Pengulangan
Perkara-perkara lain yang boleh anda lakukan dengan menggunakan rekursi kecuali faktorial, katakan anda ingin membuat satu dari senarai yang bersarang, ini boleh dilakukan dengan menggunakan kod di bawah:
def flatten (a_list, flat_list = none): if flat_list is none: flat_list = [] untuk item dalam a_list: if isinstance (item, list): flatten (item, flat_list) other: flat_list.append (item) return flat_list if __name__ == '__main__': bersarang = [1,2,3, [4,5], 6] x = ratakan (bersarang) cetakan (x)
Pengeluaran: [1,2,3,4,5,6]
Menjalankan kod di atas akan menghasilkan satu senarai dan bukannya senarai bilangan bulat yang mengandungi senarai bilangan bulat yang kami gunakan sebagai input. Anda juga boleh melakukan perkara yang sama dengan cara lain juga, Python mempunyai sesuatu yang disebut itertools.chain () anda boleh memeriksa kod yang digunakan untuk membuat rantai fungsi () ini adalah pendekatan yang berbeza untuk melakukan perkara yang sama seperti yang kita lakukan.
Kelebihan Berulang
Kodnya bersih dan elegan dalam fungsi rekursif.
Tugas komposit dapat dipecah menjadi sub-masalah yang lebih mudah dengan menggunakan rekursi.
Menjana urutan lebih mudah dengan pengulangan daripada menggunakan beberapa lelaran bersarang.
Kekurangan Pengulangan
Mengikuti logik di sebalik fungsi rekursif kadang-kadang sukar.
Panggilan berulang adalah mahal (tidak cekap) kerana memerlukan banyak memori dan masa.
Fungsi rekursif sukar untuk di-debug.
Dalam artikel ini kita melihat apa itu rekursi dan bagaimana kita dapat mengembangkan fungsi rekursif dari pernyataan masalah, bagaimana secara matematik pernyataan masalah dapat didefinisikan. Kami menyelesaikan masalah faktorial dan mengetahui syarat-syarat yang diperlukan untuk mencari faktorial dari mana kami dapat mengubah keadaan itu menjadi kod python yang memberi anda pemahaman tentang bagaimana rekursi berfungsi. Saya berpendapat bahawa Python mempunyai had yang teratur untuk pengulangan untuk mengelakkan pembangun membuat fungsi rekursif yang kurang dibina. Satu perkara penting yang perlu diperhatikan adalah bahawa rekursi sukar untuk debug kerana fungsi terus memanggilnya sendiri.