# Iterative Function To Find X to the power N

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

Joined:
Apr 4, 2005
Messages:
1,645
87
Trophy Points:
0
Occupation:
Programmer
Location:
Kolkata, India
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_gandalfNew Member

Joined:
Nov 4, 2005
Messages:
46
1
Trophy Points:
0
Occupation:
Final Year Comp Engg
Location:
Mumbai