Rekursija ir fundamentāls jēdziens datorzinātnēs un matemātikā, kas ļauj funkcijām izsaukt sevi, ļaujot atrisināt sarežģītas problēmas, izmantojot iteratīvus soļus. Viens vizuālais attēlojums, ko parasti izmanto, lai izprastu un analizētu rekursīvo funkciju izpildi, ir rekursijas koks. Šajā rakstā mēs izpētīsim rekursijas koku teoriju, to struktūru un nozīmi rekursīvo algoritmu izpratnē.

Kas ir rekursijas koks?

Rekursijas koks ir grafisks attēlojums, kas ilustrē rekursīvās funkcijas izpildes plūsmu. Tas nodrošina vizuālu rekursīvo zvanu sadalījumu, parādot algoritma progresu, kad tas atzarojas un galu galā sasniedz bāzes gadījumu. Koka struktūra palīdz analizēt laika sarežģītību un izprast iesaistīto rekursīvo procesu.

Koka struktūra

Katrs rekursijas koka mezgls apzīmē noteiktu rekursīvo zvanu. Sākotnējais zvans ir attēlots augšpusē, un turpmākie zvani atzarojas zem tā. Koks aug uz leju, veidojot hierarhisku struktūru. Katra mezgla sazarošanas koeficients ir atkarīgs no funkcijas ietvaros veikto rekursīvo zvanu skaita. Turklāt koka dziļums atbilst rekursīvo zvanu skaitam pirms bāzes gadījuma sasniegšanas.

Pamatlieta

Bāzes gadījums kalpo kā beigu nosacījums rekursīvai funkcijai. Tas nosaka punktu, kurā rekursija apstājas un funkcija sāk atgriezt vērtības. Rekursijas kokā mezgli, kas attēlo bāzes gadījumu, parasti tiek attēloti kā lapu mezgli, jo tie neizraisa turpmākus rekursīvus izsaukumus.

Rekursīvie zvani

Pakārtotie mezgli rekursijas kokā attēlo rekursīvos izsaukumus, kas veikti funkcijā. Katrs pakārtotais mezgls atbilst atsevišķam rekursīvam izsaukumam, kā rezultātā tiek izveidotas jaunas apakšproblēmas. Vērtības vai parametri, kas tiek nodoti šiem rekursīvajiem izsaukumiem, var atšķirties, kā rezultātā var atšķirties apakšproblēmu raksturlielumi.

Izpildes plūsma:

Rekursijas koka šķērsošana sniedz ieskatu rekursīvās funkcijas izpildes plūsmā. Sākot no sākotnējā izsaukuma saknes mezglā, mēs sekojam zariem, lai sasniegtu nākamos izsaukumus, līdz sastopamies ar bāzes gadījumu. Kad tiek sasniegti bāzes gadījumi, rekursīvie izsaukumi sāk atgriezties, un to attiecīgie mezgli kokā tiek atzīmēti ar atgrieztajām vērtībām. Šķērsošana turpinās, līdz ir šķērsots viss koks.

Laika sarežģītības analīze

Rekursijas koki palīdz analizēt rekursīvo algoritmu laika sarežģītību. Izpētot koka struktūru, varam noteikt veikto rekursīvo zvanu skaitu un paveikto darbu katrā līmenī. Šī analīze palīdz izprast algoritma kopējo efektivitāti un identificēt visas iespējamās neefektivitātes vai optimizācijas iespējas.

Ievads

