Kas ir rekursija?
Procesu, kurā funkcija izsauc sevi tieši vai netieši, sauc par rekursiju, un atbilstošo funkciju sauc par rekursīvo funkciju. Izmantojot rekursīvo algoritmu, dažas problēmas var atrisināt diezgan vienkārši. Šādu problēmu piemēri ir Hanojas torņi (TOH) , Pasūtīšanas/iepriekšpasūtīšanas/Postorder Tree Traversals , Graph DFS utt. Rekursīvā funkcija atrisina noteiktu problēmu, izsaucot pašas kopiju un atrisinot mazākas sākotnējo problēmu apakšproblēmas. Pēc vajadzības var ģenerēt daudz vairāk rekursīvu zvanu. Ir svarīgi zināt, ka mums ir jānodrošina noteikts gadījums, lai pārtrauktu šo rekursijas procesu. Tātad mēs varam teikt, ka katru reizi, kad funkcija izsauc sevi ar vienkāršāku sākotnējās problēmas versiju.

Nepieciešamība pēc rekursijas

Rekursija ir pārsteidzošs paņēmiens, ar kura palīdzību mēs varam samazināt sava koda garumu un atvieglot lasīšanu un rakstīšanu. Tam ir noteiktas priekšrocības salīdzinājumā ar iterācijas paņēmienu, kas tiks apspriests vēlāk. Uzdevums, ko var definēt ar līdzīgu apakšuzdevumu, rekursija ir viens no labākajiem risinājumiem. Piemēram; Skaitļa faktoriāls.

Rekursijas īpašības:

• Vienas un tās pašas darbības vairākas reizes ar dažādām ievadēm.
• Katrā solī mēs izmēģinām mazākus ievades datus, lai problēmu mazinātu.
• Pamatnosacījums ir nepieciešams, lai apturētu rekursiju, pretējā gadījumā radīsies bezgalīga cilpa.

Algoritms: soļi

The algorithmic steps for implementing recursion in a function are as follows: Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.>

Matemātiskā interpretācija

Apskatīsim problēmu, ka programmētājam ir jānosaka pirmo n naturālo skaitļu summa, ir vairāki veidi, kā to izdarīt, bet vienkāršākā pieeja ir vienkārši saskaitīt skaitļus, sākot no 1 līdz n. Tātad funkcija vienkārši izskatās šādi,

pieeja(1) — vienkārši pievienošana pa vienam

f(n) = 1 + 2 + 3 +……..+ n

bet ir arī cita matemātiska pieeja, kā to attēlot,

pieeja(2) – rekursīvā pievienošana

f(n) = 1 n = 1

f(n) = n + f(n-1) n>1

Pastāv vienkārša atšķirība starp pieeju (1) un pieeju (2), un tā ir pieeja (2) funkcija f( ) pati tiek izsaukta funkcijas iekšienē, tāpēc šī parādība tiek nosaukta par rekursiju, un funkcija, kas satur rekursiju, tiek saukta par rekursīvo funkciju, beigās tas ir lielisks rīks programmētāju rokās, lai kodētu dažas problēmas daudz vienkāršāk un efektīvāk. veidā.

Kā rekursīvās funkcijas tiek saglabātas atmiņā?

Rekursija izmanto vairāk atmiņas, jo rekursīvā funkcija pievieno steku ar katru rekursīvo zvanu un saglabā vērtības līdz zvana beigām. Rekursīvā funkcija izmanto LIFO (LAST IN FIRST OUT) struktūru tāpat kā steka datu struktūru. steka-datu-struktūra/

Kāds ir rekursijas pamatnosacījums?
Rekursīvajā programmā tiek sniegts bāzes gadījuma risinājums un lielākās problēmas risinājums tiek izteikts mazāku uzdevumu izteiksmē.

int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }>

Iepriekš minētajā piemērā ir definēts pamatgadījums n <= 1, un skaitļa lielāko vērtību var atrisināt, konvertējot uz mazāku, līdz tiek sasniegts pamatgadījums.

Kā konkrēta problēma tiek atrisināta, izmantojot rekursiju?
Ideja ir attēlot problēmu vienas vai vairāku mazāku problēmu izteiksmē un pievienot vienu vai vairākus pamata nosacījumus, kas aptur rekursiju. Piemēram, mēs aprēķinām faktoriālu n, ja zinām (n-1) faktoriālu. Faktoriāla pamatgadījums būtu n = 0. Mēs atgriežam 1, ja n = 0.

