The Power of Recursion

Unlike C/C++, Java, etc. Perl provides an exponentiation operator, **, so $y = $x ** $n calculates $x raised to the $n power. If $n is not an integer, this is undoubtedly calculated using logarithms. If $n is a positive integer, the most straightforward way to calculate the nth power is using a loop:

sub power {
  my( $x, $n ) = @_;
  
  my( $ret_val ) = 1;
  foreach (1..$n) { $ret_val *= $x; }
  return $ret_val;
}

A little experimentation with this will show that it is too slow to be used when $n is large. For example, if $n == 1000 it takes 1000 multiplications.

We can write a faster version using the following two facts that hold when $n is a positive integer:

• If $n is even, then $x ** $n is the same as the square of $x ** ($n/2).
• If $n is odd, then $x ** $n can be calculated as $x times the square of $x ** (($n-1)/2)

Putting these together gives the recursive function:

sub power {
  my( $x, $n ) = @_;
  
  if ($n < 1) { return 1; }
  if ($n < 2) { return $x; }
  my( $half_n ) = int( $n / 2 );
  my( $half_power ) = &power( $x, $half_n );
  my( $ret_val ) = $half_power * $half_power;
  if ( $n % 2 == 0 ) { return $ret_val; }
  return $ret_val * $x;
}

When $n == 1000 this only takes 14 multiplications.

Note that there's nothing magic about recursion. The following version is also recursive:

sub power {
   my( $x, $n ) = @_;
   
   if ($n < 1) { return 1; }
   if ($n < 2) { return $x; }
   my( $half_n ) = int( $n / 2 );
   my( $ret_val ) = &power( $x, $half_n ) * &power( $x, $half_n );
   if ( $n % 2 == 0 ) { return $ret_val; }
   return $ret_val * $x;
 }