c++ – While calculating x^n using recursion a test case fails with following error?
Quesion: Question Link
The question is to calculate the power of x to n where n can be in
range :-2^31 <= n <= 2^(31-1)
But for certain test case code seems to give stack overflow error:
Test Case for which the code fails:
x = 0.00001
n = 2147483647
==31==ERROR: AddressSanitizer: stack-overflow on address 0x7ffe5053aff8 (pc 0x000000343a6a bp 0x7ffe5053b010 sp 0x7ffe5053b000 T0)
==31==ABORTING
How can I handle the stack overflow in this ?
MYCODE:
double myPow(double x, long long n) {
double res;
// long long nn=abs(n);
// BC
if(n==0)
return 1;
if(x==0)
return 0;
res=myPow(x,abs(n)-1);
return n<0?1/(x*res):x*res;
}
Here I changed the data type of the n which was initially int to counter the overflow issue.
If there is any other way too counter that do tell?
Also I had written the optimised version of Code which any more improvements that can be made is appreciated..
Optimised Code:
double myPow(double x, int n) {
double res;
long long nn=abs(n);
// BC
if(n==0)
return 1;
if(x==0)
return 0;
if(nn%2==0){
res=myPow(x,nn/2);
res=res*res;
return n<0?1/res:res;
}
else {
res=myPow(x,nn-1);
return n<0?1/(x*res):x*res;
}
}
Read more here: Source link