Iterative Function To Find X to the power N

In rashida.par's Recursive function to find X to the power n (http://www.go4expert.com/showthread.php?t=9307) I see that she intelligently used recursion to find the power of x to n. So, I was wondering whether we can do this iteratively also, I always do that - trying to find a iterative solution to a recursive one.

Being more of a Perl programmer than C, I wrote my code in Perl - can be understood by any programmer. I also benchmarked the recursive function to the iterative version.

The Iterative Solution

Code:

 sub power_iterative
 {
     my ($x,$n) = @_; ## take in parameters
     my $result = 1;
 
     while($n--)
     {
         $result *= $x;
     }
 
     return $result;
 }
 

Test run of the code:

Code:

 printf("\n %.4f to the power of % d is %.4f",$x,$n,power_iterative($x,$n));
 

Code:

 [pradeep@go4expert perl_test]$ perl power_iterative.pl
 
  4.0000 to the power of  10 is 1048576.0000
 

Benchmarking

I also benchmarked the recursive function to the iterative version to see which one performs better.

Code:

 use Benchmark;
 
 sub power_iterative
 {
     my ($x,$n) = @_; ## take in parameters
     my $result = 1;
 
     while($n--)
     {
         $result *= $x;
     }
 
     return $result;
 }
 
 sub power_recursive
 {     
     my ($x,$n) = @_; ## take in parameters
     
     if ($x==0)     
     {         
         return 0;     
     }     
     elsif($n==0)     
     {         
         return 1;     
     }     
     elsif ($n>0)     
     {         
         return( $x* power_recursive($x,$n-1));     
     }     
     else     
     {         
         return ((1/$x)*power_recursive($x,$n+1));     
     } 
 }
 
 my ($x,$n) = (4,10);
 
 timethese(400000,{
 'iterative'=> sub{my $power = power_iterative($x,$n);},
 'recursive'=> sub{my $power = power_recursive($x,$n);}});
 

Result:

Code:

 [pradeep@go4expert perl_test]$ perl power_iterative.pl
 Benchmark: timing 400000 iterations of iterative, recursive...
  iterative:  2 wallclock secs ( 1.28 usr +  0.00 sys =  1.28 CPU) @ 312500.00/s (n=400000)
  recursive:  6 wallclock secs ( 5.90 usr +  0.00 sys =  5.90 CPU) @ 67796.61/s (n=400000)
 

As we see here, the iterative version performs much better than the recursive one, the reason being the recursive version need more memory for function call stacks etc.

I hope this was helpful to you all.

 

As was evident from the Recursive implementation, there was tail recursion, which is both redundant & inefficient. Tail recursion must always be replaced with a more efficient, easier to comprehend iterative counter-part, as you have done here.

Only, you have done it in Perl - a language which I do not know much about - so I got to learn the basics of a new language as well!

Regards,
Rajiv