Ce este Tail Recursion
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șire
120Complexitatea 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.>
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șire
120Complexitatea 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 )
