Go4Expert (http://www.go4expert.com/)
-   Perl (http://www.go4expert.com/articles/perl-tutorials/)
-   -   Iterative Function To Find X to the power N (http://www.go4expert.com/articles/iterative-function-x-power-n-t9342/)

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: Perl

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

Test run of the code:
Code: Perl

`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: Perl

`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.

 rai_gandalf 8Apr2008 00:18

Re: Iterative Function To Find X to the power N

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

 All times are GMT +5.5. The time now is 15:09.