CODEWITHSUNDEEP
javarecursionreturnbinary-treereturn-type
David Tamrazov
David Tamrazov

Reputation: 597

Recursive return error, Java

So I'm defining a recursive function that takes as an argument a value for x (like the arithmetic variable x, i.e. "x + 3 = 5") and returns the result of the arithmetic expression. The expression is taken from a Binary expression tree that looks like this: enter image description here

You start at the root and keep working your way down till you hit the leaves, and once you do you come back up. The expression on the tree is then:

x * ( (x + 2) + cos(x-4) ).

My code for this function is as follows:

     // Returns the value of the expression rooted at a given node
// when x has a certain value
double evaluate(double x) {
    if (this.isLeaf()) {
        //convert every instance of 'x' to the specified value
        if (this.value.equals("x")) {
            this.value = Double.toString(x);
        }
        //return the string-converted-to-double

        return Double.parseDouble(this.value);
    }
    //if-else statements to work as the arithmetic operations from the tree. Checks the given node and performs the required operation
    else {
        if(this.value.equals("sin")) { return Math.sin(evaluate(Double.parseDouble(this.leftChild.value))); }
        if(this.value.equals("cos")) { return Math.cos(evaluate(Double.parseDouble(this.leftChild.value))); }
        if(this.value.equals("exp")) { return Math.pow(evaluate(Double.parseDouble(this.leftChild.value)), evaluate(Double.parseDouble(this.rightChild.value))); }
        if(this.value.equals("*")) { return evaluate(Double.parseDouble(this.leftChild.value)) * evaluate(Double.parseDouble(this.rightChild.value)); }
        if(this.value.equals("/")) { return evaluate(Double.parseDouble(this.leftChild.value)) / evaluate(Double.parseDouble(this.rightChild.value)); }
        if(this.value.equals("+")) { return evaluate(Double.parseDouble(this.leftChild.value)) + evaluate(Double.parseDouble(this.rightChild.value)); }
        if(this.value.equals("-")) { return evaluate(Double.parseDouble(this.leftChild.value)) - evaluate(Double.parseDouble(this.rightChild.value)); }
    }
}

However the compiler is tossing an error telling me that my function must return a type double. Both the if and the else statements return a double- the if statement directly and the else statement through the sum of 2 doubles returned by the same function. What is the deal here? If I place a return statement outside of the if-else then the error resolves itself but to work with that would require me to keep a static or a global variable consistent through each recursion. I'd like to know what is wrong with my function as is, because it feels much more intuitive than a global variable and I think I'm missing a key concept about recursion here. Any help is appreciated- thank you!

Upvotes: 2

Views: 646

Answers (1)

resueman
resueman

Reputation: 10613

Both the if and the else statements return a double

They actually don't. The if branch always does, but the else branch doesn't. What happens if this.value equals "Invalid", or something else which isn't in your list? Then it won't ever hit a return statement. Since it's required to always return, or throw an exception, this isn't allowed.

Even if you have your program structured in such a way that it logically always has to return a value, the compiler isn't going to be doing complex analysis on all the branches of your program to ensure that it always returns something. It just checks that each branch has a valid return.

So, for example, something like is invalid

if(x < 0)  return -1;
if(x >= 0) return 1;

Because the compiler doesn't know that it always has to hit one of those two conditions (an issue which is further complicated by the fact that, depending on what x is, it might not always have to go down one of those branches).

Instead, your code should be structured like this:

if(x < 0) return -1;
else      return 1;

So that every branch has a valid exit condition.

Upvotes: 6

Related Questions