Design a recursive algorithm for computing 2^n for any non-negative integer n by the formula 2^n = 2^(n-1) + 2^(n-1). Prerequisites : There must be an addition operation perform
int computepowerOfTwo(int power) {
if(power == 1)
return 1;
else
return (2*computepowerOfTwo(power-1)) + (2*computepowerOfTwo(power-1))
}
When I supply power as 3 initially it returns 16
As the other answer points out 2^1 is 2, not 1.
... but your code should actually stop at 0 instead:
if(power == 0)
return 1;
This is a good opportunity to learn the value of unit testing. A simple test case of the following...
for i in range(0, 11):
assert computepowerOfTwo(i) == 2 ** i
...would show you that (1) you didn't handle the case of 0 and (2) your answer for 2^1 was wrong.
Errors in your code:-
if(power == 1) you should return 2^1 which is 2.else part what you are returning is equivalent to 2*2^(power-1) + 2*2^(power-1) which will result 2^(n+1) which is wrong, so you should just return 2*2^(power-1)According to your question your function should be as follow:-
int computepowerOfTwo(int power) {
if(power == 0)
return 1;
else
return computepowerOfTwo(power-1) + computepowerOfTwo(power-1);
}
