printbinary recursive algorithm

Question

I can't wrap my head around how this simple recursive function works:

void printBinary(const int& n)
{
    if(n < 2)
    {
        cout << n;
    }
    else
    {
        printBinary(n / 2);
        printBinary(n % 2);
    }
}

I know it has something to do with n / 2 "chopping" off the last digit of the binary representation and n % 2 yielding such last digit of the binary representation, but when I recursively trace this code it just seems like magic. I can't come up with a simple logical explanation.

Edit: This is a great explanation of the algorithm, and leads me to kind of rephrase my question to: why does n % 2, or the remainder of a decimal number, give you the binary digits of such number. What is the logic behind that?

Do you understand why n % 10 gives you the last base-10 digit? Then n % 2 is the same in base 2. — interjay
– interjay, Commented Feb 22, 2015 at 1:17
Ok so it applies across all bases... I guess its just something you have to take as fact and not ask why the remainder is a digit in the binary representation? — Francisco Aguilera
– Francisco Aguilera, Commented Feb 22, 2015 at 1:24
It's because the number is a0 + 2*a1 + 4*a2 + 8*a3 + ... where a0,a1,... are the binary digits from right to left. If you work out the quotient and remainder by 2, you'll get a1 + 2*a2 + 4*a3 + ... and a0 respectively. — interjay
– interjay, Commented Feb 22, 2015 at 9:20
Makes sense, interjay. Its basically due to the definition of the system how each position is a power of 2. I wish i could mark this as answer... Thanks! — Francisco Aguilera
– Francisco Aguilera, Commented Feb 24, 2015 at 6:54

robert_x44 · Accepted Answer · 2015-02-22 01:44:33Z

For a recursive algorithm, I always find it helpful to quickly write a small example out in a text file with indents to show the recurse levels:

This is an equivalent tree in binary, that may help:

f(101010b)
    f(10101b)
        f(1010b)
            f(101b)
                f(10b)
                    f(1b)  - 1
                    f(0b)  - 0
                f(1b)  - 1
            f(0b)  - 0
        f(1b)  - 1
    f(0b)  - 0

What you'll see from this, is that the first recursive call (n/2) is going to keep dividing by 2 until it finds the most significant bit, the number of times it recurses is the number of bits in the answer. How many times can you divide 42 by 2 before you get to a 1 or 0? 6 times, so there are 6 total bits in the answer.

The next step is less obvious. When you drill down to the next to last level - f(2) or f(10b), what you've done is identified the two most significant digits. Look at a decimal value that might be less confusing.

f(1234)
    f(123)
        f(12)
            f(1)  - 1
            f(2)   - 2
        f(3)  - 3
    f(4)  - 4

When you keep dividing by 10, you always have some number of most significant digits. When you get to the last two digits (12), the first one is 12/10 and the second is 12%10. Going back up a level, (123), you've already recursively taken care of the first two most sig digits, f(12) and now you run f(3) which in the decimal case would be part of the base case (n <10).

Hope this helps

Collectives™ on Stack Overflow

printbinary recursive algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related