Halerekursion er defineret som en rekursiv funktion, hvor det rekursive kald er den sidste sætning, der udføres af funktionen. Så der er stort set intet tilbage at udføre efter rekursionsopkaldet.
For eksempel er den følgende C++ funktion print() hale rekursiv.
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> > |
>
>
Tidskompleksitet: På)
Hjælpeplads: På)
Behov for halerekursion:
De rekursive hale-funktioner anses for at være bedre end ikke-hale-rekursive funktioner, da hale-rekursion kan optimeres af compileren.
Kompilere udfører normalt rekursive procedurer ved at bruge en stak . Denne stak består af al den relevante information, inklusive parameterværdierne, for hvert rekursivt kald. Når en procedure kaldes, er dens information skubbet på en stak, og når funktionen afsluttes, er informationen poppede ud af stakken. For de ikke-hale-rekursive funktioner er det således stak dybde (maksimal mængde stackplads brugt til enhver tid under kompilering) er mere.
Ideen brugt af compilere til at optimere hale-rekursive funktioner er enkel, da det rekursive kald er det sidste udsagn, er der intet tilbage at gøre i den aktuelle funktion, så det nytter ikke noget at gemme den aktuelle funktions stakramme (se dette for mere detaljer).
Kan en ikke-hale-rekursiv funktion skrives som hale-rekursiv for at optimere den?
Overvej følgende funktion til at beregne faktoren af n.
Det er en ikke-hale-rekursiv funktion. Selvom det ved første øjekast ligner en rekursiv hale. Hvis vi kigger nærmere, kan vi se, at værdien returneret af fakta(n-1) bruges i fakta(n) . Så opfordringen til fakta(n-1) er ikke det sidste, der er gjort af fakta(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> > |
>
>Produktion
120>
Tidskompleksitet: På)
Hjælpeplads: På)
Ovenstående funktion kan skrives som en hale-rekursiv funktion. Ideen er at bruge et argument mere og akkumulere faktorværdien i det andet argument. Når n når 0, returneres den akkumulerede værdi.
Nedenfor er implementeringen ved hjælp af en hale-rekursiv funktion.
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.> |
>
romertal diagram 1 100
>
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> > > |
>
>Produktion
120>
Tidskompleksitet: På)
Hjælpeplads: O(1)
Næste artikler om dette emne:
- Fjernelse af haleopkald
- QuickSort Tail Call Optimization (Reducer worst case plads til log n)