La recursión en Perl es cualquier función que no utiliza elforbucle o elwhilebucle, sino que se llama a sí misma durante la ejecución del programa y la función correspondiente se conoce como función recursiva .
La función recursiva de cola es un caso especial de recursividad en el que la declaración de llamada de función se realiza como la acción final del procedimiento. Entonces return loop(..);funcionaría, pero return loop() + operation;no lo haría. La recursión de cola (o recursión de cola) es particularmente útil y, a menudo, fácil de manejar en las implementaciones. La implementación de la recursión de cola se realiza principalmente para evitar el espacio ocupado por la estructura de datos de la pila que realiza un seguimiento de los datos devueltos por la instrucción de llamada de recursión anterior.
Los siguientes son algunos ejemplos para una mejor comprensión del concepto:
Ejemplos 1:
#!/usr/bin/perl
# Perl Program to calculate Factorial
# Recursion without tail call
sub recurse_fact
{
my $x = $_[0];
# checking if that value is 0 or 1
if ($x == 0 || $x == 1)
{
return 1;
}
# Recursively calling function with
# the next value which is one less
# than current one
else
{
return $x * recurse_fact($x - 1);
}
}
# Recursion using Tail Call
sub tail_recurse_fact
{
my ($ans, $x) = @_;
# checking if that value is 0 or 1
if ($x == 0 || $x == 1)
{
return $ans;
}
# Recursively calling function with
# the next value which is one less
# than current one
else
{
return tail_recurse_fact($ans * $x, $x - 1);
}
}
# Driver Code
$a = 5;
# Function call and printing result after return
print "Factorial of a number $a ",
"through recursion is ", recurse_fact($a);
print "\nFactorial of a number $a ",
"through tail-recursion is ",
tail_recurse_fact(1, $a);
Factorial of a number 5 through recursion is 120 Factorial of a number 5 through tail-recursion is 120
En la versión sin cola, el compilador necesita realizar un seguimiento del número con el que lo va a multiplicar, mientras que en la versión de llamada de cola, el compilador puede darse cuenta de que el único trabajo que queda por hacer es otra llamada de función y puede olvídese de todas las variables y estados utilizados en la función actual.
Ejemplos 2:
#!/usr/bin/perl
# Perl program to demonstrate the
# use of tail-recursion
use strict;
use warnings;
sub recurse_fib
{
my $n = shift;
if ($n == 1 or $n == 2)
{
return 1
}
# recursive calling
return (recurse_fib($n - 1) +
recurse_fib($n - 2));
}
sub tail_recurse_fib
{
my ($n, $a, $b) = @_;
if ($n == 1)
{
return $a
}
if ($n == 2)
{
return $b
}
else
{
# tail recursive calling
return tail_recurse_fib($n - 1, $b, $a + $b)
}
}
# Driver code
$a = 10;
print "Fibonacci upto $a through recursion is ",
recurse_fib($a);
print "\nFibonacci upto $a through tail-recursion is ",
tail_recurse_fib($a, 1, 1);
Fibonacci upto 10 through recursion is 55 Fibonacci upto 10 through tail-recursion is 55
Uso de gotola declaración para demostrar Tail Recursion: goto transferirá el compilador a la subrutina del nombre dado desde la subrutina que se está ejecutando actualmente. Esto reemplazará la llamada a la función y creará un proceso de recurrencia de la misma manera.
# Perl program to demonstrate the
# use of tail-recursion
use warnings;
sub recurse
{
my $i = shift;
return if $i == 0;
recurse($i - 1);
}
sub tail_recurse
{
my $i = shift;
return if $i == 0;
@_ = ($i - 1);
goto &tail_recurse;
}
# Driver Code
print "recursing\n";
recurse(200);
print "tail_recursing\n";
tail_recurse(200);
Producción:
recursing tail_recursing
En el ejemplo anterior, la recursefunción producirá un error fatal de ‘recurrencia profunda’ mientras tail_recurseque funcionará bien.
Eliminación de Tail Call
La cola recursiva es mejor que la no cola recursiva, ya que los compiladores modernos pueden optimizar la cola recursiva. Lo que hace un compilador moderno para optimizar el código recursivo de cola se conoce como eliminación de llamada de cola . La eliminación de llamadas de cola ahorra espacio en la pila. Reemplaza una llamada de función con una instrucción goto . Esto realmente no es eliminación, es una optimización .
A veces, un método profundamente recursivo es la solución más fácil para un problema, pero si recurre a más de un par de cientos de llamadas, se encontrará con el error de «recurrencia profunda» de Perl. Esa es la razón por la cual se usa cola recursiva sobre códigos no recursivos de cola en Perl.
Si echamos un vistazo más de cerca a la función discutida anteriormente, podemos eliminar la última llamada con goto. A continuación se muestran ejemplos de eliminación de llamadas de cola.
Ejemplos 1: Factorial de un número
#!/usr/bin/perl
# Perl Program to calculate Factorial
sub tail_recurse_fact
{
my $ans = shift;
my $x = shift;
# checking if that value is 0 or 1
if ($x == 0 || $x == 1)
{
return $ans;
}
# Recursively calling function with
# the next value which is one less
# than current one
else
{
@_ = ($x * $ans, $x - 1);
goto &tail_recurse_fact;
}
}
# Driver Code
$a = 5;
# Function call and printing result after return
print "Factorial of a number $a ",
"through tail-recursion is ",
tail_recurse_fact(1, $a);
Factorial of a number 5 through tail-recursion is 120
Ejemplos 2: Fibonacci hasta n
#!/usr/bin/perl
# Perl program to demonstrate the
# use of tail-recursion-elimination
use strict;
use warnings;
sub tail_recurse_fib
{
my $n = shift;
my $a = shift;
my $b = shift;
if ($n == 1)
{
return $a
}
if ($n == 2)
{
return $b
}
else
{
@_ = ($n - 1, $b, $a + $b);
# tail recursive calling
goto &tail_recurse_fib;
}
}
# Driver code
$a = 10;
print "Fibonacci upto $a through tail-recursion is ",
tail_recurse_fib($a, 1, 1);
Fibonacci upto 10 through recursion is 55 Fibonacci upto 10 through tail-recursion is 55
Publicación traducida automáticamente
Artículo escrito por BhavikBothra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA