Recursie coadă este definită ca o funcție recursivă în care apelul recursiv este ultima instrucțiune care este executată de funcție. Deci practic nu mai rămâne nimic de executat după apelul recursiv.
De exemplu, următoarea funcție C++ print() este recursivă coadă.
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> > |
>
>
Complexitatea timpului: Pe)
Spațiu auxiliar: Pe)
Nevoia recursiunii cozii:
Funcțiile recursive tail sunt considerate mai bune decât funcțiile recursive non-tail, deoarece recursiunea coadă poate fi optimizată de compilator.
Compilatorii execută de obicei proceduri recursive folosind a grămadă . Această stivă constă din toate informațiile pertinente, inclusiv valorile parametrilor, pentru fiecare apel recursiv. Când o procedură este apelată, informațiile acesteia sunt împins pe o stivă, iar când funcția se termină, informațiile sunt a izbucnit din stivă. Astfel, pentru funcțiile non-coada recursive, the adâncimea stivei (cantitatea maximă de spațiu de stivă utilizată în orice moment în timpul compilării) este mai mare.
Ideea folosită de compilatori pentru a optimiza funcțiile recursive de coadă este simplă, deoarece apelul recursiv este ultima instrucțiune, nu mai este nimic de făcut în funcția curentă, așa că salvarea cadrului de stivă a funcției curente nu este de folos (vezi aceasta pentru mai multe Detalii).
Poate fi scrisă o funcție non-recursivă coadă ca recursiv coadă pentru a o optimiza?
Luați în considerare următoarea funcție pentru a calcula factorialul lui n.
Este o funcție non-coada recursivă. Deși pare o coadă recursivă la prima vedere. Dacă aruncăm o privire mai atentă, putem vedea că valoarea returnată de fact(n-1) este folosită în fapt (n) . Deci apelul la fapt (n-1) nu este ultimul lucru făcut de fapt (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>>>>Ieșire120>Complexitatea timpului: Pe)
Spațiu auxiliar: Pe)Funcția de mai sus poate fi scrisă ca o funcție recursivă de coadă. Ideea este să folosiți încă un argument și să acumulați valoarea factorială în al doilea argument. Când n ajunge la 0, returnează valoarea acumulată.
Mai jos este implementarea folosind o funcție recursivă de coadă.
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.>>actor ranbir kapoor varsta>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>>>>>Ieșire120>Complexitatea timpului: Pe)
Spațiu auxiliar: O(1)Următoarele articole pe această temă:
- Eliminarea apelului de coadă
- Optimizare QuickSort Tail Call (reducerea spațiului în cel mai rău caz la Log n )