C++ and Recursive functions

[Saint Nick]

All I know about this function is that it is recursive. It converts decimal to binary. And the if statement says if 0 is 0, then its 0 in binary, and if its 1, then its 1 in binary. Other than that, I don't know how the recursive part of the function works, and I don't know what a bitshift is. I read a definition of it, but it doesn't make sense.

Could someone please explain to me how this particular function works, regarding the function as a whole, with recursion, and the bitshift?

 

[notfred]

This doesn't convert decimal to binary, it just prints numbers in binary.

Really, every number in the computer is represented in binary. If you don't understand binary, go read up on it now before reading the rest of this explanation.

Ok, since you're reading this line, you must understand binary. Let's take a number... we'll use 44 as our example.
Here's 44 in binary: 00101100

So, when you pass 44 to that function, the first thing it does is check to see if the number is less than or equal to 2. If it is, it prints it out and returns. You should understand that part, so now let's look at the hard part:

remainder = number % 2;
This just divides the number by two, and keeps the remainder.
If you'll look at our binary representation of 44, it ends in 0. You'll also notice that 44 / 2 has a remainder of 0. This is not a coincidence. All numbers that are evenly divisible by two (even numbers) have a remainder of zero, and a binary representation that ends with 0. All odd numbers will have a remainder of 1 when divided by 2, and the binary representation will end in 1.

So what good doe the remainder operation do? It gets us the *last* binary digit of the number.

So what does the bitshift operator do? Essentially it cuts off the last binary digit. So, 44, which is:
00101100
gets the last digit cut off and becomes:
001010 (10 in decimal, but that's not important)
So, now we have saved the lowest binary digit of our number, and then chopped that last digit off.
Now we send this new number (001010, or decimal 10) through this function again
it finds a remainder of 0, cuts off the last digit, and repeats.

This continues until the number that gets passed into binary() is 1 or 0. At this point, the function prints out it's number and returns, and then the function that called this one prints its number and returns, and the fucntion that called that one does the same, until we've returned all the way to the top of the stack, with each function call printing out the one binary digit that it had saved.

 

[DaveSimmons]

Once you understand that, try swapping the order of the cout and recursive call and see what happens 🙂

 

[itachi]

Originally posted by: DaveSimmons
Once you understand that, try swapping the order of the cout and recursive call and see what happens 🙂

i think that's probably one of the most important points. understanding binary is useless if u can't even differentiate between the most and least significant bits.

as for the recursion.. if you call the function with n=5 and trace it's execution, it would look something like this..

call binary(5)
- allocate integer (remainder) on the stack
- is number less than or equal to 1?
- no.. skip block of code
* remainder = n % 2 (= 1)
- shift n right by 1 -- equivalent to n / 2
- call binary(2)
- - allocate integer (remainder) on the stack (not the same as above)
- - is number less than or equal to 1?
- - no.. skip block of code
* * remainder = n % 2 (= 0)
- - shift n right by 1
- - call binary(1)
- - - allocate remainder
- - - is number less than or equal to 1?
- - - yea.. enter code block
* * * print n (1)
- - - return
* * print remainder (0)
- - return
* print remainder (1)
- return