Staart recursie wordt gedefinieerd als een recursieve functie waarbij de recursieve aanroep de laatste instructie is die door de functie wordt uitgevoerd. Er hoeft dus eigenlijk niets meer te worden uitgevoerd na de recursieaanroep.
De volgende C++-functie print() is bijvoorbeeld recursief.
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> > |
>
>
Tijdcomplexiteit: Op)
Hulpruimte: Op)
Behoefte aan staartrecursie:
De recursieve staartfuncties worden als beter beschouwd dan niet-staartrecursieve functies, aangezien staartrecursie door de compiler kan worden geoptimaliseerd.
Compilers voeren gewoonlijk recursieve procedures uit met behulp van a stapel . Deze stapel bestaat uit alle relevante informatie, inclusief de parameterwaarden, voor elke recursieve oproep. Wanneer een procedure wordt aangeroepen, wordt de informatie ervan weergegeven geduwd op een stapel, en wanneer de functie eindigt, wordt de informatie opgeslagen knalde uit de stapel. Dus voor de niet-staart-recursieve functies geldt de stapeldiepte (maximale hoeveelheid stapelruimte die op enig moment tijdens het compileren wordt gebruikt) is meer.
Het idee dat door compilers wordt gebruikt om staart-recursieve functies te optimaliseren is eenvoudig, aangezien de recursieve aanroep de laatste instructie is, er niets meer te doen is in de huidige functie, dus het opslaan van het stapelframe van de huidige functie heeft geen zin (zie dit voor meer informatie details).
Kan een niet-staart-recursieve functie als staart-recursief worden geschreven om deze te optimaliseren?
Beschouw de volgende functie om de faculteit van n te berekenen.
Het is een niet-staart-recursieve functie. Hoewel het op het eerste gezicht lijkt op een recursieve staart. Als we beter kijken, kunnen we zien dat de waarde die wordt geretourneerd door fact(n-1) wordt gebruikt feit(n) . Dus de oproep tot feit(n-1) is niet het laatste wat gedaan wordt feit(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> > |
>
>Uitvoer
120>
Tijdcomplexiteit: Op)
Hulpruimte: Op)
De bovenstaande functie kan worden geschreven als een staart-recursieve functie. Het idee is om nog een argument te gebruiken en de factoriële waarde in het tweede argument te accumuleren. Wanneer n 0 bereikt, retourneert u de geaccumuleerde waarde.
Hieronder ziet u de implementatie met behulp van een staart-recursieve functie.
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.> |
>
array van strings c programmeren
>
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> > > |
>
>Uitvoer
120>
Tijdcomplexiteit: Op)
Hulpruimte: O(1)
Volgende artikelen over dit onderwerp:
- Eliminatie van staartoproepen
- QuickSort Tail Call-optimalisatie (verkleining van de worst case-ruimte naar Log n)