Recurs de la cua es defineix com una funció recursiva en la qual la crida recursiva és l'última instrucció que la funció executa. Així, bàsicament, no queda res per executar després de la crida de recursivitat.
Per exemple, la següent funció C++ print() és recursiva a la cua.
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> |
>
>
Python 3
# 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> > |
>
>
Complexitat temporal: O(n)
Espai auxiliar: O(n)
Necessitat de recurs a la cua:
Les funcions recursives de cua es consideren millors que les funcions recursives no de cua, ja que el compilador pot optimitzar la recursivitat de la cua.
Els compiladors solen executar procediments recursius mitjançant a pila . Aquesta pila consta de tota la informació pertinent, inclosos els valors dels paràmetres, per a cada trucada recursiva. Quan es crida un procediment, la seva informació és empès a una pila, i quan la funció finalitza la informació és va esclatar fora de la pila. Així, per a les funcions no recursives de la cua, el profunditat de la pila (la quantitat màxima d'espai de pila utilitzat en qualsevol moment durant la compilació) és més.
La idea que fan servir els compiladors per optimitzar les funcions recursives de la cua és senzilla, ja que la crida recursiva és l'última instrucció, no hi ha res a fer a la funció actual, de manera que desar el marc de pila de la funció actual no serveix de res (vegeu això per a més informació). detalls).
Es pot escriure una funció no recursiva a la cua com a recursiva a la cua per optimitzar-la?
Considereu la funció següent per calcular el factorial de n.
És una funció no recursiva de la cua. Encara que a primera vista sembla una cua recursiva. Si mirem més de prop, podem veure que s'utilitza el valor retornat per fact(n-1). fet (n) . Així que la crida a fet (n-1) no és l'últim que ha fet fet (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.> |
>
>
Python 3
# 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> > |
>
>Sortida
120>
Complexitat temporal: O(n)
Espai auxiliar: O(n)
La funció anterior es pot escriure com una funció recursiva de la cua. La idea és utilitzar un argument més i acumular el valor factorial en el segon argument. Quan n arriba a 0, retorna el valor acumulat.
A continuació es mostra la implementació mitjançant una funció recursiva de cua.
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.> |
>
conté python
>
Python 3
# 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> > > |
>
>Sortida
120>
Complexitat temporal: O(n)
Espai auxiliar: O(1)
Pròxims articles sobre aquest tema:
- Eliminació de trucades de cua
- Optimització de trucades a la cua QuickSort (reduint l'espai en el pitjor dels casos a Log n )