Apakah Rekursi dan Bagaimana Anda Menggunakannya?

Rekursi ialah konsep pengaturcaraan yang menyeronokkan tetapi boleh menjadi sedikit sukar untuk dipelajari. Rekursi hanya bermaksud sesuatu yang berulang. Jika anda ingin melihat contoh rekursi yang kurang ajar, cuba cari rekursi di Google. Anda akan menemui telur Paskah di mana cadangan hasil carian adalah rekursif. Jika, sebaliknya, anda ingin belajar cara mengekod fungsi rekursif, baca terus!

Apakah Fungsi Rekursif?

Fungsi rekursif ialah fungsi yang memanggil dirinya sendiri. Anda pada asasnya membuat gelung dengan fungsi. Seperti yang anda boleh bayangkan, ini boleh menjadi fungsi yang sukar untuk ditulis. Anda tidak mahu kod anda berjalan selama-lamanya.

Sama seperti gelung, fungsi rekursif akan dikawal oleh keadaan. Setelah syarat dipenuhi, fungsi berhenti memanggil dirinya sendiri, yang menghentikan gelung. Beginilah cara anda boleh mencipta fungsi yang memanggil dirinya sendiri tanpa ia berjalan selama-lamanya.

Walaupun fungsi rekursif bertindak seperti gelung, ia dilaksanakan oleh komputer secara berbeza. Jadi, sesetengah algoritma lebih cekap dalam gelung dan yang lain mendapat manfaat daripada fungsi rekursif. Tetapi sebelum kita melihat cara menggunakan fungsi rekursif, anda perlu tahu cara menulisnya.

Cara Menulis Fungsi Rekursif

Semua fungsi rekursif mempunyai struktur asas yang sama:

FUNCTION name IF condition THEN RETURN result ELSE CALL FUNCTION name END FUNCTION

Contoh di atas ditulis dalam pseudo-code. Ia menggariskan struktur fungsi, yang boleh digunakan pada mana-mana bahasa. Untuk kesederhanaan, dalam artikel ini, kami akan menumpukan pada Python.

Perkara pertama yang perlu diperhatikan tentang fungsi rekursif ialah apabila syarat dipenuhi, fungsi itu keluar dari rekursif. Ini bermakna apabila anda menulis fungsi rekursif, perkara pertama yang anda ingin tentukan ialah masa untuk menghentikan rekursif.

Jika syarat tidak dipenuhi, fungsi akan memanggil dirinya sendiri. Jadi, jika anda ingin menghantar maklumat ke gelung seterusnya, anda perlu menghantarnya sebagai hujah dalam fungsi anda. Ini boleh memberikan fungsi rekursif lebih kuasa.

Berkaitan: Apakah Fungsi dalam Pengaturcaraan?

Contoh Fungsi Rekursif dalam Python

Ia akan menjadi lebih mudah untuk memahami cara rekursi berfungsi apabila anda melihatnya dalam tindakan. Untuk menunjukkannya, mari tulis fungsi rekursif yang mengembalikan faktorial nombor.

Faktor mengembalikan hasil darab suatu nombor dan semua integer sebelum itu. Sebagai contoh, faktorial bagi 5 ialah 5 x 4 x 3 x 2 x 1 atau, 120.

def factorialFunction(numberToMultiply): if numberToMultiply == 1 : return 1 else : return numberToMultiply * factorialFunction(numberToMultiply - 1) result = factorialFunction(3) print(result) //Outputs: 6

Program di atas akan memberikan anda keputusan 6, yang merupakan faktorial bagi nombor 3. Ini boleh menjadi sedikit mengelirukan pada mulanya. Ia akan membantu jika kita menjalankan program langkah demi langkah.

1. Apabila fungsi dipanggil, numberToMultiply sama dengan 3.
2. Syarat tidak dipenuhi, jadi kita pergi ke syarat lain .
3.  Fungsi kami mengembalikan 3 * tetapi kemudian dijeda. Ia mesti memanggil dirinya sendiri untuk menentukan baki nilai yang dipulangkan.
4. Apabila fungsi dipanggil kali ini, nilai numberToMultiply sama dengan 2.
5. Syarat tidak dipenuhi, jadi kita pergi ke syarat lain.
6. Fungsi kami mengembalikan 2 * tetapi kemudian dijeda. Ia mesti memanggil dirinya sendiri untuk menentukan baki nilai yang dipulangkan.
7. Fungsi dipanggil lagi. Kali ini, nilai numberToMultiply sama dengan 1.
8. Syarat kami jika dipenuhi. Fungsi mengembalikan 1.
9. Fungsi dari langkah 6 kini boleh mengembalikan 2 * 1 kepada fungsi pada langkah 3.
10. Fungsi pada langkah tiga kini boleh mengembalikan 3 * 2 * 1, iaitu 6.

Rekursi adalah konsep yang rumit. Ia boleh membantu untuk menganggapnya sebagai menyusun satu fungsi di atas fungsi lain. Setelah satu fungsi akhirnya diselesaikan, ia boleh menghantar maklumat kembali ke dalam timbunan, sehingga semua fungsi mempunyai jawapannya.

