# simple Recursion problem

• 06-11-2008
wOo[FIN.K.L]
simple Recursion problem
Hey there guys :)

I've got a sample code on converting numbers into binary by using recursions

heres the function:

Code:

```void printBinary (int n) {   if (n < 2) {       printf ("%d ", n);   } else {       printf ("testX "); //this is hear to see how recursive pattern works       // recursively print the leading bits       printBinary (n/2);       printf ("testY ");  //this is also hear to see how recursive pattern works       // print the least significant bit       printf ("%d ", n%2);   } }```
Output:

Code:

```Enter an integer to display in binary 8 testX testX testX 1 testY 0 testY 0 testY 0```
ok so the output is 1000, however it recurs 3 times before printing a 1 without therefore:

8 / 2 = 4 (first time)
4 / 2 = 2 (second time)
2 / 2 = 1 (third time)

since 1 < 2 it prints out 1, fair enough. now from here on it gets confusing O_O. How is it going to this part of the function:

Code:

```    // print the least significant bit       printf ("%d ", n%2);```
3 times?

thanks guys.
• 06-11-2008
tabstop
When a function call returns, it returns to the point where it was called. So when the third printBinary returns, it returns to the printf("testY") -- and voila, there's a //print the least significant bit to be done.
• 06-11-2008
wOo[FIN.K.L]
oh I think i get it now, so for each loop (3 in this case), it will "// print the least significant bit" the same amount of times as loops? which is why theres 3 testY's?
• 06-11-2008
tabstop
You don't have any loops. Every time you call printBinary it will either (a) do the true part, or (b) do the false part -- print testX, do another call, print testY, and print n%2.
• 06-11-2008
wOo[FIN.K.L]
ok maybe I shouldn't call it a loop :x it's 3:30AM and I'm having trouble concentrating :P

Quote:

Originally Posted by tabstop
(b) do the false part -- print testX, do another call, print testY, and print n&#37;2.

this is whats confusing me, how does it have the chance to print testY and n%2 when it's calling "printBinary (n/2);"
before them, wouldnt it just keep recurring until its false, and never reach print testY, and print n%2?

hang on a second let me try to explain how I'm seeing the program at this moment in time (forgive my crappy explanation)

I input 8

printBinary (n/2) is called for the first time
8 / 2 = 4
printBinary (n/2) is called for the second time
4 / 2 = 2
printBinary (n/2) is called for the third time
2 / 2 = 1

1 < 2 therefore 1 is printed. and the recursion halts.

and since you said that when a function call returns, it returns to the point its called.

testY is printed
printf ("%d ", n%2);
so 1 is printed again, thats not right ;x
• 06-11-2008
tabstop
The statements would go something like this:
Code:

```printBinary(8)     print "testX"     printBinary(4)         print "testX"         printBinary(2)             print "testX"             printBinary(1)                 print "1"             print "testY"             print "0" (2%2 is 0)         print "testY"         print "0" (4%2 is 0)     print "testY"     print "0" (8%2 is 0)```
You have to let each function call finish before it returns, and the function calls won't finish until they get through the printing of testY and n%2.
• 06-11-2008
slingerland3g
In other words think of

Code:

`printf ("%d ", n%2)`
...as a simple place holder for the bits that are not satisfying (n <2).

When the recursive function exits it will simply spit out what the value of n was at that time, in your case 0.

I can not recall the place, but there is a good recursive function for the Fibonacci sequence which depicts all the values that are round up within the recursive calls.
• 06-11-2008
carrotcake1029
Or if you want a non recursive function method you could try something like this:
Code:

```#include <stdio.h> #include <limits.h> int main (void) {         int i;         char number = 0x72;  //Change to whatever you want                 for (i = 0; i < CHAR_BIT; i++)         {                 if (number & ((0x01 << (CHAR_BIT - 1)) >> i))                         printf("1");                 else                         printf("0");         }         printf("\n"); }```
• 06-12-2008
wOo[FIN.K.L]
ok sweet thanks for the help guys