bool returning recursive function alters variable unexpectedly

Question

Could someone explain to me what happens in this? From the little knowledge I have(and clearly I am wrong in my thinking), to me this should keep decreasing x by 1 until x is 3. Then it should go to the 'return true, part and as the function returns true, it goes back to the second if statement, return false and then exit the function since there is nothing to do if the function returns false. But this keeps going back to the second if statement adding 1 to x until it is 9 again and then exits. Thanks in advance.

 bool Rec(int x)
    {
        if( x > 3)
        {
            if(Rec(x - 1) == true)
            {
                return false;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return true;
        }

    }
    void main()
    {
        Rec(9);
    }

@πάνταῥεῖ: Or the whole function body with `return x <= 3;` — too honest for this site, Nov 02 '15 at 18:31
What do you want to accomplish? What do you mean with "alters variable ..."? The recursion here is useless. — too honest for this site, Nov 02 '15 at 18:32
What do you mean "it keeps going back to the second if?". This is the way you programmed it. I take it you're attempting to learn how recursion works? Right idea, bad example. If you print the variable X at the top of the rec function it's actually working how you state. It counts from 9 down to 3 then exits. But that doesn't mean the code is right. The two return false statements with the second if are both returning false. You could therefore just write. Rec(x-1); return false. — hookenz, Nov 02 '15 at 18:42
_@CoconutDug_ Well, stepping through your code using the debugger might give you some enlightenment what's actually going on. — πάντα ῥεῖ, Nov 02 '15 at 18:44
@Matt: Why removed the C tag? I'd say this is more C than C++ (and the signature of `main` is wrong in both languages). — too honest for this site, Nov 02 '15 at 18:50
Yeah it's bad code. bool is c++ only so I removed the c tag. But as it stands it won't compile. Some really old compilers might allow void main() but not a modern one. — hookenz, Nov 02 '15 at 18:59

score 0 · Accepted Answer · edited May 23 '17 at 11:51

Actually I don't see a problem with the way your code functions. It actually works.

It can be simplified and is equivalent to:

#include <stdio.h>

bool Rec(int x)
{
    printf("x = %d\n", x);

    if (x > 3)
    {
        Rec(x - 1);
        return false;
    }

    return true;
}

int main(int argc, char* argv[])
{
    Rec(9);
    return 0;
}

Which produces:

x=9
x=8
x=7
x=6
x=5
x=4
x=3

However you've also said: "But this keeps going back to the second if statement adding 1 to x until it is 9 again and then exits". But you're not actually adding 1 to x. I think what's going on is to do with your debug. You haven't put any debug in your code to print out said behaviour.

So I'll attempt to do it for you.

bool Rec(int x)
{
    printf("x = %d\n", x);

    if (x > 3)
    {
        Rec(x - 1);
        printf("*x = %d\n", x);

        return false;
    }

    return true;
}

Which produces:

x = 9
x = 8
x = 7
x = 6
x = 5
x = 4
x = 3
*x = 4
*x = 5
*x = 6
*x = 7
*x = 8
*x = 9

Think about this carefully. You're not adding 1. Your function is calling itself again printing x = and then if it's greater than 3 doing the same. Only when x > 3 does it return. After it returns it will again print *x = So it's actually printing what x was before the recursive call. I hope that helps you see what's going on.

Your function is fine to see how recursion works. But in practice you'd never write code like that. Because you could just write it as a simple loop.

Avoid recursion if you can come up with code using a loop. But sometimes, recursion is easier. For example, traversing binary trees is really simple with recursion.

There are some answers on this question here which give real world examples of where recursion makes sense. Real-world examples of recursion

Great this is what I was after. Well done for understanding my poorly worded question and thank you very much! — CoconutDug, Nov 02 '15 at 22:43

score -1 · Answer 2 · answered Nov 02 '15 at 18:38

-1

This is the nature of the recursion. You called function 6 times, it is going to return 6 times.

answered Nov 02 '15 at 18:38

SergeyA

61,605
5
78
137

bool returning recursive function alters variable unexpectedly

2 Answers2