Inilah sebenarnya yang dilakukan oleh komputer anda. Apabila anda memanggil fungsi, ia disimpan dalam ingatan sehingga ia dikembalikan. Ini bermakna fungsi rekursif boleh menggunakan lebih banyak memori daripada gelung.

Oleh itu, mungkin tidak cekap untuk menulis gelung sebagai fungsi rekursif, tetapi ia adalah cara terbaik untuk berlatih membinanya. Anda sepatutnya boleh membuat kod gelung sebagai fungsi rekursif dengan hasil yang serupa.

Contoh Cara Menukar Gelung kepada Fungsi Rekursif

print("Enter an even number:") i = int(input()) while (i % 2) != 0 : print("That number is not even. Please enter a new number:") i = int(input())

Gelung ini juga boleh ditulis secara rekursif sebagai:

def recursiveFunction(number) : if (number % 2) == 0 : return number else: print("That number is not even. Please enter a new number:") recursiveFunction(int(input())) print("Enter and even number:") i = recursiveFunction(int(input()))

Langkah pertama ialah menentukan bila anda mahu fungsi anda berhenti. Dalam kes ini, kami mahu ia berhenti sebaik sahaja nombor genap dimasukkan. Dalam contoh kami, nombor menjejaki input pengguna. Jika mereka memasukkan nombor genap, kami mengembalikan nombor itu. Jika tidak, kami akan terus meminta nombor baru.

Untuk menyediakan gelung, kami memanggil fungsi kami sekali lagi. Tetapi kali ini, nombor yang kita hantar ke fungsi seterusnya adalah nombor baru yang dimasukkan oleh pengguna. Panggilan fungsi seterusnya akan menyemak nombor.

Ini adalah fungsi yang sangat buruk! Ya, ia sedang menyemak sama ada nombor itu genap, seperti gelung kami, tetapi ia tidak cekap. Setiap kali pengguna memasukkan nombor ganjil, fungsi tersebut disimpan dalam ingatan dan fungsi baharu dipanggil. Jika anda melakukan ini cukup kali, anda akan kehabisan ingatan!

Berkaitan: Contoh Python Asas Yang Akan Membantu Anda Belajar Dengan Pantas

Contoh Dunia Sebenar bagi Fungsi Rekursif

Contoh di atas adalah contoh yang baik tentang masa tidak menggunakan rekursi. Jadi, di manakah rekursi digunakan? Contoh yang baik apabila anda ingin menggunakan rekursi ialah mencari pokok binari.

Apabila data distrukturkan dalam pepohon binari, anda perlu pergi ke banyak laluan untuk mencari data. Pada setiap titik dalam pokok, anda perlu memutuskan sama ada anda mahu terus mencari di sebelah kanan atau kiri. Anda boleh menyimpan bahagian pokok yang anda lawati dalam pembolehubah, tetapi fungsi rekursif secara semula jadi boleh menjejaki maklumat tersebut.

Bayangkan kita sedang mencari nombor enam dalam pokok di atas. Kita boleh membuat fungsi rekursif yang mencari pokok dari kiri ke kanan. Algoritma akan kelihatan seperti ini:

FUNCTION searchTree(branchToSearch) IF find 6 OR end of tree THEN RETURN result ELSE PROCESS branch CALL FUNCTION searchTree(left) CALL FUNCTION searchTree(right) END FUNCTION

Dalam contoh pseudokod ini, algoritma akan mencari bahagian kiri pokok terlebih dahulu. Setiap kali ia melawat nombor baharu, fungsi itu dijeda dan disimpan dalam ingatan. Ini membolehkan kami menjejaki di mana kami berada.

Algoritma akan sentiasa mencari bahagian kiri sejauh yang boleh dahulu. sebaik sahaja ia sampai ke hujung pokok, searchTree(kiri) akan selesai dan ia akan menyemak bahagian kanan. Setelah kedua-dua belah disemak, carian menyandarkan satu cawangan dan terus menyemak bahagian kanan.

Jika algoritma mencari keseluruhan pokok, ia akan melakukannya mengikut urutan:

2, 7, 2, 6, 5, 11, 5, 9, dan 4

Lihat jika anda boleh mengikuti bersama menggunakan kod pseudo di atas.

Semakan Rekursi

Rekursi ialah topik lanjutan. Ia akan mengambil sedikit masa untuk memahami dan lebih lama lagi untuk mahir mengekodnya. Ia akan membantu jika anda berjalan melalui fungsi rekursif langkah demi langkah. Malah mungkin membantu untuk menyusun kad indeks atau nota pos semasa anda melalui fungsi apabila belajar untuk mewakili setiap panggilan fungsi.

Apabila menulis fungsi rekursif, mulakan dengan memutuskan cara anda ingin keluar dari fungsi tersebut. Seterusnya, tentukan cara menyediakan gelung anda. Kenal pasti maklumat yang perlu dihantar ke panggilan fungsi seterusnya dan apa yang perlu dikembalikan.

Cara terbaik untuk mempelajari rekursi adalah dengan mempraktikkannya dan belajar daripada kesilapan anda. Lihat beberapa kod lama anda dan cabar diri anda untuk menulis semula gelung sebagai fungsi rekursif. Ia mungkin tidak akan menjadikan kod anda lebih cekap, tetapi ia akan menjadi amalan yang baik.