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.

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.

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?

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.

ok maybe I shouldn't call it a loop :x it's 3:30AM and I'm having trouble concentrating :P

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

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.

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.

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");
}

ok sweet thanks for the help guys