Recursão em Perl é qualquer função que não usa oforloop ou owhileloop, em vez disso, chama a si mesma durante a execução do programa e a função correspondente é conhecida como função recursiva .

A função recursiva de cauda é um caso especial de recursão em que a instrução de chamada de função é executada como a ação final do procedimento. Então return loop(..);funcionaria, mas return loop() + operation;não funcionaria. A recursão da cauda (ou recursão da extremidade da cauda) é particularmente útil e, muitas vezes, fácil de manusear em implementações. A implementação da recursão final é feita principalmente para evitar o espaço ocupado pela estrutura de dados da pilha que mantém o controle dos dados retornados da instrução de chamada de recursão anterior.

A seguir estão alguns exemplos para uma melhor compreensão do conceito:
 
Exemplos 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); 


Saída:
Fatorial de um número 5 até a recursão é 120
Fatorial de um número 5 até a recursão da cauda é 120



Na versão não final, o compilador precisa controlar o número pelo qual você vai multiplicá-lo, enquanto na versão final, o compilador pode perceber que o único trabalho restante a fazer é outra chamada de função e pode esqueça todas as variáveis ​​e estados usados ​​na função atual.




Exemplos 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); 




Saída:
Fibonacci até 10 através da recursão é 55
Fibonacci até 10 através da recursão da cauda é 55



 
Uso da gotoinstrução para demonstrar Tail Recursion: goto irá transferir o compilador para a sub-rotina do nome fornecido da sub-rotina em execução no momento. Isso substituirá a chamada de função e criará um processo de recursão da mesma maneira.


# 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);




Saída:
recorrente
tail_recursing



No exemplo acima, a recursefunção produzirá um erro fatal de 'recursão profunda' enquanto tail_recursefuncionará bem.


Eliminação da chamada final


O recursivo final é melhor do que o recursivo não final, pois o recursivo final pode ser otimizado por compiladores modernos. O que um compilador moderno faz para otimizar o código recursivo final é conhecido como eliminação de chamada final . A eliminação da chamada final economiza espaço na pilha. Ele substitui uma chamada de função por uma instrução goto . Isso realmente não é eliminação - é uma otimização .


Às vezes, um método profundamente recursivo é a solução mais fácil para um problema, mas se você repetir mais de algumas centenas de chamadas, encontrará o erro de “recursão profunda” do Perl. Essa é a razão pela qual o recursivo de cauda é usado em vez de códigos recursivos de cauda não em Perl.


Se examinarmos mais de perto a função discutida acima, podemos remover a última chamada com goto. Abaixo estão exemplos de eliminação de chamada de cauda.


Exemplos 1: fatorial de um 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); 




Saída:
Fatorial de um número 5 até a recursão da cauda é 120



 
Exemplos 2: Fibonacci até 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); 




Saída:
Fibonacci até 10 através da recursão é 55
Fibonacci até 10 através da recursão da cauda é 55