Mikä on rekursio?
Prosessia, jossa funktio kutsuu itseään suoraan tai epäsuorasti, kutsutaan rekursioksi ja vastaavaa funktiota rekursiiviseksi funktioksi. Rekursiivisen algoritmin avulla tietyt ongelmat voidaan ratkaista melko helposti. Esimerkkejä tällaisista ongelmista ovat Hanoin tornit (TOH) , Tilaus/ennakkotilaus/jälkitilauspuun läpikulku , DFS of Graph jne. Rekursiivinen funktio ratkaisee tietyn ongelman kutsumalla kopion itsestään ja ratkaisemalla alkuperäisten tehtävien pienemmät osaongelmat. Paljon enemmän rekursiivisia puheluita voidaan luoda tarpeen mukaan. On olennaista tietää, että meidän tulee tarjota tietty tapaus tämän rekursioprosessin lopettamiseksi. Voimme siis sanoa, että joka kerta kun funktio kutsuu itseään alkuperäisen ongelman yksinkertaisemmalla versiolla.

Rekursion tarve

Rekursio on hämmästyttävä tekniikka, jonka avulla voimme lyhentää koodimme pituutta ja helpottaa sen lukemista ja kirjoittamista. Sillä on tiettyjä etuja iterointitekniikkaan verrattuna, joista keskustellaan myöhemmin. Tehtävä, joka voidaan määritellä samankaltaisella osatehtävällään, rekursiolla, on yksi parhaista ratkaisuista siihen. Esimerkiksi; Lukujen tekijöitä.

Rekursion ominaisuudet:

• Suorita samat toiminnot useita kertoja eri tuloilla.
• Yritämme jokaisessa vaiheessa pienempiä syötteitä pienentääksemme ongelmaa.
• Perusehto tarvitaan pysäyttämään rekursio, muuten tapahtuu ääretön silmukka.

Algoritmi: Vaiheet

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

Matemaattinen tulkinta

Tarkastellaanpa ongelmaa, että ohjelmoijan on määritettävä n ensimmäisen luonnollisen luvun summa, siihen on useita tapoja, mutta yksinkertaisin tapa on yksinkertaisesti laskea yhteen luvut alkaen 1:stä n:ään. Toiminto näyttää siis tältä,

lähestymistapa(1) – Yksinkertaisesti lisääminen yksitellen

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

mutta on olemassa toinen matemaattinen lähestymistapa tämän esittämiseen,

lähestymistapa(2) – Rekursiivinen lisääminen

f(n) = 1 n = 1

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

Lähestymistavan (1) ja lähestymistavan (2) välillä on yksinkertainen ero, ja se on siinä lähestymistapa(2) toiminto f( ) itseään kutsutaan funktion sisällä, joten tätä ilmiötä kutsutaan rekursioksi ja rekursion sisältävää funktiota kutsutaan rekursiiviseksi funktioksi, loppujen lopuksi tämä on loistava työkalu ohjelmoijien käsissä koodata joitakin ongelmia paljon helpommin ja tehokkaammin. tapa.

Miten rekursiiviset funktiot tallennetaan muistiin?

Rekursio käyttää enemmän muistia, koska rekursiivinen funktio lisää pinon jokaisen rekursiivisen kutsun yhteydessä ja säilyttää arvot siellä, kunnes puhelu on valmis. Rekursiivinen funktio käyttää LIFO (LAST IN FIRST OUT) -rakennetta aivan kuten pinon tietorakenne. pino-data-rakenne/

Mikä on perusehto rekursiossa?
Rekursiivisessa ohjelmassa tarjotaan ratkaisu perustapaukseen ja isomman ongelman ratkaisu ilmaistaan ​​pienempinä ongelmina.

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

Yllä olevassa esimerkissä perustapaus arvolle n <= 1 on määritelty ja luvun suurempi arvo voidaan ratkaista muuttamalla pienemmäksi, kunnes perustapaus saavutetaan.

Miten tietty ongelma ratkaistaan ​​rekursion avulla?
Ajatuksena on esittää ongelma yhden tai useamman pienemmän ongelman muodossa ja lisätä yksi tai useampi perusehto, joka pysäyttää rekursion. Laskemme esimerkiksi faktoriaalin n, jos tiedämme (n-1) faktoriaalin. Faktoriaalin perustapaus olisi n = 0. Palautamme 1, kun n = 0.

Miksi pinon ylivuotovirhe tapahtuu rekursiossa?
Jos perustapausta ei saavuteta tai sitä ei ole määritelty, voi syntyä pinon ylivuotoongelma. Otetaan esimerkki tämän ymmärtämiseksi.

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

