Please explain recursive function

[mgoodall]

I understand the concept of recursion, and have written a couple simple recursive functions. I've come across one however, that seems to have challenged what I know. I understand what the function is doing, and the math, but wasn't getting the result I wanted. Someone suggested I move my cout to AFTER the recursive call. I don't understand why.

To my mind, once the function has been recalled, processing moves back up to the beginning of the function. This doesn't work that way. If I move the cout to before the recursive function call, I don't get the same result (which is why I was stuck). I was wondering if someone could explain exactly why I need line 11 after line 10 (my recursive function call). Thanks!

void findBinary(int num)
{
int rem;
if (num <= 1)
{
cout << num;
.	return;
}
rem = num % 2;
findBinary(num / 2);
cout << rem;
}

[MrHutch]

Consider a simple case. Four, of which the binary equivalent is 100.

Personally, it reads a bit easier to me if you only declare rem when you need it.

void findBinary(int num)
{
    if (num <= 1)
    {
        std::cout << num;
        return;
    }

    findBinary(num / 2);
    int rem = num % 2;
    std::cout << rem;
}

Stepping through this case...

findBinary(4)
--> num > 1 
--> findBinary(2)
    --> num > 1
    --> findBinary(1)
        --> num <= 1
        --> print num       (1st print = 1)
    --> rem = 2 % 2 = 0
    --> print rem           (2nd print = 0)
--> rem = 4 % 2 = 0
--> print rem               (3rd print = 0)

Final output = 100

Now, if you moved that rem calculation and print to before the recursion...

findBinary(4)
--> num > 1 
--> rem = 4 % 2 = 0
--> print rem              (1st print = 0)
--> findBinary(2)
    --> num > 1
    --> rem = 2 % 2 = 0
    --> print rem          (2nd print = 0)
    --> findBinary(1)
        --> num <= 1
        --> print num      (3rd print = 1)

Final output = 001

Hope this helps.

[Chervil]

Not sure whether I can explain. My thoughts went in a different direction. The function looked a bit elaborate to me, I wondered whether it could be simplified.
Original function:

void findBinary(int num)
{
    int rem;
    if (num <= 1)
    {
        cout << num;
        return;
    }
	
    rem = num % 2;
    findBinary(num / 2);
    cout << rem;
}

The variable rem stood out. Its use is scattered throughout the function; declared at line 3, a value is assigned at line 10 and then that value is output at line 12. Let's see if we can combine all those three uses into a single line.

void findBinary(int num)
{
    if (num <= 1)
    {
        cout << num;
        return;
    }
	
    findBinary(num / 2);
    cout << num % 2;
}

But then, having two separate cout statements bothered me. Is there a way that they might be combined? Well, that seems unlikely. But, what if we temporarily increase the complexity by changing line 5 to look like line 10. The result is the same.

void findBinary(int num)
{
    if (num <= 1)
    {
        cout << num % 2;
        return;
    }
	
    findBinary(num / 2);
    cout << num % 2;
}

Now it is seen that the only difference between the two outputs is that in one case there is a recursive function call. By changing the if statement, instead of if (num <= 1) consider the complementary condition, if (num > 1).
This looks more complicated, but bear with me a moment.

void findBinary(int num)
{
    if (num <= 1)
    {
        cout << num % 2;
        return;
    }
	
    if (num > 1)
    {
        findBinary(num / 2);
        cout << num % 2;	    
    }
}

Now, since both if statements contain the same cout statement, it can be moved outside of them both like this:

void findBinary(int num)
{
    if (num > 1)
        findBinary(num / 2);

    cout << num % 2;
}

Now it's clearer. If the cout statement is moved to the top, the output is changed, the order of digits is reversed.

I don't know whether this helps, I didn't directly address the original question.

[coder777]

You actually do get the same result. Only the order will be different.

Think about it: Line 11 will be called after the recursion while before line 10 means before the recursion.

You may test it like so:

int index = 0;
void findBinary(int num)
{
int rem;
if (num <= 1)
{
cout << num;
.	return;
}
rem = num % 2;
++index;
int idx = index; // Note a local copy
cout << "Before: " << idx << "\n";
findBinary(num / 2);
cout << "After: " << idx << "\n";
cout << rem;
}

[mgoodall]

Thank you both! That really helps. I thought I understood before, but now I get it. IHutch105, your example was especially helpful!