Pernahkah anda terperangkap dalam kitaran yang kelihatan tidak berkesudahan di mana masalah terus bercabang menjadi serpihan yang lebih kecil?
Jika ya, anda mungkin telah menemui dunia rekursi yang memikat. Walaupun nampaknya sukar untuk difahami, jangan risau! Dalam siaran ini, kami akan meneruskan perjalanan yang menarik untuk mengetahui tentang jenis rekursi.
Jadi sandarkan diri semasa kami meneroka pelbagai pendekatan rekursif. Bersedia untuk memasuki alam rekursi yang menarik dan perhatikan keupayaannya yang luar biasa dalam menyelesaikan isu rumit.
Apakah Sebenarnya Rekursi?
Secara asasnya, rekursi ialah teknik pengaturcaraan yang berkuasa yang merangkumi fungsi yang memanggil dirinya sendiri semasa pelaksanaan. Ia seperti merenung ke dalam cermin dan melihat imej di dalam imej, menghasilkan kitaran rujukan kendiri.
Kita boleh menangani isu besar menggunakan rekursi dengan membahagikannya kepada submasalah yang lebih kecil dan lebih mudah diurus.
Ia sama seperti menyusun jigsaw, di mana satu bahagian menghubungkan ke bahagian lain untuk menghasilkan gambar penuh. Rekursi membolehkan kami menyelesaikan isu dengan cara yang elegan dan cekap dengan mengulang set arahan yang sama dengan pelbagai input.
1-Rekursi Langsung
Rekursi langsung ialah jenis rekursi yang paling asas, di mana fungsi memanggil dirinya secara langsung. Ia memerlukan pembahagian masalah bermasalah kepada submasalah yang lebih kecil sehingga kes asas dicapai, yang membawa kepada penamatan.
Fungsi rekursif memanggil dirinya dengan pelbagai input, membolehkan pelaksanaan set arahan yang sama diulang. Setiap seruan dibina pada seruan sebelumnya, secara beransur-ansur menghampiri kes asas yang menyebabkan pengulangan berakhir.
Mari kita semak contoh ini.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Output:
5
4
3
2
1
2-Rekursi Tidak Langsung
Rekursif tidak langsung menambah sentuhan yang menarik pada laluan rekursif. Berbeza dengan rekursi langsung, yang melibatkan fungsi secara eksplisit memanggil dirinya sendiri, rekursi tidak langsung termasuk rangkaian panggilan fungsi.
Satu fungsi memanggil yang lain, yang kemudiannya boleh memanggil fungsi asal atau mana-mana fungsi lain yang akhirnya kembali kepada asal. Panggilan fungsi web yang saling berkait ini menghasilkan tarian yang memikat di mana beberapa fungsi bekerjasama untuk menyelesaikan masalah.
Contoh:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
Output:
A: 3
B: 2
A: 1
3-Rekursi Linear
Pertimbangkan perjalanan melalui laluan yang lurus, satu langkah pada satu masa, sehingga anda tiba pada objektif anda. Teknik urutan ini dijelmakan oleh rekursi linear, di mana fungsi melakukan satu panggilan rekursif dalam setiap lelaran fungsi.
Dengan setiap panggilan rekursif, proses rekursif bergerak lebih dekat kepada kes asas dengan mengurangkan saiz isu. Ia diteruskan dengan cara yang jelas dan linear, menyelesaikan submasalah satu demi satu sehingga jawapan muktamad dicapai.
Contoh:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Output:
120
4-Rekursi Pokok
Apabila fungsi bercabang menjadi beberapa panggilan rekursif, kita memasuki dunia rekursi pokok. Fungsi dalam rekursi pokok menjana banyak panggilan rekursif, setiap satunya menyelesaikan submasalah yang berasingan, seperti yang dilakukan oleh dahan pokok.
Struktur percabangan ini membolehkan penyiasatan serentak beberapa laluan, dengan berkesan memecahkan isu rumit kepada komponen yang lebih kecil dan saling berkaitan.
Contoh:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Output:
8
5-Rekursi Bersarang
Rekursi bersarang menambah tahap kerumitan yang menarik kepada alam semesta rekursif. Dalam bentuk rekursif ini, fungsi menggabungkan panggilan rekursif sebagai hujah dalam panggilan rekursif yang lain.
Panggilan rekursif dalam bertindak pada nilai yang bergantung pada panggilan rekursif luar. Kerumitan bertambah dengan setiap seruan bersarang, yang memuncak dalam corak panggilan rekursif bersarang yang menarik.
Contoh:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
keputusan:
91
6-Rekursi Ekor
Rekursi ekor ialah teknik pengoptimuman untuk algoritma rekursif yang boleh meningkatkan prestasinya. Panggilan rekursif muncul sebagai tindakan terakhir fungsi dengan rekursif ekor, membuat.
Oleh kerana tiada operasi tertunggak selepas panggilan rekursif, pengkompil atau penterjemah boleh memudahkan rekursi dengan menggantikannya dengan lompatan mudah.
Pendekatan pengoptimuman ini, dikenali sebagai pengoptimuman panggilan ekor, mengurangkan keperluan untuk setiap panggilan rekursif untuk mengekalkan bingkai tindanan, menghasilkan kelajuan yang dipertingkatkan dan penggunaan memori yang lebih rendah.
Contoh:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Keluar:
120
7-Rekursi Bukan Ekor
Berbeza dengan rekursi ekor, rekursi bukan ekor melibatkan aktiviti tambahan yang dilakukan selepas panggilan rekursif dalam fungsi. Sebelum apa-apa lagi tindakan boleh dilakukan, setiap panggilan rekursif mesti selesai dan kembali.
Akibatnya, sehingga kes asas dicapai dan rekursi berakhir, timbunan operasi tertunggak dikekalkan. Rekursi bukan ekor kerap menggunakan lebih banyak memori dan kurang cekap daripada rekursi ekor, tetapi ia masih merupakan alat yang berguna untuk menangani pelbagai isu.
Contoh:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Output:
15
Wrap Up
Rekursi adalah konsep yang menarik dalam pengaturcaraan. Ia membolehkan kami menangani masalah rumit secara rekursif, merujuk kendiri.
Ia menawarkan kaedah tersendiri untuk memikirkan dan menyelesaikan masalah, membahagikannya kepada bahagian yang lebih kecil dan lebih mudah diurus. Apabila bekerja dengan rekursi, bagaimanapun, adalah penting untuk menggunakan perhatian kepada beberapa perkara.
Anda harus mengenal pasti kes asas yang sesuai yang membolehkan rekursi berakhir. Jika mereka tidak hadir, fungsi itu boleh terus memanggil dirinya selama-lamanya.
Kedua, berdasarkan senario yang ada, memilih jenis rekursi yang sesuai boleh membawa kepada penyelesaian yang lebih cekap dan elegan. Cuba cari apa yang paling sesuai untuk masalah di tangan. Apabila bekerja dengan kedalaman rekursi yang luas, berhati-hati tentang potensi bahaya seperti limpahan tindanan.
Sila tinggalkan balasan anda