Kas yra Rekursija?
Procesas, kurio metu funkcija išsikviečia save tiesiogiai arba netiesiogiai, vadinamas rekursija, o atitinkama funkcija vadinama rekursine funkcija. Naudojant rekursinį algoritmą, tam tikras problemas galima išspręsti gana lengvai. Tokių problemų pavyzdžiai yra Hanojaus bokštai (TOH) , Inorder/Preorder/Postorder Tree Traversals , DFS of Graph ir tt Rekursyvinė funkcija išsprendžia tam tikrą problemą, iškviesdama savo kopiją ir išspręsdama mažesnes pradinių uždavinių dalis. Kai reikia, galima sugeneruoti daug daugiau rekursinių skambučių. Svarbu žinoti, kad turėtume pateikti tam tikrą atvejį, kad užbaigtume šį rekursijos procesą. Taigi galime pasakyti, kad kiekvieną kartą, kai funkcija išsikviečia paprastesnę pradinės problemos versiją.

Rekursijos poreikis

Rekursija yra nuostabi technika, kurios pagalba galime sumažinti savo kodo ilgį ir palengvinti skaitymą bei rašymą. Ji turi tam tikrų pranašumų, palyginti su iteracijos technika, kuri bus aptarta vėliau. Užduotis, kurią galima apibrėžti panašia antrine užduotimi, rekursija yra vienas geriausių sprendimų jai. Pavyzdžiui; Skaičiaus faktorialas.

Rekursijos savybės:

• Tų pačių operacijų atlikimas kelis kartus su skirtingais įvestimis.
• Kiekviename žingsnyje stengiamės naudoti mažesnes įvestis, kad problema būtų mažesnė.
• Norint sustabdyti rekursiją, reikalinga pagrindinė sąlyga, kitaip atsiras begalinis ciklas.

Algoritmas: žingsniai

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.>

Matematinis aiškinimas

Panagrinėkime problemą, kurią programuotojas turi nustatyti pirmųjų n natūraliųjų skaičių sumą, yra keletas būdų tai padaryti, tačiau paprasčiausias būdas yra tiesiog sudėti skaičius, pradedant nuo 1 iki n. Taigi funkcija tiesiog atrodo taip,

metodas(1) – tiesiog pridėkite po vieną

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

bet yra ir kitas matematinis požiūris, kaip tai pavaizduoti,

metodas(2) – Rekursyvus pridėjimas

f(n) = 1 n = 1

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

Yra paprastas skirtumas tarp metodo (1) ir metodo (2), ir tai yra požiūris (2) funkcija f( ) pati yra vadinama funkcijos viduje, todėl šis reiškinys vadinamas rekursija, o funkcija, kurioje yra rekursija, vadinama rekursine funkcija, galų gale, tai yra puikus įrankis programuotojų rankose, kad būtų lengviau ir efektyviau koduoti kai kurias problemas. būdu.

Kaip atmintyje saugomos rekursinės funkcijos?

Rekursija naudoja daugiau atminties, nes rekursinė funkcija papildo krūvą su kiekvienu rekursiniu skambučiu ir išlaiko reikšmes, kol skambutis baigsis. Rekursyvinė funkcija naudoja LIFO (LAST IN FIRST OUT) struktūrą, kaip ir kamino duomenų struktūra. stack-data-structure/

Kokia yra bazinė rekursijos sąlyga?
Rekursyvinėje programoje pateikiamas bazinio atvejo sprendimas, o didesnės problemos sprendimas išreiškiamas mažesniais uždaviniais.

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

Aukščiau pateiktame pavyzdyje apibrėžiamas pagrindinis n <= 1 atvejis, o didesnė skaičiaus reikšmė gali būti išspręsta konvertuojant į mažesnę, kol bus pasiektas pagrindinis atvejis.

Kaip konkreti problema išsprendžiama naudojant rekursiją?
Idėja yra pateikti problemą kaip vieną ar daugiau mažesnių problemų ir pridėti vieną ar daugiau bazinių sąlygų, kurios sustabdo rekursiją. Pavyzdžiui, apskaičiuojame faktorialą n, jei žinome (n-1) faktorialą. Bazinis faktorialo atvejis būtų n = 0. Grąžiname 1, kai n = 0.

Kodėl rekursijos metu atsiranda Stack Overflow klaida?
Jei bazinis atvejis nepasiekiamas arba neapibrėžtas, gali kilti dėklo perpildymo problema. Paimkime pavyzdį, kad tai suprastume.

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

Jei iškviečiamas faktas (10), jis iškviečia faktą (9), faktą (8), faktą (7) ir tt, bet skaičius niekada nepasieks 100. Taigi bazinis atvejis nepasiektas. Jei dėl šių dėklo funkcijų išeikvojama atmintis, tai sukels dėklo perpildymo klaidą.

