Reputation: 361

Returns in Recursive Function in C++

I'm a little confused here. Let's look at the following code:

bool testing(int i) {

    if((i%2)==0) {
        return true;
    } else {
        --i;
        testing(i);
    }
    return false;
}

When I do testing(5), I was expecting the function to return true because at some point, 5 will become 4, so 4 % 2 == 0, so the function will return true but it just wasn't the case. What's wrong?

Upvotes: 1

Answers (5)

batabek

Reputation: 541

it returns false because its return value is overridden by the last statement of "return false".

Upvotes: 0

Ziezi

Reputation: 6467

The idea of recursion is when a function calls itself, directly or indirectly.
The function in your code will become recursive if it is modified to:

bool testing(int i){
    // test if even, if so return true
    if((i % 2) == 0){
        return true;
    // otherwise decrement and test again
    }else{
        // at this point the function calls itself with decremented argument
        return testing(--i);
    }
    // I doubt that this case will be ever returned  
    // more likely your function will return "true" or run "forever" decrementing
    return false;
}

To avoid infinite cycles you need a base case, termination condition that produces result without recursion.
For example if i becomes very small or negative you return false.

bool testing(int i){
    // base case
    if(i < 0) return false;
    // rest of the function
    if((i % 2) == 0){
        return true;
    }else{
        return testing(--i);
    } 
}

Making it a bit more concise, you finally have three cases:

bool testing(int i){
    // base case
    if(i < 0) return false;
    // test if even
    if((i % 2) == 0) return true;
    // recursion step
    return testing(--i);
}

For further reading, check this

Upvotes: 1