Jos kutsutaan fact(10), se kutsuu fact(9), fact(8), fact(7) ja niin edelleen, mutta luku ei koskaan saavuta 100. Joten perustapausta ei saavuteta. Jos muisti kuluu loppuun näiden pinon toimintojen takia, se aiheuttaa pinon ylivuotovirheen.

Mitä eroa on suoralla ja epäsuoralla rekursiolla?
Funktiota kutsutaan suoraksi rekursiiviseksi, jos se kutsuu samaa funktiota fun. Funktiota fun kutsutaan epäsuoraksi rekursiiviseksi, jos se kutsuu toista funktiota eli fun_new ja fun_new kutsuu fun suoraan tai epäsuorasti. Suoran ja epäsuoran rekursion välinen ero on havainnollistettu taulukossa 1.

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

Mitä eroa on tailed- ja ei-tailed-rekursiolla?
Rekursiivinen funktio on häntärekursiivinen, kun rekursiivinen kutsu on funktion viimeinen suorittama asia. Katso tail rekursio artikkeli yksityiskohtia varten.

Miten muistia varataan eri funktiokutsuille rekursiossa?
Kun mitä tahansa funktiota kutsutaan main(:sta), sille varataan muisti pinossa. Rekursiivinen funktio kutsuu itseään, kutsutun funktion muisti varataan kutsuvalle funktiolle varatun muistin päälle ja jokaiselle funktiokutsulle luodaan eri kopio paikallisista muuttujista. Kun perustapaus saavutetaan, funktio palauttaa arvonsa funktiolle, joka kutsuu sitä ja muisti puretaan ja prosessi jatkuu.
Otetaan esimerkki siitä, kuinka rekursio toimii ottamalla yksinkertainen funktio.

CPP

>

>

Java

modeemi vs reititin

>

>

Python 3

>

>

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);> > > 
 
 
 
 
    
 
>
 
    
 
>
 
  Lähtö  
 
3 2 1 1 2 3>
 
  Aika monimutkaisuus: O(1) 
  Aputila: O(1)
Java-kielen haastattelukysymykset
 
Kun printFun(3) kutsutaan main(), muisti on varattu printFun(3) ja paikallinen muuttujatesti alustetaan arvoon 3 ja käskyt 1-4 työnnetään pinoon alla olevan kaavion mukaisesti. Se tulostaa ensin '3'. Lausunnossa 2 printFun(2) kutsutaan ja muistia varataan printFun(2) ja paikallinen muuttujatesti alustetaan arvoon 2 ja käsky 1-4 työnnetään pinoon. Samalla lailla, printFun(2) puhelut printFun(1) ja printFun(1) puhelut printFun(0) . printFun(0) menee if-lauseeseen ja se palaa printFun(1) . Loput lausunnot printFun(1) suoritetaan ja se palaa printFun(2) ja niin edelleen. Tulosteessa arvot 3-1 tulostetaan ja sitten 1-3 tulostetaan. Muistipino on esitetty alla olevassa kaaviossa.
 
 
 
  Rekursio VS Iteraatio  
 
 
 
 
  SR nro  
 
  Rekursio  
 
  Iterointi  
 
 
 
1)
 
Päättyy, kun perustapaus muuttuu todeksi.
 
Päättyy, kun ehdosta tulee epätosi.
 
 
 
2)
 
Käytetään toimintojen kanssa.
 
Käytetään silmukoiden kanssa.
 
 
 
3)
 
Jokainen rekursiivinen puhelu tarvitsee ylimääräistä tilaa pinomuistissa.
 
Jokainen iteraatio ei vaadi ylimääräistä tilaa.
 
 
 
4)
 
Pienempi koodikoko.
 
Suurempi koodikoko.
 
 
 
 
Keskustellaan nyt muutamasta käytännön ongelmasta, jotka voidaan ratkaista käyttämällä rekursiota, ja ymmärrämme sen perustoiminnan. Perusymmärryksen saamiseksi lue seuraavat artikkelit. 
Rekursion perusymmärrys. 
  Ongelma 1: Kirjoita ohjelma ja toistuvuusrelaatio löytääksesi n:n Fibonacci-sarja, jossa n>2 . 
  Matemaattinen yhtälö:  
 
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>
 
  Toistuva suhde:  
 
T(n) = T(n-1) + T(n-2) + O(1)>
 
  Rekursiivinen ohjelma:  
 
 Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>
 
  Toteutus:  
 
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.>
 
 
 
 
    
 
>
 
    
 
>
 
 
Python 3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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) + ' ');  }>
 
 
 
 
    
 
>
 
    
 
>
 
  Lähtö  
 
Fibonacci series of 5 numbers is: 0 1 1 2 3>
 
  Aika monimutkaisuus: O(2n) 
  Aputila: Päällä)
 