Kāpēc rekursijā rodas Stack Overflow kļūda?
Ja bāzes gadījums nav sasniegts vai nav definēts, var rasties steka pārpildes problēma. Ņemsim piemēru, lai to saprastu.

int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }>

Ja tiek izsaukts fakts (10), tas izsauks faktu (9), faktu (8), faktu (7) un tā tālāk, bet skaitlis nekad nesasniegs 100. Tātad bāzes gadījums nav sasniegts. Ja šīs steka funkcijas izsmels atmiņu, tas izraisīs steka pārpildes kļūdu.

Kāda ir atšķirība starp tiešo un netiešo rekursiju?
Funkcijas jautrība tiek saukta par tiešu rekursīvu, ja tā to pašu funkciju sauc par fun. Funkciju fun sauc par netiešu rekursīvu, ja tā tieši vai netieši izsauc citu funkciju, piemēram, fun_new un fun_new izsauc fun. Atšķirība starp tiešo un netiešo rekursiju ir parādīta 1. tabulā.

 // An example of direct recursion void directRecFun() { // Some code.... directRecFun(); // Some code... } // An example of indirect recursion void indirectRecFun1() { // Some code... indirectRecFun2(); // Some code... } void indirectRecFun2() { // Some code... indirectRecFun1(); // Some code... }>

Kāda ir atšķirība starp astes un nesadalīto rekursiju?
Rekursīva funkcija ir astes rekursīva, ja rekursīvs izsaukums ir pēdējais, ko funkcija izpilda. Lūdzu, skatiet astes rekursijas raksts sīkākai informācijai.

Kā atmiņa tiek piešķirta dažādiem funkciju izsaukumiem rekursijā?
Kad jebkura funkcija tiek izsaukta no main(), tai stekā tiek piešķirta atmiņa. Rekursīvā funkcija izsauc sevi, atmiņa izsauktajai funkcijai tiek piešķirta papildus izsaucējai funkcijai piešķirtajai atmiņai, un katram funkcijas izsaukumam tiek izveidota atšķirīga vietējo mainīgo kopija. Kad ir sasniegts bāzes gadījums, funkcija atgriež savu vērtību funkcijai, kas to izsauc, un atmiņa tiek atdalīta, un process turpinās.
Ņemsim piemēru, kā darbojas rekursija, izmantojot vienkāršu funkciju.

CPP

>

>

Java

pārvērst virkni par datumu

>

>

Python3

>

>

C#

>

>

PHP

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > > // JavaScript program to demonstrate working of> // recursion> > function> printFun(test)> >{> >if> (test <1)> >return>;> >else> {> >document.write(test +>' '>);> >printFun(test - 1);>// statement 2> >document.write(test +>' '>);> >return>;> >}> >}> > // Driver code> >let test = 3;> >printFun(test);> > > 
 
 
 
 
    
 
>
 
    
 
>
 
  Izvade  
 
3 2 1 1 2 3>
 
  Laika sarežģītība: O(1) 
  Palīgtelpa: O(1)
 
Kad printFun (3) tiek izsaukts no main(), atmiņa tiek piešķirta printFun (3) un lokālā mainīgā pārbaude tiek inicializēta uz 3, un priekšraksts no 1 līdz 4 tiek nospiests stekā, kā parādīts zemāk esošajā diagrammā. Vispirms tiek izdrukāts '3'. 2. paziņojumā printFun (2) tiek izsaukts un tiek piešķirta atmiņa printFun (2) un lokālā mainīgā pārbaude tiek inicializēta uz 2, un priekšraksts no 1 līdz 4 tiek ievietots kaudzē. Līdzīgi, printFun (2) zvani printFun (1) un printFun (1) zvani printFun (0) . printFun (0) pāriet uz if paziņojumu un tas atgriežas printFun (1) . Pārējie paziņojumi par printFun (1) tiek izpildīti un tas atgriežas printFun (2) un tā tālāk. Izvadē tiek izdrukātas vērtības no 3 līdz 1 un pēc tam no 1 līdz 3. Atmiņas kaudze ir parādīta zemāk esošajā diagrammā.
 
 
 
  Rekursija VS iterācija  
 
 
 
 
  SR Nr.  
 
  Rekursija  
 
  Iterācija  
 
 
 
1)
 
Tiek pārtraukta, kad pamata gadījums kļūst patiess.
 
Izbeidzas, kad nosacījums kļūst nepatiess.
 
 
 
2)
 
