Professional Perl | 9

[previous] [next]

Professional Perl

Recursion

Recursion happens when a subroutine calls itself, either directly, or indirectly, via another subroutine (also known as mutual recursion). For example, consider this subroutine that calculates the Fibonacci sequence up to a specified number of terms:

#!/usr/bin/perl 
# fib1.pl
use warnings;
use strict;
sub fibonacci1 {
   my ($count, $aref) = @_;
   unless ($aref) {
      # first call - initialize
      $aref = [1,1];
      $count -= scalar(@{$aref});
      }
      $aref = [1,1] unless $aref;
      if ($count--) {
         my $next = $aref->[-1] + $aref->[-2];
         push @{$aref}, $next;
         return fibonacci1($count, $aref);
      } else {
         return wantarray?@{$aref}: $aref->[-1];
      }
}
# calculate 10th element of standard Fibonacci sequence
print scalar(fibonacci1(10)), "\n";
# calculate 10th element beyond sequence starting 2, 4
print scalar(fibonacci1(10, [2, 4])), "\n";
# return first ten elements of standard Fibonacci sequence
my @sequence = fibonacci1(10);
print "Sequence: @sequence \n";

Each time the subroutine is entered, it calculates one term, decrements the counter by one and calls itself to calculate the next term. The subroutine takes two arguments, the counter, and a reference to the list of terms being calculated. (As a convenience, if we don't pass in a reference the subroutine initializes itself with the start of the standard Fibonacci sequence, 1, 1). We pass in a reference to avoid copying the list repeatedly, which is wasteful. When the counter reaches zero, the subroutine exits without calling itself again, and returns either the whole list or the last term, depending on how it was called.

This is an example of forward recursion, where we start at the beginning of the task and work our way towards the end. Elements are calculated one by one as we continue with our recursion. An alternative way of doing the same job is to use reverse recursion, which starts by trying to calculate the last term first:

#!/usr/bin/perl 
# fib2.pl
use warnings;
use strict;
sub fibonacci2 {
   my ($count, $internal) = @_;
                    
   if ($count [-1] + $result->[-2];
                    
      if ($internal) {
         push @{$result}, $next;
         return $result;
      } else {
         return $next;
      }     
   }
}               
                
foreach (1..20) { 
   print "Element $_ is ", fibonacci2($_), "\n";
}

This time the subroutine starts by trying to work out the last term, starting at the end, and reversing back towards the beginning until we can determine the answer without a further call. If the requested term is the first or second, we just return the result, otherwise, it needs to work out the terms prior to the one we have been asked for, which it does by calling itself for the previous terms. In this model, we descend rapidly to the bottom of the recursion stack until we get the answer '[1,1]'. We then calculate each new term as we return back up.

Reverse recursion is not as obvious as forward recursion, but can be a much more powerful tool, especially in algorithms where we do not know in advance exactly how the initial known results will be found. Problems like the Queen's Dilemma (placing eight queens on a chessboard such that no Queen can take another) are more easily solved with reverse recursion, for example.

Both approaches suffer from the problem that Perl generates a potentially large call stack. If we try to calculate a sufficiently large sequence then Perl will run out of room to store this stack and will fail with an error message:

Deep recursion on subroutine "main::fibonacci2" at ...

Some languages support 'tail' recursion, an optimization of forward recursive subroutines where no code exists after the recursive subroutine call. Because there is no more work to do at the intermediate levels of the subroutine stack, they can be removed. This allows the final call to the recursed subroutine call to directly return to the original caller. Since no stack is maintained, no room is needed to store it.

Perl's interpreter is not yet smart enough to figure out this optimization automatically, but we can code it explicitly using a goto statement. The fibonnaci1 subroutine we showed first is a recursive subroutine that fits the criteria for 'tau' recursion, as it returns. Here is a modified version, fibonacci3 that uses goto to avoid creating a stack of recursed subroutine calls. Note that the goto statement and the line immediately before it are the only difference between this subroutine and fibonacci1:

#!/usr/bin/perl 
# fib3.pl
use warnings;
use strict;
sub fibonacci3 {
   my ($count, $aref) = @_;
   unless ($aref) {
   # first call - initialize
   $aref = [1,1];
   $count -= scalar(@{$aref});
   }
   if ($count--) {
      my $next = $aref->[-1] + $aref->[-2];
      push @{$aref}, $next;
      @_ = ($count, $aref);
      goto &fibonacci3;
   } else {
      return wantarray?@{$aref}:$aref->[-1];
   }
}
# calculate 1000th element of standard Fibonacci sequence
print scalar(fibonacci3(1000)), "\n";

The goto statement jumps directly to another subroutine without actually calling it (which creates a new stack frame). The automatic creation of a localized @_ does not therefore happen. Instead, the context of the current subroutine call is used, including the current @_. In order to 'pass' arguments we therefore have to predefine @_ before we call goto. Examining the code above, we can see that although it would sacrifice legibility, we could also replace $count with $_[0] to set up @_ correctly without redefining it.

Recursion is a nice programming trick, but it is easy to get carried away with it. Any calculation that uses recursion can also be written using ordinary iteration too, so use recursion only when it presents the most elegant solution to a programming problem.

[previous] [next]