• Padomājiet par programmu, kas nosaka skaitļa faktoriālu. Šī funkcija izmanto skaitli N kā ievadi un kā rezultātā atgriež N faktoriālu. Šīs funkcijas pseidokods būs līdzīgs

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• Rekursijas piemērs ir iepriekš minētā funkcija. Mēs izsaucam funkciju, lai noteiktu skaitļa faktoriālu. Pēc tam, ņemot vērā mazāku tā paša skaitļa vērtību, šī funkcija izsauc sevi. Tas turpinās, līdz sasniedzam pamata gadījumu, kurā vairs nav funkciju izsaukumu.
• Rekursija ir paņēmiens sarežģītu problēmu risināšanai, ja rezultāts ir atkarīgs no vienas un tās pašas problēmas mazāku gadījumu rezultātiem.
• Ja mēs domājam par funkcijām, tiek uzskatīts, ka funkcija ir rekursīva, ja tā turpina sevi izsaukt, līdz sasniedz bāzes gadījumu.
• Jebkurai rekursīvai funkcijai ir divi galvenie komponenti: bāzes gadījums un rekursīvais solis. Mēs pārtraucam pāriet uz rekursīvo fāzi, kad esam sasnieguši pamata gadījumu. Lai novērstu nebeidzamu atkārtošanos, pamatgadījumi ir pareizi jādefinē, un tiem ir izšķiroša nozīme. Bezgalīgas rekursijas definīcija ir rekursija, kas nekad nesasniedz bāzes gadījumu. Ja programma nekad nesasniedz bāzes gadījumu, steka pārpilde turpinās notikt.

Rekursijas veidi

Vispārīgi runājot, ir divi dažādi rekursijas veidi:

• Lineārā rekursija
• Koku rekursija
• Lineārā rekursija

Lineārā rekursija

• Tiek uzskatīts, ka funkcija, kas izsauc sevi tikai vienu reizi katrā izpildes reizē, ir lineāri rekursīva. Jauka lineārās rekursijas ilustrācija ir faktoriālā funkcija. Nosaukums “lineārā rekursija” attiecas uz faktu, ka lineāri rekursīvas funkcijas izpildei nepieciešams lineārs laiks.
• Apskatiet zemāk esošo pseidokodu:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Ja skatāmies uz funkciju doSomething(n), tā pieņem parametru ar nosaukumu n un veic dažus aprēķinus, pirms vēlreiz izsauc to pašu procedūru, bet ar zemākām vērtībām.
• Kad metode doSomething() tiek izsaukta ar argumenta vērtību n, pieņemsim, ka T(n) ir kopējais laiks, kas nepieciešams aprēķina pabeigšanai. Šim nolūkam mēs varam arī formulēt atkārtošanās sakarību, T(n) = T(n-1) + K. K šeit kalpo kā konstante. Konstante K ir iekļauta, jo funkcijai ir nepieciešams laiks, lai piešķirtu vai atdalītu atmiņu mainīgajam vai veiktu matemātisko darbību. Mēs izmantojam K, lai definētu laiku, jo tas ir tik īss un nenozīmīgs.
• Šīs rekursīvās programmas laika sarežģītību var vienkārši aprēķināt, jo sliktākajā gadījumā metode doSomething () tiek izsaukta n reizes. Formāli runājot, funkcijas laika sarežģītība ir O(N).

Koku rekursija

• Ja rekursīvajā gadījumā veicat rekursīvu zvanu vairāk nekā vienu reizi, to sauc par koka rekursiju. Efektīvs Tree rekursijas piemērs ir fibonači secība. Koku rekursīvās funkcijas darbojas eksponenciālā laikā; tie nav lineāri savā laika sarežģītībā.
• Apskatiet tālāk redzamo pseidokodu,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Vienīgā atšķirība starp šo kodu un iepriekšējo ir tā, ka šis veic vēl vienu izsaukumu tai pašai funkcijai ar mazāku n vērtību.
• Uzliksim T(n) = T(n-1) + T(n-2) + k kā šīs funkcijas atkārtošanās sakarību. K atkal kalpo kā konstante.
• Ja tiek veikts vairāk nekā viens vienas funkcijas izsaukums ar mazākām vērtībām, šāda veida rekursiju sauc par koka rekursiju. Tagad intriģējošs aspekts ir šāds: cik laikietilpīga ir šī funkcija?
• Veiciet minējumu, pamatojoties uz tālāk redzamo rekursijas koku par to pašu funkciju.
  
