Why run time error when the base case of recursion is changed?


  • 0
    L

    The following code leads to error message: "Runtime Error Last executed input: 1.00000, -2147483648"
    However, if replacing the line about base case of the recursion "if (n==1) return x" with "if (n==0) return 1.0", then it becomes acceptable. I can't figure out why? It seems to me the two different base bases essentially the same.

    double pow(double x, int n) {
        if (n==0) return 1.0;
        if (n<0)
            return 1.0/pow0(x,-n);
        else
            return pow0(x,n);
    }
    
    double pow0(double x, int n) {
        if (n==1) return x;   //if (n==0) return 1.0; 
    
        double sub_result=pow0(x,n/2);
        if (n%2==1){
            return x*sub_result*sub_result;
        }
        else{
            return sub_result*sub_result;
        }
    }

  • 0
    Z

    I have exactly the same problem. Did you find out the answer?


  • 0
    W

    Hi, this damn case happened to me, too. You got ans to it?


  • 4
    S

    n is -2147483648, -n would be 2147483648. Isn't it overflow?


  • 0
    L

    Oh, I see. Thanks!
    When it is overflow, -n is assigned as 0. That's why it need a base case of n=0.
    Plus it is natural to have the query with n=0. So n=1 is not really the base case, since it does not handle the special case of n=0.


  • 2
    C
    class Solution {
    public:
        double pow(double x, int n) {
            if (x==1) return 1;
            if (x==-1){
                if (n%2) return -1;
                else return 1;
            }
            
            if (n<0) return(1/(pow(x,-n)));
            if(n==0) return 1;
            if (n%2==1) return(pow(x*x,n/2)*x);
            else return(pow(x*x,n/2));
                         
        }
    };
    

    you could write the condition for 1 and -1. then the code will work.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.