StackOverFlow error

Question

Below is my code:

public class Solution {
    public double pow(double x, int n) {
        if(n == 0) 
            return 1.0;
        else if(n<0)
            return 1/x * pow(x, n+1);
        else
            return x * pow(x, n-1);
    }
}

I am getting java.lang.StackOverflowError with input (1.00001, 123456).

I tried this code on small inputs and that seemed to work. Im not sure why its erroring with large inputs, is it actually an error with the stack space, and I should use an iterative solution? I saw other posting their solution that seemed to have worked on larger power than 123456....

Thanks in advance.

Comments

Iterative solutions would be better. In this case, you've used 8 * 123456 = 987646 (Byte), which is more than 900MB.

Edit: This revised recursive approach works: http://www.programcreek.com/2012/12/leetcode-powx-n/

Answer 1

If the n is very big, there are too much recursions. Then the stack would be used up. So StackOverflowError be thrown out. In this case, iteration is a better solution compare to recursion. But be careful, if n is extreme huge, you had better to judge if it is really necessary to continue to calculate. For example, pow(1,123456789) is always 1. You had better judge it and return in advanced. Good luck.