• Jums var šķist, ka ir grūti novērtēt laika sarežģītību, tieši aplūkojot rekursīvo funkciju, it īpaši, ja tā ir koka rekursija. Rekursijas koka metode ir viena no vairākām metodēm šādu funkciju laika sarežģītības aprēķināšanai. Izpētīsim to sīkāk.

Kas ir rekursijas koka metode?

• Atkārtošanās attiecības, piemēram, T(N) = T(N/2) + N vai divas, kuras mēs aplūkojām iepriekš rekursijas veidu sadaļā, tiek atrisinātas, izmantojot rekursijas koka pieeju. Šajās attiecībās, kas atkārtojas, bieži tiek izmantota “skaldi un valdi” stratēģija, lai risinātu problēmas.
• Ir nepieciešams laiks, lai integrētu atbildes uz mazākajām apakšproblēmām, kas rodas, ja lielāka problēma tiek sadalīta mazākās apakšproblēmās.
• Atkārtošanās attiecība, piemēram, ir T(N) = 2 * T(N/2) + O(N) sapludināšanas kārtošanai. Laiks, kas nepieciešams, lai apvienotu atbildes uz divām apakšproblēmām ar kopējo lielumu T(N/2), ir O(N), kas attiecas arī uz ieviešanas līmeni.
• Piemēram, tā kā binārās meklēšanas atkārtošanās attiecība ir T(N) = T(N/2) + 1, mēs zinām, ka katra binārās meklēšanas iterācija rada meklēšanas telpu, kas tiek pārgriezta uz pusēm. Kad rezultāts ir noteikts, mēs izejam no funkcijas. Atkārtošanās relācijai ir pievienots +1, jo šī ir pastāvīga laika darbība.
• Jāņem vērā atkārtošanās sakarība T(n) = 2T(n/2) + Kn. Kn apzīmē laiku, kas nepieciešams, lai apvienotu n/2-dimensiju apakšproblēmu atbildes.
• Attēlosim iepriekšminētās atkārtošanās attiecības rekursijas koku.

Mēs varam izdarīt dažus secinājumus, pētot iepriekš minēto rekursijas koku, tostarp

1. Problēmas apjoms katrā līmenī ir vienīgais, kas ir svarīgs mezgla vērtības noteikšanai. Emisijas apjoms ir n 0. līmenī, n/2 1. līmenī, n/2 2. līmenī un tā tālāk.

2. Kopumā mēs definējam koka augstumu kā vienādu ar log (n), kur n ir emisijas lielums, un šī rekursijas koka augstums ir vienāds ar līmeņu skaitu kokā. Tā ir taisnība, jo, kā mēs tikko noskaidrojām, atkārtošanās attiecības izmanto problēmu risināšanai „skaldi un valdi” stratēģiju, un, lai no izdevuma lieluma n līdz 1. problēmas lielumam, vienkārši ir jāveic log (n) soļi.

• Apsveriet, piemēram, vērtību N = 16. Ja mums ir atļauts katrā solī dalīt N ar 2, cik soļu ir nepieciešams, lai iegūtu N = 1? Ņemot vērā, ka mēs katrā solī dalām ar divi, pareizā atbilde ir 4, kas ir log(16) bāzes 2 vērtība.

log(16) 2. bāze

log(2^4) 2. bāze

4 * log(2) bāze 2, jo log(a) bāze a = 1

string to itn

tātad, 4 * log(2) bāze 2 = 4

3. Katrā līmenī otrais atkārtošanās termins tiek uzskatīts par sakni.

Lai gan šīs stratēģijas nosaukumā parādās vārds “koks”, jums nav jābūt koku ekspertam, lai to saprastu.

Kā izmantot rekursijas koku, lai atrisinātu atkārtošanās attiecības?

Apakšproblēmas izmaksas rekursijas koka tehnikā ir laiks, kas nepieciešams apakšproblēmas atrisināšanai. Tāpēc, ja pamanāt ar rekursijas koku saistītu frāzi “izmaksas”, tā vienkārši norāda uz laiku, kas nepieciešams noteiktas apakšproblēmas risināšanai.

Izpratīsim visas šīs darbības ar dažiem piemēriem.

