Sa mga simpleng salita, ang recursion ay isang paraan ng paglutas ng problema sa pamamagitan ng pagkakaroon ng isang function na tawagan mismo, Ang salitang ' recursive 'Nagmula sa pandiwang Latin na' umulit ”, Na nangangahulugang muling gawin ang isang bagay. Ito ang ginagawa ng recursive function, muling ginagawa nito ang parehong bagay nang paulit-ulit, ibig sabihin ay naaalala nito ang sarili. Sa artikulong ito, malalaman natin ang tungkol sa recursion sa sawa. Ang sumusunod ay ang mga paksang sakop sa blog na ito:
- Ano ang Recursion sa Python?
- Kalagayan sa Pagwawakas
- Limit sa Recursion ng Python
- Mga Flattening List na May Recursion
- Mga kalamangan Ng Recursion
- Disadvantages Ng Recursion
Ano ang Recursion sa Python?
Ang recursion ay ang proseso ng pagtukoy ng isang bagay sa mga tuntunin ng sarili nito. Alam namin na sa Python, ang anumang pagpapaandar ay maaaring tumawag sa anumang iba pang pagpapaandar, ang isang pagpapaandar ay maaari ding tawagan ang sarili nito. Ang mga uri ng pag-andar na tumawag sa sarili nito hanggang sa hindi natugunan ang tiyak na kundisyon ay tinawag bilang mga recursive function.
kumuha tayo ng ilang mga halimbawa upang makita kung paano ito gumagana, Kung bibigyan ka ng isang positibong integer n ang factorial ay magiging.
- n! = n * (n-1) * (n-2) at iba pa.
- 2! = 2 * (2-1)
- isa! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Ang pagpapalit ng mga halagang nasa itaas ay magreresulta sa sumusunod na expression
- 4! = 4 * 3 * 2 * 1
Kailangan nating tukuyin ang isang pagpapaandar na hinahayaan na sabihin ang katotohanan (n) na kung saan ay tumatagal ng positibong integer o 0 bilang parameter nito at ibabalik ang ika-n na factorial, paano natin magagawa iyon gamit ang recursion?
Tingnan natin, upang magawa ito gamit ang recursion kailangan nating suriin ang sumusunod na equation
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! Maaari nating muling isulat ang pahayag sa itaas tulad ng sa linyang ito
Ngayon dito kung pumasa kami sa 2 bilang parameter makakakuha kami ng:
2! = 2.1! = 2
Katulad nito, kung pumasa tayo sa 1 makukuha natin ang:
isa! = 1.0! = 1
Ngunit kung pumasa tayo sa 0, masisira ito
ay isang java ay isang java
0! = 0. (- 1)! at dito ang factorial para sa -1 ay hindi tinukoy kaya gumagana lamang ito para sa mga halagang> 0
Kaya kailangan nating magsulat ng dalawang kaso
1. n! = n. (n-1)! kung n> = 1
2. 1 kung n = 0
Ito ay isang kumpletong solusyon para sa lahat ng mga positibong integer at 0.
Kalagayan sa Pagwawakas
Ang isang recursive function ay kailangang matupad ang isang mahalagang kondisyon upang wakasan. Ang paglipat patungo sa isang kundisyon kung saan malulutas ang problema nang walang karagdagang recursion, ang isang recursive function ay magwawakas, pinapaliit ang problema sa mas maliit na mga sub-step. Ang isang recursion ay maaaring magtapos sa isang walang katapusan na loop kung ang kalagayan ng pagwawakas ay hindi natutugunan sa mga tawag.
Mga kundisyon ng kadahilanan:
- factorial ng n = n * (n-1) basta ang n ay mas malaki sa 1.
- 1 kung n = 0
I-convert namin ang mga kundisyon ng factorial sa itaas sa python code:
def fact (n): kung n == 1: bumalik n iba: bumalik n * fact (n-1)
Kumuha tayo ng isang halimbawa, sabihin na nais nating makahanap ng factorial ng 4:
katotohanan (4) #ito ang ibabalik 4 * katotohanan (3) at iba pa hanggang n == 1.
Output: 24
Ginagamit ito nang madalas bilang isang halimbawa para sa recursion dahil sa pagiging simple at kalinawan nito. Ang paglutas ng mas maliit na mga pagkakataon ng isang problema sa bawat hakbang na ito ay tinawag bilang recursion sa computer science.
Limit sa Recursion ng Python
Sa ilang mga wika, maaari kang lumikha ng isang walang katapusang recursive loop ngunit, sa Python, mayroong isang limitasyon sa recursion. Upang suriin ang limitasyon patakbuhin ang sumusunod na pagpapaandar mula sa sys module. na magbibigay ng hangganan ng itinakdang recursion para sa sawa.
pinakamahusay na java ide para sa windows
import sys sys.getrecursionlimit ()
Output: 1000
Maaari mo ring baguhin ang limitasyon gamit ang sys module's functionsetrecursionlimit () alinsunod sa iyong kinakailangan, Ngayon ay lumikha tayo ng isang pagpapaandar na tumatawag nang paulit-ulit hanggang sa lumampas sa limitasyon at suriin kung ano ang mangyayari:
def recursive (): recursive () kung __name__ == '__main__': recursive ()
Kung patakbuhin mo ang code sa itaas, makakakuha ka ng isang pagbubukod ng runtime: RuntimeError: lumagpas sa maximum na lalim ng recursion. Pinipigilan ka ng Python mula sa paglikha ng isang pagpapaandar na nagtatapos sa isang walang katapusang recursive loop.
Mga Flattening List na May Recursion
Ang iba pang mga bagay na maaari mong gawin gamit ang recursion maliban sa mga factorial, sabihin natin na nais mong lumikha ng solong mula sa isang listahan na may pugad, magagawa ito gamit ang code sa ibaba:
def flatten (a_list, flat_list = none): kung ang flat_list ay wala: flat_list = [] para sa item sa a_list: kung isinstance (item, list): patagin (item, flat_list) iba pa: flat_list.append (item) bumalik flat_list kung __name__ == '__main__': pugad = [1,2,3, [4,5], 6] x = patagin (pugad) i-print (x)
Output: [1,2,3,4,5,6]
Ang pagpapatakbo ng code sa itaas ay magreresulta sa isang solong listahan sa halip na listahan ng integer na naglalaman ng listahan ng integer na ginamit namin bilang input. Maaari mo ring gawin ang parehong bagay gamit ang iba pang mga paraan, ang Python ay may tinatawag na itertools.chain () maaari mong suriin ang code na ginamit para sa paglikha ng isang function chain () ito ay ibang diskarte upang gawin ang parehong bagay tulad ng ginawa namin.
Mga kalamangan Ng Recursion
Ang code ay malinis at matikas sa isang recursive function.
Ang isang pinaghalong gawain ay maaaring hatiin sa mas simpleng mga sub-problema gamit ang recursion.
Ang pagbuo ng pagkakasunud-sunod ay mas madali sa recursion kaysa sa paggamit ng ilang nakapugad na ulit.
Disadvantages Ng Recursion
Ang pagsunod sa lohika sa likod ng recursive function ay maaaring mahirap minsan.
Ang mga rekursibong tawag ay mahal (hindi mabisa) habang tumatagal sila ng maraming memorya at oras.
Ang mga recursive function ay mahirap i-debug.
Sa artikulong ito nakita natin kung ano ang recursion at paano tayo makakabuo ng mga recursive function mula sa pahayag ng problema, kung paano maaaring tukuyin ang matematika ng isang pahayag ng problema. Nalutas namin ang isang problema ng factorial at nalaman ang mga kundisyong kinakailangan upang makahanap ng mga factorial kung saan nagawa naming i-convert ang mga kundisyon na iyon sa python code na magbibigay sa iyo ng pag-unawa sa kung paano gumagana ang recursion. Sa palagay ko ay maayos na ang Python ay may built-in na limitasyon para sa recursion upang maiwasan ang mga developer na lumikha ng hindi magandang konstruksyon na recursive function. Ang isang mahalagang bagay na mapapansin ay ang recursion ay mahirap i-debug dahil ang pagpapaandar ay patuloy na tumatawag mismo.