recursive function calling in c++

Question

Whats the difference between

return(checkBst(root->left, minvalue, root) && checkBst(root->right, root, maxvalue));

and

return(checkBst(root->left, minvalue, root));
return(checkBst(root->right, root, maxvalue));

My whole programme looks like this

bool checkBst(node *root, node * minvalue, node * maxvalue){
    if(root == NULL){
        return true;
    }
    if((minvalue && root->data <= minvalue->data) || (maxvalue && root->data >= maxvalue->data)){
        return false;
    }
    return(checkBst(root->left, minvalue, root) && checkBst(root->right, root, maxvalue));
    // return(checkBst(root->left, minvalue, root));
    // return(checkBst(root->right, root, maxvalue));
}

user_4116465 · Answer

To be frank, you cannot have a return for each of the function calls. This is because return is the last statement executed in a function before the control is given back to the calling function.

In your case, the second function is NEVER called. So, if your first function returns true, it never calls the 2nd function. Had the 2nd function result been false, the answer you get will be erroneous.

You still need to have a return statement at the end of both statements and capture the value returned by the functions.

I mean this statement:

return(checkBst(root->left, minvalue, root) && checkBst(root->right, root, maxvalue));

is equal to:

ret1 = checkBst(root->left, minvalue, root);
if(ret1)
    return checkBst(root->right, root, maxvalue);
else
    return false;

Recursion is not about putting everything in one line. That is just a coding style. The Comment by Pepijn Kramer and Some programmer dude talk about the optimization that you can get with writing in the same line. If the 1st half is false, you don't need to evaluate the 2nd half and that saves computation time and energy.

Recursion is about doing repetitive tasks by calling the same function within itself and using the result of it to give the final result.

In your case, Initially you send the whole tree. Then you divide the problem into 2 halves by calling the function for each of the sub-trees.

In each function call you take care of the terminal conditions. That is the first and second lines that you have. Those are the only cases where you don't call more functions. You are getting a return value.

Now, this return value should be propagated back to the calling function

recursive function calling in c++

1 Answers