Kuo skiriasi tiesioginė ir netiesioginė rekursija?
Funkcijos fun vadinama tiesiogine rekursine, jei ji vadina tą pačią funkciją fun. Funkcija fun vadinama netiesiogine rekursine, jei ji tiesiogiai arba netiesiogiai iškviečia kitą funkciją, tarkim, fun_new ir fun_new. Skirtumas tarp tiesioginės ir netiesioginės rekursijos parodytas 1 lentelėje.

 // 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... }>

Kuo skiriasi uodeginė ir neuodeginė rekursija?
Rekursyvinė funkcija yra tail rekursinė, kai rekursinis skambutis yra paskutinis funkcijos vykdomas dalykas. Prašome kreiptis uodegos rekursijos straipsnis dėl detalių.

Kaip atmintis paskirstoma skirtingiems funkcijų iškvietimams rekursijos metu?
Kai kuri nors funkcija iškviečiama iš main(), atmintis jai priskiriama krūvoje. Rekursyvinė funkcija iškviečia save, iškviestos funkcijos atmintis paskirstoma virš atminties, skirtos iškvietimo funkcijai, ir kiekvienam funkcijos iškvietimui sukuriama skirtinga vietinių kintamųjų kopija. Pasiekus bazinį atvejį, funkcija grąžina savo reikšmę funkcijai, kuri ją iškviečia, atmintis atimama ir procesas tęsiasi.
Paimkime pavyzdį, kaip veikia rekursija, paimdami paprastą funkciją.

CPP

>

>

Java

java spalvos

>

>

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);> > > 
 
 
 
 
    
 
>
 
    
 
>
 
  Išvestis  
 
3 2 1 1 2 3>
 
  Laiko sudėtingumas: O(1) 
  Pagalbinė erdvė: O(1)
 
Kada printFun (3) iškviečiamas iš main(), atmintis yra skirta printFun (3) ir vietinio kintamojo testas inicijuojamas į 3, o sakinys nuo 1 iki 4 perkeliamas į krūvą, kaip parodyta toliau pateiktoje diagramoje. Pirmiausia išspausdinama „3“. 2 pareiškime printFun (2) iškviečiama ir paskirstoma atmintis printFun (2) ir vietinio kintamojo testas inicijuojamas į 2, o teiginys nuo 1 iki 4 įstumiamas į krūvą. Panašiai, printFun (2) skambučių printFun (1) ir printFun (1) skambučių printFun (0) . printFun (0) eina į if teiginį ir grįžta į printFun (1) . Likę pareiškimai apie printFun (1) yra vykdomi ir grįžta į printFun (2) ir taip toliau. Išvestyje atspausdinamos reikšmės nuo 3 iki 1, o tada – nuo ​​1 iki 3. Atminties krūva parodyta žemiau esančioje diagramoje.
 
 
 
  Rekursija VS iteracija  
 
 
 
 
  SR Nr.  
 
  Rekursija  
 
  Iteracija  
 
 
 
1)
 
Nutraukiamas, kai pagrindinis atvejis tampa teisingas.
 
Nutrūksta, kai sąlyga tampa klaidinga.
 
 
 
2)
 
Naudojamas su funkcijomis.
 
Naudojamas su kilpomis.
 
 
 
3)
 
Kiekvienam rekursiniam skambučiui reikia papildomos vietos kamino atmintyje.
 
Kiekvienai iteracijai nereikia papildomos vietos.
 
 
 
4)
 
Mažesnis kodo dydis.
 
Didesnis kodo dydis.
 
 
 
 
Dabar aptarkime keletą praktinių problemų, kurias galima išspręsti naudojant rekursiją, ir suprasime pagrindinį jos veikimą. Norėdami gauti pagrindinį supratimą, perskaitykite šiuos straipsnius. 
Pagrindinis rekursijos supratimas. 
  1 problema: Parašykite programą ir pasikartojimo ryšį, kad surastumėte n Fibonačio eilutę, kur n>2 . 
  Matematinė lygtis:  
 
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>
 
  Pasikartojimo ryšys:  
 
T(n) = T(n-1) + T(n-2) + O(1)>
 
  Rekursyvi programa:  
 
 Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>
 
  Įgyvendinimas:  
 
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.>
 
 
 
 
    
 
>
 
    
 
>
 
 
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#
    
dinaminis programavimas
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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) + ' ');  }>
 
 
 
 
    
 
>
 
    
 
>
 
  Išvestis  
 
