¿Qué es la recursión de cola?
Una función recursiva es recursiva de cola cuando una llamada recursiva es lo último que ejecuta la función. Por ejemplo, la siguiente función de C++ print() es recursiva de cola.
C
// An example of tail recursive function
void print(int n)
{
if (n < 0) return;
cout << " " << n;
// The last executed statement is recursive call
print(n-1);
}
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
<script>
// 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
</script>
¿Por qué nos importa?
Las funciones recursivas de cola se consideran mejores que las funciones no recursivas de cola, ya que el compilador puede optimizar la recursividad de cola. Los compiladores normalmente ejecutan procedimientos recursivos usando una pila . Esta pila consta de toda la información pertinente, incluidos los valores de los parámetros, para cada llamada recursiva. Cuando se llama a un procedimiento, su información se coloca en una pila, y cuando la función termina, la información se extrae de la pila. Por lo tanto, para las funciones no recursivas de cola, la profundidad de la pila(cantidad máxima de espacio de pila utilizado en cualquier momento durante la compilación) es más. La idea utilizada por los compiladores para optimizar las funciones recursivas de cola es simple, dado que la llamada recursiva es la última declaración, no queda nada por hacer en la función actual, por lo que no sirve guardar el marco de pila de la función actual (consulte esto para obtener más información ) . detalles).
¿Se puede escribir una función recursiva sin cola como recursiva de cola para optimizarla?
Considere la siguiente función para calcular el factorial de n. Es una función no recursiva de cola. Aunque parece una cola recursiva a primera vista. Si observamos más de cerca, podemos ver que el valor devuelto por fact(n-1) se usa en fact(n), por lo que la llamada a fact(n-1) no es lo último que hace fact(n)
C++
#include<iostream>
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 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
<?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
<script>
// 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
</script>
120
La función anterior se puede escribir como una función recursiva de cola. La idea es usar un argumento más y acumular el valor factorial en el segundo argumento. Cuando n llega a 0, devuelve el valor acumulado.
C++
#include<iostream>
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
<?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
<script>
// 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
</script>
120
Próximos artículos sobre este tema:
Eliminación de llamadas de cola
QuickSort Optimización de llamadas de cola (reducción del espacio en el peor de los casos para iniciar sesión)
Referencias:
http://en.wikipedia.org/wiki/Tail_call
http://c2.com/cgi/wiki?TailRecursion
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA