1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

Iterative Function To Find X to the power N

Discussion in 'Perl' started by pradeep, Mar 14, 2008.

  1. pradeep

    pradeep Team Leader

    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.
     
  2. rai_gandalf

    rai_gandalf New Member

    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
     

Share This Page