Repna rekurzija je definirana kot rekurzivna funkcija, pri kateri je rekurzivni klic zadnji stavek, ki ga izvede funkcija. Tako v bistvu po klicu rekurzije ni več ničesar za izvedbo.
Naslednja funkcija C++ print() je na primer repno rekurzivna.
C
// An example of tail recursive function> void> print(>int> n)> {> >if> (n <0)> >return>;> >printf>(>'%d '>, n);> >// The last executed statement is recursive call> >print(n - 1);> }> |
>
>
C++
// An example of tail recursive function> static> void> print(>int> n)> {> >if> (n <0)> >return>;> >cout <<>' '> << n;> > >// The last executed statement is recursive call> >print(n - 1);> }> // This code is contributed by Aman Kumar> |
>
>
Java
// An example of tail recursive function> static> void> print(>int> n)> {> >if> (n <>0>)> >return>;> >System.out.print(>' '> + n);> >// The last executed statement> >// is recursive call> >print(n ->1>);> }> // This code is contributed by divyeh072019> |
>
>
Python3
# An example of tail recursive function> def> prints(n):> >if> (n <>0>):> >return> >print>(>str>(n), end>=>' '>)> ># The last executed statement is recursive call> >prints(n>->1>)> ># This code is contributed by Pratham76> ># improved by ashish2021> |
>
>
C#
// An example of tail recursive function> static> void> print(>int> n)> {> >if> (n <0)> >return>;> >Console.Write(>' '> + n);> >// The last executed statement> >// is recursive call> >print(n - 1);> }> // This code is contributed by divyeshrabadiya07> |
>
>
Javascript
> // An example of tail recursive function> function> print(n)> {> >if> (n <0)> >return>;> > >document.write(>' '> + n);> > >// The last executed statement> >// is recursive call> >print(n - 1);> }> // This code is contributed by Rajput-Ji> > |
>
>
Časovna zapletenost: O(n)
Pomožni prostor: O(n)
Potreba po repni rekurziji:
Repne rekurzivne funkcije veljajo za boljše od nerepnih rekurzivnih funkcij, saj lahko repno rekurzijo optimizira prevajalnik.
Prevajalniki običajno izvajajo rekurzivne postopke z uporabo a kup . Ta sklad je sestavljen iz vseh ustreznih informacij, vključno z vrednostmi parametrov, za vsak rekurzivni klic. Ko je postopek poklican, so njegove informacije potisnil na sklad in ko se funkcija prekine, je informacija počil iz sklada. Tako je za ne-rekurzivne funkcije globina sklada (največja količina prostora sklada, uporabljenega kadar koli med prevajanjem) je več.
Zamisel, ki jo uporabljajo prevajalniki za optimizacijo repno rekurzivnih funkcij, je preprosta, ker je rekurzivni klic zadnji stavek, v trenutni funkciji ni več treba storiti ničesar, zato shranjevanje okvira sklada trenutne funkcije ni koristno (glejte to za več podrobnosti).
Ali je mogoče nerekurzivno funkcijo zapisati kot repno rekurzivno, da jo optimiziramo?
Razmislite o naslednji funkciji za izračun faktoriala n.
Je ne-rekurzivna funkcija. Čeprav je na prvi pogled videti kot rekurziven rep. Če pogledamo pobližje, lahko vidimo, da je vrednost, ki jo vrne fact(n-1), uporabljena v dejstvo (n) . Torej poziv k dejstvo (n-1) ni zadnja stvar, ki jo je naredil dejstvo (n) .
C++
#include> using> namespace> std;> // A NON-tail-recursive function. The function is not tail> // recursive because the value returned by fact(n-1) is used> // in fact(n) and call to fact(n-1) is not the last thing> // done by fact(n)> unsigned>int> fact(unsigned>int> n)> {> >if> (n <= 0)> >return> 1;> >return> n * fact(n - 1);> }> // Driver program to test above function> int> main()> {> >cout << fact(5);> >return> 0;> }> |
>
>
Java
class> GFG {> >// A NON-tail-recursive function.> >// The function is not tail> >// recursive because the value> >// returned by fact(n-1) is used> >// in fact(n) and call to fact(n-1)> >// is not the last thing done by> >// fact(n)> >static> int> fact(>int> n)> >{> >if> (n ==>0>)> >return> 1>;> >return> n * fact(n ->1>);> >}> >// Driver program> >public> static> void> main(String[] args)> >{> >System.out.println(fact(>5>));> >}> }> // This code is contributed by Smitha.> |
>
>
Python3
# A NON-tail-recursive function.> # The function is not tail> # recursive because the value> # returned by fact(n-1) is used> # in fact(n) and call to fact(n-1)> # is not the last thing done by> # fact(n)> def> fact(n):> >if> (n>=>=> 0>):> >return> 1> >return> n>*> fact(n>->1>)> # Driver program to test> # above function> if> __name__>=>=> '__main__'>:> >print>(fact(>5>))> # This code is contributed by Smitha.> |
>
>
C#
using> System;> class> GFG {> >// A NON-tail-recursive function.> >// The function is not tail> >// recursive because the value> >// returned by fact(n-1) is used> >// in fact(n) and call to fact(n-1)> >// is not the last thing done by> >// fact(n)> >static> int> fact(>int> n)> >{> >if> (n == 0)> >return> 1;> >return> n * fact(n - 1);> >}> >// Driver program to test> >// above function> >public> static> void> Main() { Console.Write(fact(5)); }> }> // This code is contributed by Smitha> |
>
>
PHP
// A NON-tail-recursive function. // The function is not tail // recursive because the value // returned by fact(n-1) is used in // fact(n) and call to fact(n-1) is // not the last thing done by fact(n) function fact( $n) { if ($n == 0) return 1; return $n * fact($n - 1); } // Driver Code echo fact(5); // This code is contributed by Ajit ?>> |
>
>
Javascript
> // A NON-tail-recursive function.> // The function is not tail> // recursive because the value> // returned by fact(n-1) is used> // in fact(n) and call to fact(n-1)> // is not the last thing done by> // fact(n)> function> fact(n)> {> >if> (n == 0)> >return> 1;> > >return> n * fact(n - 1);> }> // Driver code> document.write(fact(5));> // This code is contributed by divyeshrabadiya07> > |
>
>Izhod
120>
Časovna zapletenost: O(n)
Pomožni prostor: O(n)
Zgornjo funkcijo lahko zapišemo kot repno rekurzivno funkcijo. Ideja je, da uporabimo še en argument in v drugem argumentu zberemo faktorijelo. Ko n doseže 0, vrne akumulirano vrednost.
Spodaj je implementacija z repno rekurzivno funkcijo.
C++
#include> using> namespace> std;> // A tail recursive function to calculate factorial> unsigned factTR(unsigned>int> n, unsigned>int> a)> {> >if> (n <= 1)> >return> a;> >return> factTR(n - 1, n * a);> }> // A wrapper over factTR> unsigned>int> fact(unsigned>int> n) {>return> factTR(n, 1); }> // Driver program to test above function> int> main()> {> >cout << fact(5);> >return> 0;> }> |
>
>
Java
// Java Code for Tail Recursion> class> GFG {> >// A tail recursive function> >// to calculate factorial> >static> int> factTR(>int> n,>int> a)> >{> >if> (n <=>0>)> >return> a;> >return> factTR(n ->1>, n * a);> >}> >// A wrapper over factTR> >static> int> fact(>int> n) {>return> factTR(n,>1>); }> >// Driver code> >static> public> void> main(String[] args)> >{> >System.out.println(fact(>5>));> >}> }> // This code is contributed by Smitha.> |
>
četrtina v poslu
>
Python3
# A tail recursive function> # to calculate factorial> def> fact(n, a>=>1>):> >if> (n <>=> 1>):> >return> a> >return> fact(n>-> 1>, n>*> a)> # Driver program to test> # above function> print>(fact(>5>))> # This code is contributed> # by Smitha> # improved by Ujwal, ashish2021> |
>
>
C#
// C# Code for Tail Recursion> using> System;> class> GFG {> >// A tail recursive function> >// to calculate factorial> >static> int> factTR(>int> n,>int> a)> >{> >if> (n <= 0)> >return> a;> >return> factTR(n - 1, n * a);> >}> >// A wrapper over factTR> >static> int> fact(>int> n) {>return> factTR(n, 1); }> >// Driver code> >static> public> void> Main()> >{> >Console.WriteLine(fact(5));> >}> }> // This code is contributed by Ajit.> |
>
>
PHP
// A tail recursive function // to calculate factorial function factTR($n, $a) { if ($n <= 0) return $a; return factTR($n - 1, $n * $a); } // A wrapper over factTR function fact($n) { return factTR($n, 1); } // Driver program to test // above function echo fact(5); // This code is contributed // by Smitha ?>> |
>
>
Javascript
> // Javascript Code for Tail Recursion> // A tail recursive function> // to calculate factorial> function> factTR(n, a)> {> >if> (n <= 0)> >return> a;> > >return> factTR(n - 1, n * a);> }> > // A wrapper over factTR> function> fact(n)> {> >return> factTR(n, 1);> }> // Driver code> document.write(fact(5));> // This code is contributed by rameshtravel07> > > |
>
>Izhod
120>
Časovna zapletenost: O(n)
Pomožni prostor: O(1)
Naslednji članki na to temo:
- Odprava repnega klica
- Optimizacija repnega klica QuickSort (zmanjšanje prostora v najslabšem primeru na Log n)