Tässä on syötteen 5 rekursiivinen puu, joka näyttää selkeän kuvan siitä, kuinka suuri ongelma voidaan ratkaista pienemmiksi. 
fib(n) on Fibonacci-funktio. Annetun ohjelman aika monimutkaisuus voi riippua funktiokutsusta.
  
 
fib(n) -> taso CBT (UB) -> 2^n-1 solmua -> 2^n funktiokutsu -> 2^n*O(1) -> T(n) = O(2^n)
 
 
Parhaassa tapauksessa.
 
T(n) = ?(2^n2)>
 
  Työskentely:  
 
 
 
  Ongelma 2: Kirjoita ohjelma ja toistuvuusrelaatio löytääksesi n:n kertoimen, jossa n>2 . 
  Matemaattinen yhtälö:  
 
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>
 
  Toistuva suhde:  
 
T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>
 
  Rekursiivinen ohjelma:   
  Syöte: n = 5 
  Lähtö:   
5:n faktoraali on: 120 
  Toteutus:  
 
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.> 
 
 
 
 
    
 
>
 
    
 
>
 
 
Python 3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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
    
 
     
  
 
    
 
     
     
    
von Neumann -arkkitehtuuri
 
 
 
 
 
 > // 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.> > 
 
 
 
 
    
 
>
 
    
 
>
 
  Lähtö  
 
factorial of 5 is: 120>
 
  Aika monimutkaisuus: Päällä) 
  Aputila: Päällä)
 
  Työskentely:   
 
  
Käyttäjän syötteen 5 tekijärekursiofunktion kaavio.
 
Esimerkki: Rekursion todelliset sovellukset todellisissa ongelmissa
 
Rekursio on tehokas tekniikka, jolla on monia sovelluksia tietojenkäsittelytieteessä ja ohjelmoinnissa. Tässä on joitain yleisimpiä rekursiosovelluksia:
 
Puun ja graafin läpikulku: Rekursiota käytetään usein tietorakenteiden, kuten puiden ja kaavioiden, läpikulkuun ja etsimiseen. Rekursiivisten algoritmien avulla voidaan tutkia kaikki puun tai graafin solmut tai kärjet systemaattisesti. Lajittelualgoritmit : Rekursiivisia algoritmeja käytetään myös lajittelualgoritmeissa, kuten pikalajittelussa ja yhdistämislajittelussa. Nämä algoritmit jakavat tiedot rekursion avulla pienempiin aliryhmiin tai aliluetteloihin, lajittelevat ne ja yhdistävät ne sitten takaisin yhteen. Jaa ja hallitse -algoritmit : Monet jakaa ja hallitse -lähestymistapaa käyttävät algoritmit, kuten binäärihakualgoritmi, käyttävät rekursiota ongelman pilkkomiseen pienempiin osaongelmiin. Fraktaaligenerointi: Fraktaalimuotoja ja -kuvioita voidaan luoda käyttämällä rekursiivisia algoritmeja. Esimerkiksi Mandelbrot-joukko luodaan soveltamalla toistuvasti rekursiivista kaavaa kompleksilukuihin. Peruutusalgoritmit : Takaisinseurannan algoritmeja käytetään ratkaisemaan ongelmia, jotka edellyttävät sarjan päätöksiä, joissa jokainen päätös riippuu edellisistä. Nämä algoritmit voidaan toteuttaa käyttämällä rekursiota tutkimaan kaikkia mahdollisia polkuja ja palaamaan takaisin, kun ratkaisua ei löydy. Memoisointi: Memoisointi on tekniikka, joka sisältää kalliiden funktiokutsujen tulosten tallentamisen ja välimuistissa olevan tuloksen palauttamisen, kun samat syötteet toistuvat. Memoisointi voidaan toteuttaa käyttämällä rekursiivisia funktioita aliongelmien tulosten laskemiseen ja tallentamiseen välimuistiin.
 
Nämä ovat vain muutamia esimerkkejä rekursion monista sovelluksista tietojenkäsittelytieteen ja ohjelmoinnin alalla. Rekursio on monipuolinen ja tehokas työkalu, jota voidaan käyttää monenlaisten ongelmien ratkaisemiseen.
 
Selitys: yksi todellinen esimerkki rekursiosta:
 
Rekursio on ohjelmointitekniikka, jossa funktio kutsuu itseään. Se voi olla tehokas työkalu monimutkaisten ongelmien ratkaisemiseen, mutta se vaatii myös huolellista toteutusta, jotta vältetään loputtomat silmukat ja pinon ylivuodot.
 
Tässä on esimerkki rekursion toteuttamisesta Pythonissa:
 
C++
    
 
     
  
 
    
 
     
     
    
 
tekoäly ja älykkäät agentit
 
 
 
 
 #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> >}> }> 
 
 
 
 
    
 
