Nahuli ka na ba sa isang tila walang katapusang cycle kung saan ang isang problema ay patuloy na sumasanga sa mas maliliit na fragment?
Kung gayon, maaaring nakarating ka na sa nakakabighaning mundo ng recursion. Bagama't mukhang mahirap unawain, huwag mag-alala! Sa post na ito, pupunta kami sa isang kawili-wiling paglalakbay upang matutunan ang tungkol sa mga uri ng mga recursion.
Kaya buckle up habang nag-e-explore kami ng maraming recursive approach. Maghanda na pumasok sa kaakit-akit na larangan ng recursion at obserbahan ang kahanga-hangang kakayahan nito sa paglutas ng mga kumplikadong isyu.
Ano ang Eksaktong Mga Recursion?
Sa mga pangunahing salita, ang recursion ay isang makapangyarihang pamamaraan ng programming na may kasamang function na tumatawag sa sarili nito sa panahon ng pagpapatupad. Ito ay tulad ng pagtitig sa salamin at nakikita ang isang imahe sa loob ng isang imahe, na nagreresulta sa isang self-referential cycle.
Maaari naming harapin ang malalaking isyu gamit ang recursion sa pamamagitan ng paghahati sa mga ito sa mas maliliit, mas mapapamahalaang subproblem.
Ito ay katulad ng pagsasama-sama ng isang lagari, kung saan ang isang piraso ay nag-uugnay sa iba pang mga bahagi upang makagawa ng isang buong larawan. Binibigyang-daan kami ng recursion na lutasin ang mga isyu sa eleganteng at mahusay na paraan sa pamamagitan ng pag-uulit ng parehong hanay ng mga tagubilin na may iba't ibang input.
1-Direktang Recursion
Ang direktang recursion ay ang pinakapangunahing uri ng recursion, kung saan direktang tinatawag ng isang function ang sarili nito. Nangangailangan ito ng paghahati ng isang problemadong problema sa mas maliliit na subproblema hanggang sa makamit ang isang batayang kaso, na humahantong sa pagwawakas.
Ang recursive function ay tumatawag sa sarili nito na may iba't ibang input, na nagpapagana sa pagpapatupad ng parehong hanay ng mga tagubilin na maulit. Ang bawat invocation ay bubuo sa nauna, unti-unting lumalapit sa base case na nagiging sanhi ng pagwawakas ng recursion.
Suriin natin ang halimbawang ito.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
output:
5
4
3
2
1
2-Di-tuwirang Recursion
Ang hindi direktang recursion ay nagdaragdag ng nakakaintriga na twist sa recursive path. Sa kaibahan sa direktang recursion, na nagsasangkot ng isang function na tahasang tumatawag sa sarili nito, ang hindi direktang recursion ay kinabibilangan ng isang hanay ng mga function na tawag.
Ang isang function ay tumatawag sa isa pa, na maaaring tumawag sa orihinal na function o anumang iba pang function na sa wakas ay bumalik sa orihinal. Ang magkakaugnay na web ng mga function na tawag ay gumagawa ng isang nakabibighani na sayaw kung saan ang ilang mga function ay nagtutulungan upang ayusin ang isang problema.
Halimbawa:
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-Linear Recursion
Isaalang-alang ang isang paglalakbay sa isang tuwid na ruta, isang hakbang sa isang pagkakataon, hanggang sa makarating ka sa iyong layunin. Ang sequential technique na ito ay kinakatawan ng linear recursion, kung saan ang isang function ay nagsasagawa ng isang solong recursive na tawag sa bawat function na iteration.
Sa bawat recursive na tawag, ang recursive na proseso ay lumalapit sa isang base case sa pamamagitan ng pagpapababa sa laki ng isyu. Nagpapatuloy ito sa isang malinaw at linear na paraan, niresolba ang mga subproblema nang paisa-isa hanggang sa maabot ang pinakahuling sagot.
Halimbawa:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
output:
120
4-Tree Recursion
Kapag ang isang function ay sumanga sa ilang recursive na tawag, papasok tayo sa mundo ng tree recursion. Ang isang function sa tree recursion ay bumubuo ng maraming recursive na tawag, na ang bawat isa ay lumulutas ng isang hiwalay na subproblema, tulad ng ginagawa ng mga sanga ng isang puno.
Nagbibigay-daan ang branching structure na ito para sa sabay-sabay na pagsisiyasat ng ilang ruta, na epektibong hinahati ang mga kumplikadong isyu sa mas maliliit, magkakaugnay na bahagi.
Halimbawa:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
output:
8
5-Nested Recursion
Ang nested recursion ay nagdaragdag ng kapana-panabik na antas ng pagiging kumplikado sa recursive universe. Sa ganitong paraan ng recursion, isinasama ng isang function ang isang recursive na tawag bilang argumento sa loob ng isa pang recursive na tawag.
Ang panloob na recursive na tawag ay kumikilos sa isang halaga na nakadepende sa panlabas na recursive na tawag. Ang pagiging kumplikado ay lumalaki sa bawat nested invocation, na nagtatapos sa isang nakakaintriga na pattern ng mga nested recursive na tawag.
Halimbawa:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Resulta:
91
6-Tail Recursion
Ang tail recursion ay isang diskarte sa pag-optimize para sa mga recursive algorithm na maaaring mapabuti ang kanilang performance. Lumilitaw ang recursive na tawag bilang panghuling pagkilos ng isang function na may tail recursion, making.
Dahil walang natitirang mga operasyon kasunod ng recursive na tawag, maaaring gawing simple ng compiler o interpreter ang recursion sa pamamagitan ng pagpapalit nito ng isang simpleng pagtalon.
Ang diskarte sa pag-optimize na ito, na kilala bilang tail call optimization, ay binabawasan ang pangangailangan para sa bawat recursive na tawag upang mapanatili ang isang stack frame, na nagreresulta sa pinahusay na bilis at mas mababang paggamit ng memorya.
Halimbawa:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Outout:
120
7-Non-Tail Recursion
Sa kaibahan sa tail recursion, ang non-tail recursion ay nagsasangkot ng mga karagdagang aktibidad na ginawa pagkatapos ng recursive na tawag sa loob ng isang function. Bago magsagawa ng higit pang mga pagkilos, dapat makumpleto at bumalik ang bawat recursive na tawag.
Bilang kinahinatnan, hanggang sa maabot ang base case at matapos ang recursion, isang stack ng mga natitirang operasyon ay pinananatili. Ang non-tail recursion ay madalas na gumagamit ng mas maraming memory at hindi gaanong mahusay kaysa sa tail recursion, ngunit ito ay isang kapaki-pakinabang na tool para sa pagharap sa iba't ibang isyu.
Halimbawa:
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
Balutin
Ang recursion ay isang nakakaintriga na konsepto sa programming. Nagbibigay-daan ito sa amin na harapin ang mga kumplikadong problema sa isang recursive, self-referential na paraan.
Nag-aalok ito ng natatanging paraan ng pag-iisip at paglutas ng mga problema, hinahati-hati ang mga ito sa mas maliit, mas madaling pamahalaang mga tipak. Kapag nagtatrabaho sa recursion, gayunpaman, ito ay kritikal na gumamit ng pansin sa ilang mga punto.
Dapat mong tukuyin ang mga angkop na base case na nagpapahintulot sa recursion na matapos. Kung wala ang mga ito, maaaring patuloy na tawagin ng function ang sarili nito magpakailanman.
Pangalawa, batay sa sitwasyong nasa kamay, ang pagpili ng naaangkop na uri ng recursion ay maaaring humantong sa mas mahusay at eleganteng mga solusyon. Subukan upang mahanap kung ano ang pinakamahusay na gumagana para sa problema sa kamay. Kapag nagtatrabaho sa malawak na recursion depth, magkaroon ng kamalayan sa mga potensyal na panganib tulad ng stack overflow.
Mag-iwan ng Sagot