Piemērs

Apsveriet atkārtošanās saistību,

T(n) = 2T(n/2) + K

Risinājums

Dotā atkārtošanās attiecība parāda šādas īpašības,

Problēmas izmērs n ir sadalīts divās apakšproblēmās, kuru katra izmērs ir n/2. Šo apakšproblēmu risinājumu apvienošanas izmaksas ir K.

Katrs uzdevuma lielums n/2 ir sadalīts divās apakšproblēmās, katra ar izmēru n/4 un tā tālāk.

Pēdējā līmenī apakšproblēmas lielums tiks samazināts līdz 1. Citiem vārdiem sakot, mēs beidzot sasniedzam pamata gadījumu.

Izpildiet darbības, lai atrisinātu šo atkārtošanās saistību,

1. darbība: uzzīmējiet rekursijas koku

2. darbība: aprēķiniet koka augstumu

Tā kā mēs zinām, ka, nepārtraukti dalot skaitli ar 2, pienāk brīdis, kad šis skaitlis tiek samazināts līdz 1. Tāpat kā ar uzdevuma lielumu N, pieņemsim, ka pēc K dalīšanas ar 2 N kļūst vienāds ar 1, kas nozīmē, ( n/2^k) = 1

Šeit n / 2^k ir problēmas lielums pēdējā līmenī, un tas vienmēr ir vienāds ar 1.

Tagad mēs varam viegli aprēķināt k vērtību no iepriekš minētās izteiksmes, ņemot log() abās pusēs. Tālāk ir sniegts skaidrāks atvasinājums,

n = 2^k

pirmskaitlis Java

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n)/log(2)
• k = log(n) 2. bāze

Tātad koka augstums ir log (n) bāze 2.

3. darbība. Aprēķiniet izmaksas katrā līmenī

• Izmaksas 0. līmenī = K, tiek apvienotas divas apakšproblēmas.
• Izmaksas 1. līmenī = K + K = 2*K, divas apakšproblēmas tiek apvienotas divas reizes.
• Izmaksas 2. līmenī = K + K + K + K = 4*K, divas apakšproblēmas tiek apvienotas četras reizes. un tā tālāk....

4. darbība. Aprēķiniet mezglu skaitu katrā līmenī

Vispirms noteiksim mezglu skaitu pēdējā līmenī. No rekursijas koka mēs to varam secināt

• 0. līmenim ir 1 (2^0) mezgls
• 1. līmenim ir 2 (2^1) mezgli
• 2. līmenim ir 4 (2^2) mezgli
• 3. līmenim ir 8 (2^3) mezgli

Tātad līmeņa žurnālam (n) jābūt 2^ (log(n)) mezgliem, t.i., n mezgliem.

5. darbība. Apkopojiet visu līmeņu izmaksas

• Kopējās izmaksas var rakstīt kā
• Kopējās izmaksas = visu līmeņu izmaksas, izņemot pēdējo līmeni + pēdējā līmeņa izmaksas
• Kopējās izmaksas = 0. līmeņa izmaksas + 1. līmeņa izmaksas + 2. līmeņa izmaksas +.... + Līmeņa-log(n) izmaksas + Pēdējā līmeņa izmaksas

Pēdējā līmeņa izmaksas tiek aprēķinātas atsevišķi, jo tas ir bāzes gadījums un pēdējā līmenī apvienošana netiek veikta, tāpēc izmaksas, lai atrisinātu vienu problēmu šajā līmenī, ir noteikta nemainīga vērtība. Pieņemsim to kā O (1).

Ieliksim vērtības formulās,

• T(n) = K + 2*K + 4*K + .... + log(n)' reizes + 'O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) reizes)' + 'O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) reizes + O(n)

Ja uzmanīgi aplūkojat iepriekš minēto izteiksmi, tā veido ģeometrisku progresiju (a, ar, ar^2, ar^3 ...... bezgalīgs laiks). GP summu uzrāda S(N) = a / (r - 1). Šeit ir pirmais termins, un r ir kopējā attiecība.