Izmanto ar funkcijām.
 
Lieto ar cilpām.
 
 
 
3)
 
Katram rekursīvajam zvanam ir nepieciešama papildu vieta steka atmiņā.
 
Katrai iterācijai nav nepieciešama papildu vieta.
 
 
 
4)
 
Mazāks koda izmērs.
 
Lielāks koda izmērs.
 
 
 
 
Tagad apspriedīsim dažas praktiskas problēmas, kuras var atrisināt, izmantojot rekursiju, un sapratīsim tās darbības pamatprincipus. Lai iegūtu pamata izpratni, lūdzu, izlasiet šos rakstus. 
Pamata izpratne par rekursiju. 
  1. problēma: Uzrakstiet programmu un atkārtošanās relāciju, lai atrastu n Fibonači virkni, kur n>2 . 
  Matemātiskais vienādojums:  
 
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>
 
  Atkārtošanās saistība:  
 
T(n) = T(n-1) + T(n-2) + O(1)>
 
  Rekursīvā programma:  
 
 Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>
 
  Īstenošana:  
 
C++
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C++ code to implement Fibonacci series> #include> using> namespace> std;> > // Function for fibonacci> > int> fib(>int> n)> > > // Driver Code> int> main()> {> >// Initialize variable n.> >int> n = 5;> >cout<<>'Fibonacci series of 5 numbers is: '>;> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i   {   cout<' ';   }   return 0;  }>
 
 
 
 
    
 
>
 
    
 
>
 
 
C
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C code to implement Fibonacci series> #include> > // Function for fibonacci> int> fib(>int> n)> > >// Stop condition> >if> (n == 0)> >return> 0;> > >// Stop condition> >if> (n == 1> > // Driver Code> int> main()> {> >// Initialize variable n.> >int> n = 5;> >printf>(>'Fibonacci series '> >'of %d numbers is: '>,> >n);> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i   printf('%d ', fib(i));   }   return 0;  }>
 
 
 
 
    
 
>
 
    
 
>
 
 
Java
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // Java code to implement Fibonacci series> import> java.util.*;> > class> GFG> {> > // Function for fibonacci> static> int> fib(>int> n)> > > // Driver Code> public> static> void> main(String []args)> {> > >// Initialize variable n.> >int> n =>5>;> >System.out.print(>'Fibonacci series of 5 numbers is: '>);> > >// for loop to print the fibonacci series.> >for> (>int> i =>0>; i   {   System.out.print(fib(i)+' ');   }  }  }    // This code is contributed by rutvik_56.>
 
 
 
 
virknes sadalīšana c++
    
 
>
 
    
 
