Kas ir Rekursija? Kam tā paredzēta? Kā to izmantot?

Iepriekšējā rakstā jūs uzzinājāt par “Skaldi un valdi” paradigmu. Šajā rakstā turpināsim rakstu sēriju un jūs uzzināsiet par Recursions , jeb Rekursijām un to, kā ieviest prasības rekursīvajam risinājumam.

Viens no jebkuras valodas pamatprincipiem ir tās spēja veikt cilpas Loops. Cilpas ļauj mums veikt darbības atkārtoti, līdz tiek sasniegts vēlamais rezultāts.

WHILE x < y

DO

Atšķirībā no cilvēkiem, datori nekad nenogurst atkārtoti veikt vienu un to pašu ikdienišķu uzdevumu. Alternatīva pieeja problēmas risināšanai, nevis cilpa, ir rekursija. Prakse, kad funkcijas pašas sevi izsauc, tiek saukta par rekursiju un šajā rakstā mēs uz to fokusēsimies.

Rekursija ir tad, kad funkcija atkārtoti izsauc sevi ar mazāku problēmas gadījumu, līdz tiek izpildīts kāds izejas nosacījums. Kas nepieciešams rekursijai? Rekursīva risinājuma ieviešanai ir trīs prasības, proti,

• bāzes gadījums – Base case,
• dilstošā struktūra – Diminishing structure 
• rekursīvais izsaukums – Recursive call.

Apskatīsim piemēru, kas attiecas uz bināro, lai labāk ilustrētu šīs trīs prasības. Apsveriet izaicinājumu, kurā jums tiek uzdots atrast skaitļa eksponentu. Atcerieties, ka skaitļa eksponenta aprēķināšana ir, lai noteiktu, cik daudz potenciālo permutāciju var iegūt no tā. Tas tika apspriests, demonstrējot, kā bināro var izmantot, lai attēlotu rakstzīmju diapazonu. Bāzes gadījums nodrošina, ka funkcija neturpinās sevi izsaukt un galu galā beidzas.

exponent(x, n)

If n == 0:

return 1

ELSE

return (x* exponent(x, n-1))

• 1. rindiņa iezīmē funkciju, kas izmanto divus argumentus — x un n.
• Bāzes gadījums ir, ja n ir 0. Šajā gadījumā programma tiks pārtraukta.
• 4. rinda “ELSE” ir nosacījuma paziņojuma otrā daļa. Ja galapunkts nav sasniegts, vēlreiz izsauciet funkciju ar samazinātu struktūru.

Šajā gadījumā mērķis ir reizināt x ar n, lai atrastu kopējo potenciālo stāvokļu skaitu, kas varētu pastāvēt binārajam skaitlim. Ievades vērtības samazināšana ir tikpat svarīga kā bāzes gadījuma noteikšana. Tādā veidā funkcija galu galā sasniegs pamata gadījumu un pārstās sevi izsaukt.

• Trešais rekursīvās funkcijas komponents ir iekļaut izsaukumu sev. Tas notiek 5. rindā, kur eksponents pieņem samazināto struktūru (return (x* exponent(x, n-1))).

Var teikt, ka struktūra ir samazinājusies, jo izmērs ir samazināts no viena kodola uz otru. Katru reizi, kad funkcija tiek izsaukta, izsaukuma stekā Call Stack tiek izveidots jauns gadījums. Iepriekš minētās funkcijas izsaukšana ar x ir vienāda ar 2 un n ir vienāda ar 3, tiks izveidotas trīs instances un ievietotas Call Stack.

Tas palielina skaitļošanas izmaksas, jo funkcijas izsaukšanai ir nepieciešami resursi. Tomēr katra rezultāta aprēķins tiks saglabāts Call Stack. Tas var būt noderīgi, aprēķinot hierarhiskas problēmas vai problēmas, kurās var gūt labumu, zinot, kuras darbības noveda pie noteikta rezultāta, piemēram, šķērsojot grafiku. Izpētīsim rekursijas izmantošanas piemēru.

Jau pētījām rakstā bināro meklēšanu. Binārā meklēšanas funkcija pieņems saraksta argumentu un mērķa vērtību.

Pirmkārt, saraksta viduspunkts tiek salīdzināts ar elementiem, lai noteiktu, kuru saraksta pusi pārbaudīt. Šo procesu atkārto, līdz tiek atrasts mērķa elements vai tiek uzskatīts, ka tā nav. Varat apsvērt šīs problēmas risināšanu, izmantojot cilpu vai rekursīvi.

Rekursijas ievade būtu saraksts un meklēšanas elements, un rekursīvā funkcija izsauks sevi, līdz tiks sasniegts mērķa galapunkts. Kāpēc tad izmantot rekursiju, ja derēs vienkārša cilpa? Dažas problēmas ir piemērotas rekursīviem izsaukumiem.

Apsveriet iespēju aprēķināt noteikta skaitļa Fibonači. Fibonači ir skaitļu virkne, kurā pirmie divi skaitļi ir nulle, un viens un katrs otrais skaitlis ir iepriekšējo divu kopas skaitļu summa. Rezultāta aprēķināšana ietver skaitļa nodošanu, izvades aprēķināšanu, skaitļa maiņu, pēc tam funkcijas atkārtotu izsaukšanu ar jaunu vesela skaitļa ievadi.

function fibonači(skaitlis) {
    if (skaitlis < 2) {
      return skaitlis;
    } else {
      return fibonači(skaitlis - 1) + fibonači(skaitlis - 2);
    }
  }