>
 
    
 
>
 
 
Python 3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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> 
 
 
 
 
    
 
>
 
    
 
>
 
  Lähtö  
 
120>
 
Tässä esimerkissä määrittelemme funktion nimeltä factorial, joka ottaa syötteenä kokonaisluvun n. Funktio käyttää rekursiota laskeakseen n:n kertoimen (eli kaikkien positiivisten kokonaislukujen tulon n:ään asti).
 
Tekijäfunktio tarkistaa ensin, onko n 0 vai 1, jotka ovat perustapauksia. Jos n on 0 tai 1, funktio palauttaa arvon 1, koska 0! ja 1! ovat molemmat 1.
 
Jos n on suurempi kuin 1, funktio siirtyy rekursiiviseen tapaukseen. Se kutsuu itseään argumenttina n-1 ja kertoo tuloksen n:llä. Tämä laskee n! rekursiivisesti laskemalla (n-1)!.
 
On tärkeää huomata, että rekursio voi olla tehotonta ja johtaa pinon ylivuotoon, jos sitä ei käytetä huolellisesti. Jokainen funktiokutsu lisää uuden kehyksen kutsupinoon, mikä voi saada pinon kasvamaan liian suureksi, jos rekursio on liian syvä. Lisäksi rekursio voi vaikeuttaa koodin ymmärtämistä ja virheenkorjausta, koska se edellyttää useiden toimintokutsujen tasoa.
 
Rekursio voi kuitenkin olla myös tehokas työkalu monimutkaisten ongelmien ratkaisemiseen, erityisesti sellaisiin, joissa ongelma jaetaan pienempiin osaongelmiin. Oikein käytettynä rekursio voi tehdä koodista tyylikkäämmän ja helpommin luettavan.
 
  Mitkä ovat rekursiivisen ohjelmoinnin haitat iteratiiviseen ohjelmointiin verrattuna?   
Huomaa, että sekä rekursiivisilla että iteratiivisilla ohjelmilla on samat ongelmanratkaisuvoimat, eli jokainen rekursiivinen ohjelma voidaan kirjoittaa iteratiivisesti ja päinvastoin on myös totta. Rekursiivisella ohjelmalla on suurempi tilavaatimus kuin iteratiivisella ohjelmalla, koska kaikki funktiot pysyvät pinossa, kunnes perustapaus saavutetaan. Sillä on myös suuremmat aikavaatimukset funktiokutsujen ja palautusten vuoksi.
 
Lisäksi koodin pienemmän pituuden vuoksi koodeja on vaikea ymmärtää ja siksi koodin kirjoittamisessa on oltava erityisen huolellinen. Tietokoneen muisti saattaa loppua, jos rekursiivisia kutsuja ei tarkisteta kunnolla.
 
  Mitkä ovat rekursiivisen ohjelmoinnin edut iteratiiviseen ohjelmointiin verrattuna?   
Rekursio tarjoaa puhtaan ja yksinkertaisen tavan kirjoittaa koodia. Jotkut ongelmat ovat luonnostaan ​​rekursiivisia, kuten puiden läpikulku, Hanoin torni , jne. Tällaisia ​​ongelmia varten on suositeltavaa kirjoittaa rekursiivinen koodi. Tällaisia ​​koodeja voidaan kirjoittaa myös iteratiivisesti pinotietorakenteen avulla. Katso esimerkiksi Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.
 
  Yhteenveto rekursiosta:  
 
 
Rekursiossa on kahdenlaisia ​​tapauksia eli rekursiivinen tapaus ja perustapaus.
 
Perustapausta käytetään lopettamaan rekursiivinen funktio, kun tapaus osoittautuu todeksi.
 
Jokainen rekursiivinen kutsu tekee menetelmästä uuden kopion pinomuistiin.
 
Ääretön rekursio voi johtaa pinomuistin loppumiseen.
 
Esimerkkejä rekursiivisista algoritmeista: Yhdistelmälajittelu, Pikalajittelu, Hanoin torni, Fibonacci-sarja, Factorial Problem jne.
 
 
  Tulospohjaiset harjoitusongelmat aloittelijoille:   
Rekursion harjoituskysymyksiä | Sarja 1 
Rekursion harjoituskysymyksiä | Sarja 2 
Rekursion harjoituskysymyksiä | Sarja 3 
Rekursion harjoituskysymyksiä | Sarja 4 
Rekursion harjoituskysymyksiä | Sarja 5 
Rekursion harjoituskysymyksiä | Sarja 6 
Rekursion harjoituskysymyksiä | Sarja 7 
   Tietokilpailu rekursiosta    
   Rekursion koodauskäytäntö:    
   Kaikki artikkelit rekursiosta    
Rekursiiviset käytännön ongelmat ratkaisuilla