Fibonacci series of 5 numbers is: 0 1 1 2 3>
 
  Laiko sudėtingumas: O(2n) 
  Pagalbinė erdvė: O(n)
 
Čia yra 5 įvesties rekursinis medis, kuris aiškiai parodo, kaip didelę problemą galima išspręsti į mažesnes. 
fib(n) yra Fibonačio funkcija. Duotos programos laiko sudėtingumas gali priklausyti nuo funkcijos iškvietimo.
  
 
fib(n) -> lygio CBT (UB) -> 2^n-1 mazgai -> 2^n funkcijos iškvietimas -> 2^n*O(1) -> T(n) = O(2^n)
 
 
Geriausiu atveju.
 
T(n) = ?(2^n2)>
 
  Dirba:  
 
 
 
  2 problema: Parašykite programą ir pasikartojimo ryšį, kad surastumėte n faktorių, kur n>2 . 
  Matematinė lygtis:  
 
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>
 
  Pasikartojimo ryšys:  
 
T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>
 
  Rekursyvi programa:   
  Įvestis: n = 5 
  Išvestis:   
Faktorius iš 5 yra: 120 
  Įgyvendinimas:  
 
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;> }> 
 
 
 
 
    
 
>
 
    
 
>
 
 
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.> 
 
 
 
 
romėniški skaičiai nuo 1 iki 100
    
 
>
 
    
 
>
 
 
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.> > 
 
 
 
 
    
 
>
 
    
 
>
 
  Išvestis  
 
factorial of 5 is: 120>
 
  Laiko sudėtingumas: O(n) 
  Pagalbinė erdvė: O(n)
 
  Dirba:   
 
  
Faktinės rekursijos funkcijos diagrama vartotojo įvesties 5.
 
Pavyzdys: Realūs rekursijos taikymai realiose problemose
 
Rekursija yra galinga technika, turinti daug pritaikymų kompiuterių moksle ir programavime. Štai keletas įprastų rekursijos taikymo būdų:
 
Medžio ir grafiko perkėlimas : rekursija dažnai naudojama duomenų struktūroms, pvz., medžiams ir grafikams, važiuoti ir ieškoti. Rekursiniai algoritmai gali būti naudojami sistemingai ištirti visus medžio ar grafiko mazgus ar viršūnes. Rūšiavimo algoritmai : rekursiniai algoritmai taip pat naudojami rūšiavimo algoritmuose, tokiuose kaip greitasis rūšiavimas ir sujungimo rūšiavimas. Šie algoritmai naudoja rekursiją duomenims padalyti į mažesnius pogrupius arba posąraščius, juos surūšiuoti ir vėl sujungti. „Skaldyk ir valdyk“ algoritmai : daugelis algoritmų, naudojančių „skaldyk ir užkariauk“ metodą, pvz., dvejetainis paieškos algoritmas, naudoja rekursiją, kad išskaidytų problemą į smulkesnes dalis. Fraktalų generavimas: Fraktalų formos ir modeliai gali būti generuojami naudojant rekursinius algoritmus. Pavyzdžiui, Mandelbroto rinkinys generuojamas pakartotinai taikant rekursinę formulę kompleksiniams skaičiams. Grįžimo algoritmai : Grįžimo algoritmai naudojami sprendžiant problemas, susijusias su sprendimų sekos priėmimu, kai kiekvienas sprendimas priklauso nuo ankstesnių. Šiuos algoritmus galima įgyvendinti naudojant rekursiją, siekiant ištirti visus galimus kelius ir grįžti atgal, kai sprendimas nerandamas. Atmintis : atmintinė yra technika, kuri apima brangių funkcijų iškvietimų rezultatų saugojimą ir talpyklos rezultato grąžinimą, kai vėl kartojasi tie patys įėjimai. Atmintinė gali būti įgyvendinta naudojant rekursines funkcijas, kad būtų galima apskaičiuoti ir talpykloje saugoti antrinių problemų rezultatus.
 
Tai tik keli pavyzdžiai iš daugybės rekursijos taikymo kompiuterių moksle ir programavime. Rekursija yra universalus ir galingas įrankis, kurį galima naudoti sprendžiant daugybę skirtingų problemų.
 
Paaiškinimas: vienas tikras rekursijos pavyzdys:
 
Rekursija yra programavimo technika, apimanti pačios funkcijos iškvietimą. Tai gali būti galingas įrankis sprendžiant sudėtingas problemas, tačiau jį taip pat reikia kruopščiai įgyvendinti, kad būtų išvengta begalinių ciklų ir krūvos perpildymo.
 
Štai pavyzdys, kaip įgyvendinti rekursiją 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> >}> }> 
 
 
 
 
    
 
>
 
    
 
