Uodegos rekursija apibrėžiamas kaip rekursinė funkcija, kurioje rekursinis iškvietimas yra paskutinis funkcijos vykdomas sakinys. Taigi iš esmės nieko nebelieka vykdyti po rekursijos iškvietimo.
Pavyzdžiui, ši C++ funkcija print() yra rekursinė.
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> > |
>
>
Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(n)
Uodegos rekursijos poreikis:
Uodegos rekursinės funkcijos laikomos geresnėmis nei ne uodegos rekursinės funkcijos, nes kompiliatorius gali optimizuoti uodegos rekursiją.
Kompiliatoriai paprastai vykdo rekursines procedūras naudodami a krūva . Šį krūvą sudaro visa susijusi informacija, įskaitant parametrų reikšmes, kiekvienam rekursiniam skambučiui. Kai iškviečiama procedūra, jos informacija yra pastūmė į krūvą, o kai funkcija baigiasi, informacija yra iššoko iš rietuvės. Taigi ne uodegos rekursinėms funkcijoms, kamino gylis (maksimalus dėklo vietos kiekis, naudojamas bet kuriuo kompiliavimo metu) yra daugiau.
Kompiliatorių naudojama uodegos rekursinių funkcijų optimizavimo idėja yra paprasta, kadangi rekursinis iškvietimas yra paskutinis teiginys, dabartinėje funkcijoje nebelieka ką veikti, todėl dabartinės funkcijos kamino rėmelio išsaugojimas nėra naudingas (daugiau žr. detales).
Ar galima ne uodegos rekursyvią funkciją parašyti kaip uodegos rekursyvią, kad ją optimizuotų?
Apsvarstykite šią funkciją, kad apskaičiuotumėte n faktorialą.
Tai ne uodegos rekursinė funkcija. Nors iš pirmo žvilgsnio atrodo kaip rekursyvus uodega. Jei pažvelgsime atidžiau, pamatysime, kad fakto(n-1) grąžinta reikšmė naudojama faktas (n) . Taigi skambutis į faktas (n-1) nėra paskutinis dalykas, kurį padarė faktas (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 ?>>> |
>
>// 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>>>>Išvestis120>Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(n)Aukščiau pateiktą funkciją galima parašyti kaip uodegos rekursinę funkciją. Idėja yra naudoti dar vieną argumentą ir sukaupti faktorių reikšmę antrame argumente. Kai n pasiekia 0, grąžinkite sukauptą reikšmę.
Žemiau pateikiamas įgyvendinimas naudojant uodegos rekursinę funkciją.
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.>>pakeisti iš eilutės java>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 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>>>>>Išvestis120>Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(1)Kiti straipsniai šia tema:
- Uodegos skambučio pašalinimas
- „QuickSort Tail Call“ optimizavimas (blogiausio atvejo vietos sumažinimas iki žurnalo n )