Why is there a difference between the following lines of code? (Recursion based question)

Question

Here's the first part:

bool coinChangeFn(vector<int>& coins, int amount, int level, int& result) { 
    if (amount < 0) {
        cout << "Amount is less than 0!" << endl;
        return false;
    }

    if (amount == 0) {
        cout << "Amount is 0. Level is " << level << endl;
        result = min(result, level);
        return true;
    }

    bool flag = false;
    for (auto coin : coins) {
        cout << "Amount: " << amount
             << " Level: " << level
             << " Coin: "  << coin 
             << endl;
        bool temp = coinChangeFn(coins, amount - coin, level + 1, result); // THIS LINE
        flag = flag || temp; // THIS LINE
    }
    return flag;
}

int coinChange(vector<int>& coins, int amount) {
    int result{INT_MAX};
    return coinChangeFn(coins, amount, 0, result) ? result : -1;
}

And here's the second version of the code

bool coinChangeFn(vector<int>& coins, int amount, int level, int& result) {
    if (amount < 0) {
        cout << "Amount is less than 0!" << endl;
        return false;
    }

    if (amount == 0) {
        cout << "Amount is 0. Level is " << level << endl;
        result = min(result, level);
        return true;
    }

    bool flag = false;
    for (auto coin : coins) {
        cout << "Amount: " << amount
             << " Level: " << level
             << " Coin: "  << coin
             << endl;
        flag = flag || coinChangeFn(coins, amount - coin, level + 1, result); // THIS LINE
    }
    return flag;
}

int coinChange(vector<int>& coins, int amount) {
    int result{INT_MAX};
    return coinChangeFn(coins, amount, 0, result) ? result : -1;
}

I've marked the code under question as "THIS LINE" in the comments. I expected them to have the same behavior, however the first version stopped the recursion earlier than expected.

Answer 1

You’re seeing the effect of short-circuit evaluation. In C++, since true || anything is true, if the first operand to || is true, then the second argument isn’t evaluated.

Therefore, if you write

flag = flag || /* recursive call */;

and flag is already true, then no call will be made.

On the other hand, the bitwise OR operator | doesn’t short-circuit. Therefore, if you write

flag |= /* recursive call */;

then the call will always be made.

Answer 2

As noted, the || operator short-circuits. If the first operand is true, the second will not be evaluated. If you wish to make sure it is evaluated, you have to evaluate it and then use the returned value.

int result = coinChangeFn(coins, amount - coin, level + 1, result);
flag = flag || result;