>
 
 
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> 
 
 
 
 
    
 
>
 
    
 
>
 
  Išvestis  
 
120>
 
Šiame pavyzdyje apibrėžiame funkciją, vadinamą faktorialiu, kuri kaip įvestį paima sveikąjį skaičių n. Funkcija naudoja rekursiją, kad apskaičiuotų n faktorialą (t. y. visų teigiamų sveikųjų skaičių sandaugą iki n).
 
Faktorinė funkcija pirmiausia patikrina, ar n yra 0 ar 1, kurie yra pagrindiniai atvejai. Jei n yra 0 arba 1, funkcija grąžina 1, nes 0! ir 1! abu yra 1.
kas yra svn checkout
 
Jei n yra didesnis nei 1, funkcija įveda į rekursyvųjį mažąjį atvejį. Jis save vadina argumentu n-1 ir rezultatą padaugina iš n. Tai apskaičiuoja n! rekursyviai skaičiuojant (n-1)!.
 
Svarbu pažymėti, kad rekursija gali būti neveiksminga ir sukelti krūvos perpildymą, jei ji nebus naudojama atsargiai. Kiekvienas funkcijos iškvietimas į iškvietimo krūvą prideda naują kadrą, dėl kurio krūva gali išaugti per didelė, jei rekursija yra per gili. Be to, dėl rekursijos kodą gali būti sunkiau suprasti ir derinti, nes reikia galvoti apie kelių lygių funkcijų iškvietimus.
 
Tačiau rekursija taip pat gali būti galinga priemonė sprendžiant sudėtingas problemas, ypač tas, kurios apima problemos skaidymą į smulkesnes problemas. Tinkamai naudojant rekursiją, kodas gali būti elegantiškesnis ir lengviau skaitomas.
 
  Kokie yra rekursinio programavimo trūkumai, palyginti su iteraciniu programavimu?   
Atkreipkite dėmesį, kad tiek rekursinės, tiek kartotinės programos turi tas pačias problemų sprendimo galias, t. y. kiekviena rekursinė programa gali būti parašyta iteratyviai ir atvirkščiai. Rekursinei programai reikia didesnio vietos nei iteracinei programai, nes visos funkcijos liks krūvoje, kol bus pasiektas bazinis dydis. Jam taip pat reikia didesnių laiko poreikių dėl funkcijų iškvietimų ir grąžinimų.
 
Be to, dėl mažesnio kodo ilgio kodus sunku suprasti, todėl rašant kodą reikia būti ypač atsargiems. Jei pakartotiniai skambučiai nebus tinkamai patikrinti, kompiuteryje gali pritrūkti atminties.
 
  Kokie yra rekursinio programavimo pranašumai, palyginti su iteraciniu programavimu?   
Rekursija suteikia švarų ir paprastą kodo rašymo būdą. Kai kurios problemos iš prigimties yra rekursyvios, pavyzdžiui, perėjimas medžiu, Hanojaus bokštas tt Tokioms problemoms spręsti pageidautina rašyti rekursinį kodą. Tokius kodus galime rašyti ir iteratyviai, naudodami kamino duomenų struktūrą. Pavyzdžiui, žr. Inorder Tree Traversal be rekursijos, Iteratyvus Hanojaus bokštas.
 
  Rekursijos santrauka:  
 
 
Rekursijoje yra dviejų tipų atvejai, ty rekursinis atvejis ir bazinis atvejis.
 
Bazinis dydis naudojamas rekursinei funkcijai nutraukti, kai paaiškėja, kad atvejis yra teisingas.
 
Kiekvienas rekursinis iškvietimas sukuria naują šio metodo kopiją kamino atmintyje.
 
Dėl begalinės rekursijos gali pritrūkti kamino atminties.
 
Rekursinių algoritmų pavyzdžiai: sujungimo rūšiavimas, greitasis rūšiavimas, Hanojaus bokštas, Fibonačio serija, faktorinė problema ir kt.
 
 
  Išėjimu pagrįstos praktikos problemos pradedantiesiems:   
Praktiniai klausimai apie rekursiją | 1 rinkinys 
Praktiniai klausimai apie rekursiją | 2 rinkinys 
Praktiniai klausimai apie rekursiją | 3 rinkinys 
Praktiniai klausimai apie rekursiją | 4 rinkinys 
Praktiniai klausimai apie rekursiją | 5 rinkinys 
Praktiniai klausimai apie rekursiją | 6 rinkinys 
Praktiniai klausimai apie rekursiją | 7 rinkinys 
   Viktorina apie rekursiją    
   Rekursijos kodavimo praktika:    
   Visi straipsniai apie rekursiją    
Rekursyvios praktikos problemos su sprendimais