Dengan kata sederhana, rekursi adalah cara untuk memecahkan masalah dengan memiliki panggilan fungsi itu sendiri, Kata “ rekursif 'Berasal dari kata kerja Latin' terulang ”, Yang artinya mengulang sesuatu. Inilah yang dilakukan oleh fungsi rekursif, ia mengulangi hal yang sama berulang kali, yaitu mengingat dirinya sendiri. Pada artikel ini, kita akan belajar tentang rekursi dengan python. Berikut adalah topik yang dibahas dalam blog ini:
- Apa itu Rekursi dengan Python?
- Kondisi Penghentian
- Batas Rekursi Python
- Meratakan Daftar Dengan Rekursi
- Keuntungan Rekursi
- Kekurangan Rekursi
Apa itu Rekursi dengan Python?
Rekursi adalah proses menentukan sesuatu dalam dirinya sendiri. Kita tahu bahwa di Python, fungsi apa pun dapat memanggil fungsi lain, fungsi juga dapat memanggil dirinya sendiri. Jenis fungsi yang memanggil dirinya sendiri sampai kondisi tertentu tidak terpenuhi disebut sebagai fungsi rekursif.
apa itu pengadaan dalam manajemen proyek
mari kita ambil beberapa contoh untuk melihat cara kerjanya, Jika Anda diberi bilangan bulat positif n faktorialnya.
- n! = n * (n-1) * (n-2) dan seterusnya.
- 2! = 2 * (2-1)
- satu! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Mengganti nilai di atas akan menghasilkan ekspresi berikut
- 4! = 4 * 3 * 2 * 1
Kita harus mendefinisikan sebuah fungsi, katakanlah fakta (n) yang mengambil bilangan bulat positif atau 0 sebagai parameternya dan mengembalikan faktorial ke-n, bagaimana kita bisa melakukannya menggunakan rekursi?
Mari kita lihat, untuk melakukannya menggunakan rekursi kita perlu memeriksa persamaan berikut
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! #kita dapat menulis ulang pernyataan di atas seperti pada baris ini
Sekarang di sini jika kita melewatkan 2 sebagai parameter kita akan mendapatkan:
2! = 2.1! = 2
Demikian pula jika kita lolos 1 kita akan mendapatkan:
satu! = 1,0! = 1
typecast ganda ke int java
Tetapi jika kita lulus 0, itu rusak
0! = 0. (- 1)! dan di sini faktorial untuk -1 tidak ditentukan jadi ini hanya berfungsi untuk nilai> 0
Jadi kami harus menulis dua kasus
1. n! = n. (n-1)! jika n> = 1
2. 1 jika n = 0
Ini adalah solusi lengkap untuk semua bilangan bulat positif dan 0.
Kondisi Penghentian
Fungsi rekursif harus memenuhi syarat penting untuk dihentikan. Bergerak menuju kondisi di mana masalah dapat diselesaikan tanpa rekursi lebih lanjut, fungsi rekursif akan berhenti, meminimalkan masalah menjadi sub-langkah yang lebih kecil. Rekursi bisa berakhir di loop tak terbatas jika kondisi terminasi tidak terpenuhi dalam panggilan.
Kondisi faktorial:
- faktorial dari n = n * (n-1) selama n lebih besar dari 1.
- 1 jika n = 0
Kami akan mengubah kondisi faktorial di atas dalam kode python:
def fact (n): if n == 1: return n else: return n * fact (n-1)
Mari kita ambil contoh, katakanlah kita ingin mencari faktorial dari 4:
fakta (4) # ini akan mengembalikan 4 * fakta (3) dan seterusnya sampai n == 1.
Keluaran: 24
Ini sering digunakan sebagai contoh rekursi karena kesederhanaan dan kejelasannya. Memecahkan masalah yang lebih kecil di setiap langkah yang disebut sebagai rekursi dalam ilmu komputer.
Batas Rekursi Python
Dalam beberapa bahasa, Anda dapat membuat loop rekursif tak terbatas, tetapi dalam Python, ada batas rekursi. Untuk memeriksa batas, jalankan fungsi berikut dari modul sys. yang akan memberikan batas set rekursi untuk python.
impor sys sys.getrecursionlimit ()
Keluaran: 1000
Anda juga dapat mengubah batas menggunakan functionsetrecursionlimit () modul sys sesuai dengan kebutuhan Anda, Sekarang mari buat fungsi yang memanggil dirinya sendiri secara rekursif hingga melebihi batas dan memeriksa apa yang terjadi:
def recursive (): recursive () if __name__ == '__main__': recursive ()
Jika Anda menjalankan kode di atas, Anda akan mendapatkan pengecualian waktu proses: RuntimeError: kedalaman rekursi maksimum terlampaui. Python mencegah Anda membuat fungsi yang berakhir di loop rekursif yang tidak pernah berakhir.
Meratakan Daftar Dengan Rekursi
Hal-hal lain yang dapat Anda lakukan menggunakan rekursi kecuali faktorial, katakanlah Anda ingin membuat satu dari daftar yang bertingkat, itu dapat dilakukan dengan menggunakan kode di bawah ini:
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) else: flat_list.append (item) return flat_list if __name__ == '__main__': nested = [1,2,3, [4,5], 6] x = flatten (nested) print (x)
Keluaran: [1,2,3,4,5,6]
Menjalankan kode di atas akan menghasilkan daftar tunggal, bukan daftar bilangan bulat yang berisi daftar bilangan bulat yang kita gunakan sebagai input. Anda juga dapat melakukan hal yang sama menggunakan cara lain juga, Python memiliki sesuatu yang disebut itertools.chain () Anda dapat memeriksa kode yang digunakan untuk membuat rantai fungsi () itu adalah pendekatan yang berbeda untuk melakukan hal yang sama seperti yang kita lakukan.
cara menggunakan iterator
Keuntungan Rekursi
Kode ini bersih dan elegan dalam fungsi rekursif.
Tugas gabungan dapat dipecah menjadi sub-masalah yang lebih sederhana menggunakan rekursi.
Membuat urutan lebih mudah dengan rekursi daripada menggunakan beberapa iterasi bersarang.
Kekurangan Rekursi
Mengikuti logika di balik fungsi rekursif terkadang sulit.
Panggilan rekursif mahal (tidak efisien) karena menghabiskan banyak memori dan waktu.
Fungsi rekursif sulit untuk di-debug.
Pada artikel ini kita melihat apa itu rekursi dan bagaimana kita bisa mengembangkan fungsi rekursif dari pernyataan masalah, bagaimana pernyataan masalah secara matematis dapat didefinisikan. Kami memecahkan masalah faktorial dan menemukan kondisi yang diperlukan untuk menemukan faktorial yang darinya kami dapat mengonversi ketentuan tersebut menjadi kode python, memberi Anda pemahaman tentang cara kerja rekursi. Saya pikir cukup rapi bahwa Python memiliki batas built-in untuk rekursi untuk mencegah pengembang membuat fungsi rekursif yang dibangun dengan buruk. Satu hal penting untuk diperhatikan adalah rekursi sulit untuk di-debug karena fungsi terus memanggil dirinya sendiri.