Astes rekursija ir definēta kā rekursīva funkcija, kurā rekursīvais izsaukums ir pēdējais priekšraksts, ko funkcija izpilda. Tātad būtībā pēc rekursijas izsaukuma nekas nav jāizpilda.
Piemēram, šī C++ funkcija print() ir rekursīva.
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> > |
>
>
Laika sarežģītība: O(n)
Palīgtelpa: O(n)
Nepieciešamība pēc astes rekursijas:
Astes rekursīvās funkcijas tiek uzskatītas par labākām nekā nerekursīvās funkcijas, jo kompilators var optimizēt astes rekursijas funkcijas.
Kompilatori parasti izpilda rekursīvās procedūras, izmantojot a kaudze . Šī kaudze sastāv no visas atbilstošās informācijas, tostarp parametru vērtībām, katram rekursīvajam izsaukumam. Kad tiek izsaukta procedūra, tās informācija ir pagrūda uz steku, un, kad funkcija beidzas, informācija ir izlēca ārā no kaudzes. Tādējādi ne-rekursīvajām funkcijām, skursteņa dziļums (maksimālais steka vietas daudzums, kas tiek izmantots jebkurā laikā kompilācijas laikā) ir vairāk.
Ideja, ko kompilatori izmanto, lai optimizētu astes rekursīvās funkcijas, ir vienkārša, jo rekursīvais izsaukums ir pēdējais priekšraksts, pašreizējā funkcijā nekas nav jādara, tāpēc pašreizējās funkcijas steka rāmja saglabāšana nav lietderīga (vairāk skatiet šeit detaļas).
Vai ne-rekursīvu funkciju var uzrakstīt kā astes rekursīvu, lai to optimizētu?
Apsveriet šādu funkciju, lai aprēķinātu n faktoriālu.
Tā ir ne-rekursīva funkcija. Lai gan no pirmā acu uzmetiena izskatās kā aste rekursīvs. Ja mēs to aplūkojam tuvāk, mēs varam redzēt, ka tiek izmantota vērtība, ko atgriež fakts(n-1). fakts(n) . Tātad aicinājums uz fakts (n-1) nav pēdējais, ko paveicis fakts(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>>>>Izvade120>Laika sarežģītība: O(n)
Palīgtelpa: O(n)Iepriekš minēto funkciju var uzrakstīt kā astes rekursīvu funkciju. Ideja ir izmantot vēl vienu argumentu un uzkrāt faktoriālo vērtību otrajā argumentā. Kad n sasniedz 0, atgrieziet uzkrāto vērtību.
Tālāk ir sniegta ieviešana, izmantojot astes rekursīvo funkciju.
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.>>javascript ielādes skripts>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>>>>>Izvade120>Laika sarežģītība: O(n)
Palīgtelpa: O(1)Nākamie raksti par šo tēmu:
- Astes izsaukuma likvidēšana
- QuickSort Tail Call optimizācija (sliktākā gadījuma vietas samazināšana žurnālam n )