Returns in Recursive Function in C++

Question

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?

did u step through in a debugger? Then u can see whats happening — pm100, Aug 25 '15 at 22:36
I think you should have `return testing(i)`. The way it is it calls `testing()` but it continues through and returns false. — Hanlet Escaño, Aug 25 '15 at 22:36
As an optimization note, you're better off doing `if((i&1)==0)` instead of `if((i%2)==0)`. Also better off doing `return testing(i-1)` instead of `--i ; return resting(i)`, though the optimizer will optimize that one out anyway. — iAdjunct, Aug 25 '15 at 22:38
@iAdjunct `i&1` and `i%2` are not equivalent for negative numbers. — Neil Kirk, Aug 26 '15 at 01:51
@NeilKirk - Good point. I interpreted his test as "checking for odd numbers," in which case this is what he wants, but they are different. Interestingly, though, I just checked: `((-3)%2)` in C++ and Swift give `-1`, but python 2.7.10 gives `1`. — iAdjunct, Aug 26 '15 at 03:38
@iAdjunct The sign of a modulus operation using negative numbers is defined differently between languages and before C++11 was implementation-defined as well. — Neil Kirk, Aug 26 '15 at 03:45

score 5 · Answer 1 · answered Aug 25 '15 at 22:36

5

You should return testing(i); instead of just testing(i);

answered Aug 25 '15 at 22:36

Kan Li

8,557
8
53
93

Yes it is unreachable. That's a separate issue though. – Kan Li Aug 25 '15 at 22:50

score 1 · Accepted Answer · edited May 23 '17 at 11:44

1

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

edited May 23 '17 at 11:44

Community

1
1

answered Aug 25 '15 at 22:58

Ziezi

6,375
3
39
49

1

By optimizing you mean remove the curly brackets? You also don't need the last `else`. – Emz Aug 25 '15 at 23:48
@Emz you are right, the code is written more clearly and concisely, not optimized and the `else` is, indeed, not needed. Thanks :) – Ziezi Aug 26 '15 at 08:49
I recommend having a read at http://stackoverflow.com/questions/8020228/is-it-ok-if-i-omit-curly-braces-in-java this question. – Emz Aug 26 '15 at 10:07
@Emz (personal opinion) _curly braces_ could be omitted if there is a single statement which could be put in the same line, after the _flow control statement_. There are some examples in "the books" omitting _curly braces_ and using _indentation_ on the next line "python style", but that is really ambiguous. If there is a larger _block of code_ it should be enclosed. – Ziezi Aug 26 '15 at 13:37

Sakib Ahammed · Answer 3 · 2015-08-25T22:41:34.613

0

Because of you only call testing(i) function. That's why it's not call recursively.

you should write return testing(i)

edited Aug 25 '15 at 22:41

answered Aug 25 '15 at 22:38

Sakib Ahammed

2,452
2
25
29

score 0 · Answer 4 · answered Aug 25 '15 at 22:39

0

You don't bubble up the final return value; you need to use return on the recursive call. Additionally, you can simplify the pre-decrement:

return testing(--i);

answered Aug 25 '15 at 22:39

Olipro

3,489
19
25

score 0 · Answer 5 · answered Jan 04 '20 at 17:01

0

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

answered Jan 04 '20 at 17:01

batabek

511
2
5
15

Returns in Recursive Function in C++

5 Answers5

Linked