>
 
 
Python3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Python code to implement Fibonacci series> > # Function for fibonacci> def> fib(n):> > ># Stop condition> >if> (n>=>=> 0>):> >return> 0> > ># Stop condition> >if> (n>=>=> 1> or> n>=>=> 2>):> >return> 1> > ># Recursion function> >else>:> >return> (fib(n>-> 1>)>+> fib(n>-> 2>))> > > # Driver Code> > # Initialize variable n.> n>=> 5>;> print>(>'Fibonacci series of 5 numbers is :'>,end>=>' '>)> > # for loop to print the fibonacci series.> for> i>in> range>(>0>,n):> >print>(fib(i),end>=>' '>)> 
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 using> System;> > public> class> GFG> {> > >// Function for fibonacci> >static> int> fib(>int> n)> > n == 2)> >return> 1;> > >// Recursion function> >else> >return> (fib(n - 1) + fib(n - 2));> >> > >// Driver Code> >static> public> void> Main ()> >{> > >// Initialize variable n.> >int> n = 5;> >Console.Write(>'Fibonacci series of 5 numbers is: '>);> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i   {   Console.Write(fib(i) + ' ');   }   }  }    // This code is contributed by avanitrachhadiya2155>
 
 
 
 
    
 
>
 
    
 
>
 
 
Javascript
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // JavaScript code to implement Fibonacci series> > // Function for fibonacci> function> fib(n)>  n == 2)> >return> 1;> >// Recursion function> >else> >return> fib(n-1) + fib(n-2);> > > // Initialize variable n.> let n = 5;> > document.write(>'Fibonacci series of 5 numbers is: '>);> > // for loop to print the fibonacci series.> for>(let i = 0; i  {   document.write(fib(i) + ' ');  }>
 
 
 
 
    
 
>
 
    
 
>
 
  Izvade  
 
Fibonacci series of 5 numbers is: 0 1 1 2 3>
 
  Laika sarežģītība: O(2n) 
  Palīgtelpa: O(n)
 
Šeit ir 5. ievades rekursīvais koks, kas parāda skaidru priekšstatu par to, kā lielu problēmu var atrisināt mazākās. 
fib(n) ir Fibonači funkcija. Dotās programmas laika sarežģītība var būt atkarīga no funkcijas izsaukuma.
  
 
fib(n) -> līmeņa CBT (UB) -> 2^n-1 mezgli -> 2^n funkcijas izsaukums -> 2^n*O(1) -> T(n) = O(2^n)
 
 
Labākajam gadījumam.
 
T(n) = ?(2^n2)>
 
  Darbojas:  
 
 
 
  2. problēma: Uzrakstiet programmu un atkārtošanās relāciju, lai atrastu n koeficientu, kur n>2 . 
  Matemātiskais vienādojums:  
 
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>
 
  Atkārtošanās saistība:  
 
T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>
 
  Rekursīvā programma:   
  Ievade: n = 5 
  Izvade:   
Faktoriāls no 5 ir: 120 
  Īstenošana:  
 
C++
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C++ code to implement factorial> #include> using> namespace> std;> > // Factorial function> int> f(>int> n)>  n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n * f(n - 1);> > > // Driver code> int> main()> {> >int> n = 5;> >cout<<>'factorial of '><' is: '<  return 0;  }>
 
 
 
 
    
 
>
 
    
 
>
 
 
C
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C code to implement factorial> #include> > // Factorial function> int> f(>int> n)> > >// Stop condition> >if> (n == 0> > // Driver code> int> main()> {> >int> n = 5;> >printf>(>'factorial of %d is: %d'>, n, f(n));> >return> 0;> }> 
 
 
 
 
    
kā injicēt izspēles abstraktu klasi
 
>
 
    
 
>
 
 
Java
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // Java code to implement factorial> public> class> GFG> {> > >// Factorial function> >static> int> f(>int> n)> >> > >// Driver code> >public> static> void> main(String[] args)> >{> >int> n =>5>;> >System.out.println(>'factorial of '> + n +>' is: '> + f(n));> >}> }> > // This code is contributed by divyesh072019.> 
 
 
 
 
    
 
>
 
    
 
>
 
 
Python3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Python3 code to implement factorial> > # Factorial function> def> f(n):> > ># Stop condition> >if> (n>=>=> 0> or> n>=>=> 1>):> >return> 1>;> > ># Recursive condition> >else>:> >return> n>*> f(n>-> 1>);> > > # Driver code> if> __name__>=>=>'__main__'>:> > >n>=> 5>;> >print>(>'factorial of'>,n,>'is:'>,f(n))> > ># This code is contributed by pratham76.> 
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C# code to implement factorial> using> System;> class> GFG {> > >// Factorial function> >static> int> f(>int> n)> > n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n * f(n - 1);> >> > >// Driver code> >static> void> Main()> >{> >int> n = 5;> >Console.WriteLine(>'factorial of '> + n +>' is: '> + f(n));> >}> }> > // This code is contributed by divyeshrabadiya07.> 
 
 
 
 
    
 
>
 
    
 
>
 
 
Javascript
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // JavaScript code to implement factorial> > // Factorial function> function> f(n)>  n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n*f(n-1);> > > // Initialize variable n.> let n = 5;> document.write(>'factorial of '>+ n +>' is: '> + f(n));> > // This code is contributed by probinsah.> > 
 
 
 
 
    
 
>
 
    
 
>
 
  Izvade  
 
factorial of 5 is: 120>
 
  Laika sarežģītība: O(n) 
  Palīgtelpa: O(n)
 
  Darbojas:   
 
  
Faktoriālās rekursijas funkcijas diagramma lietotāja ievadei 5.
 
Piemērs: reāli rekursijas pielietojumi reālās problēmās
 
Rekursija ir spēcīgs paņēmiens, kam ir daudz pielietojumu datorzinātnēs un programmēšanā. Šeit ir daži no izplatītākajiem rekursijas lietojumiem:
 
Koku un diagrammu pārvietošana: rekursiju bieži izmanto, lai šķērsotu un meklētu datu struktūras, piemēram, kokus un grafikus. Rekursīvos algoritmus var izmantot, lai sistemātiski izpētītu visus koka vai grafa mezglus vai virsotnes. Kārtošanas algoritmi : rekursīvie algoritmi tiek izmantoti arī kārtošanas algoritmos, piemēram, ātrā kārtošanā un sapludināšanas kārtošanā. Šie algoritmi izmanto rekursiju, lai sadalītu datus mazākos apakšslāņos vai apakšsarakstos, kārtotu tos un pēc tam atkal apvienotu. Dali un valdi algoritmi : daudzi algoritmi, kas izmanto sadali un valdi pieeju, piemēram, binārais meklēšanas algoritms, izmanto rekursiju, lai sadalītu problēmu mazākās apakšproblēmās. Fraktāļu ģenerēšana: Fraktāļu formas un modeļus var ģenerēt, izmantojot rekursīvos algoritmus. Piemēram, Mandelbrota kopa tiek ģenerēta, kompleksiem skaitļiem atkārtoti piemērojot rekursīvu formulu. Atkāpšanās algoritmi : atkāpšanās algoritmi tiek izmantoti, lai atrisinātu problēmas, kas saistītas ar lēmumu secības pieņemšanu, kur katrs lēmums ir atkarīgs no iepriekšējiem. Šos algoritmus var ieviest, izmantojot rekursiju, lai izpētītu visus iespējamos ceļus un atgrieztos, ja risinājums netiek atrasts. Memoization: Memoization ir paņēmiens, kas ietver dārgu funkciju izsaukumu rezultātu saglabāšanu un kešatmiņā saglabātā rezultāta atgriešanu, kad atkārtojas tās pašas ievades. Memoizāciju var ieviest, izmantojot rekursīvas funkcijas, lai aprēķinātu un saglabātu apakšproblēmu rezultātus.
 
Šie ir tikai daži piemēri no daudzajiem rekursijas pielietojumiem datorzinātnēs un programmēšanā. Rekursija ir daudzpusīgs un jaudīgs rīks, ko var izmantot dažādu veidu problēmu risināšanai.
 
Paskaidrojums: viens reāls rekursijas piemērs:
 
Rekursija ir programmēšanas paņēmiens, kas ietver pašas funkcijas izsaukšanu. Tas var būt spēcīgs rīks sarežģītu problēmu risināšanai, taču tas prasa arī rūpīgu ieviešanu, lai izvairītos no bezgalīgām cilpām un steku pārpildīšanas.
 
Šeit ir piemērs rekursijas ieviešanai Python:
 
C++
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 #include> using> namespace> std;> int> factorial(>int> n)> {> > >// Base case: if n is 0 or 1, return 1> >if> (n == 0 || n == 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> }> > int> main()> {> > >// Call the factorial function and print the result> >int> result = factorial(5);> >cout << result 
 
 
 
 
    
 
>
 
    
 
>
 
 
Java
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 import> java.util.*;> > class> Main {> >public> static> int> factorial(>int> n)> >{> >// Base case: if n is 0 or 1, return 1> >if> (n ==>0> || n ==>1>) {> >return> 1>;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n ->1>);> >}> >}> > >public> static> void> main(String[] args)> >{> >// Call the factorial function and print the result> >int> result = factorial(>5>);> >System.out.println(result);>// Output: 120> >}> }> 
 
 
 
 
    
 
>
 
    
 
>
 
 
Python3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 def> factorial(n):> ># Base case: if n is 0 or 1, return 1> >if> n>=>=> 0> or> n>=>=> 1>:> >return> 1> > ># Recursive case: if n is greater than 1, call the function with n-1 and multiply by n> >else>:> >return> n>*> factorial(n>->1>)> > # Call the factorial function and print the result> result>=> factorial(>5>)> print>(result)># Output: 120> 
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 using> System;> > class> MainClass {> >public> static> int> factorial(>int> n)> >{> >// Base case: if n is 0 or 1, return 1> >if> (n == 0 || n == 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> >}> > >public> static> void> Main (>string>[] args) {> >// Call the factorial function and print the result> >int> result = factorial(5);> >Console.WriteLine(result);>// Output: 120> >}> }> 
 
 
 
 
    
 
>
 
savienojiet datubāzi java
    
 
>
 
 
Javascript
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 function> factorial(n) {> >// Base case: if n is 0 or 1, return 1> >if> (n === 0 || n === 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1, call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> }> > // Call the factorial function and print the result> const result = factorial(5);> console.log(result);>// Output: 120> 
 
 
 
 
    
 
>
 
    
 
>
 
  Izvade  
 
120>
 
Šajā piemērā mēs definējam funkciju, ko sauc par faktoriālu, kas kā ievadi izmanto veselu skaitli n. Funkcija izmanto rekursiju, lai aprēķinātu n faktoriālu (t.i., visu pozitīvo veselo skaitļu reizinājumu līdz n).
 
Faktoriālā funkcija vispirms pārbauda, ​​vai n ir 0 vai 1, kas ir pamata gadījumi. Ja n ir 0 vai 1, funkcija atgriež 1, jo 0! un 1! abi ir 1.
 
Ja n ir lielāks par 1, funkcija ievada rekursīvo gadījumu. Tas sevi sauc ar n-1 kā argumentu un reizina rezultātu ar n. Tas aprēķina n! rekursīvi aprēķinot (n-1)!.
 
Ir svarīgi atzīmēt, ka rekursija var būt neefektīva un izraisīt steku pārplūdi, ja to neizmanto uzmanīgi. Katrs funkcijas izsaukums pievieno jaunu kadru izsaukuma stekam, kā rezultātā steka var kļūt pārāk liela, ja rekursija ir pārāk dziļa. Turklāt rekursija var padarīt kodu grūtāk saprotamu un atkļūdojamu, jo ir jādomā par vairākiem funkciju izsaukumu līmeņiem.
 
Tomēr rekursija var būt arī spēcīgs instruments sarežģītu problēmu risināšanai, jo īpaši tām, kas ietver problēmas sadalīšanu mazākās apakšproblēmās. Pareizi lietojot, rekursija var padarīt kodu elegantāku un vieglāk lasāmu.
 
  Kādi ir rekursīvās programmēšanas trūkumi salīdzinājumā ar iteratīvo programmēšanu?   
Ņemiet vērā, ka gan rekursīvajām, gan iteratīvajām programmām ir vienādas problēmu risināšanas spējas, t.i., katru rekursīvo programmu var uzrakstīt iteratīvi un arī otrādi. Rekursīvajai programmai ir lielākas vietas prasības nekā iteratīvajai programmai, jo visas funkcijas paliks kaudzē, līdz tiek sasniegts bāzes gadījums. Tam ir arī lielākas laika prasības funkciju izsaukumu un atdeves dēļ.
 
Turklāt mazākā koda garuma dēļ kodus ir grūti saprast, un tāpēc koda rakstīšanas laikā ir jāievēro īpaša piesardzība. Ja rekursīvie zvani netiek pareizi pārbaudīti, datoram var pietrūkt atmiņas.
 
  Kādas ir rekursīvās programmēšanas priekšrocības salīdzinājumā ar iteratīvo programmēšanu?   
Rekursija nodrošina tīru un vienkāršu veidu, kā rakstīt kodu. Dažas problēmas pēc būtības ir rekursīvas, piemēram, koku šķērsošana, Hanojas tornis uc Šādām problēmām ieteicams rakstīt rekursīvu kodu. Šādus kodus varam rakstīt arī iteratīvi ar steka datu struktūras palīdzību. Piemēram, skatiet Inorder Tree Traversal bez rekursijas, Iteratīvais Hanojas tornis.
 
  Rekursijas kopsavilkums:  
 
 
Rekursijā ir divu veidu gadījumi, t.i., rekursīvs gadījums un pamata gadījums.
 
Bāzes reģistrs tiek izmantots, lai pārtrauktu rekursīvo funkciju, kad gadījums izrādās patiess.
 
Katrs rekursīvais izsaukums veido jaunu šīs metodes kopiju steka atmiņā.
 
Bezgalīgas rekursijas rezultātā var beigties steka atmiņas apjoms.
 
Rekursīvo algoritmu piemēri: sapludināšanas kārtošana, ātrā kārtošana, Hanojas tornis, Fibonači sērija, faktoriāla problēma utt.
 
 
  Uz rezultātiem balstītas prakses problēmas iesācējiem:   
Prakses jautājumi par rekursiju | 1. komplekts 
Prakses jautājumi par rekursiju | 2. komplekts 
Prakses jautājumi par rekursiju | 3. komplekts 
Prakses jautājumi par rekursiju | 4. komplekts 
Prakses jautājumi par rekursiju | 5. komplekts 
Prakses jautājumi par rekursiju | 6. komplekts 
Prakses jautājumi par rekursiju | 7. komplekts 
   Viktorīna par rekursiju    
   Rekursijas kodēšanas prakse:    
   Visi raksti par rekursiju    
Rekursīvas prakses problēmas ar risinājumiem