Thread: simple Recursion problem

  1. #1
    Registered User
    Join Date
    Jun 2008
    Posts
    8

    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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  3. #3
    Registered User
    Join Date
    Jun 2008
    Posts
    8
    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?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  5. #5
    Registered User
    Join Date
    Jun 2008
    Posts
    8
    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 View Post
    (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

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  7. #7
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    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.

  8. #8
    Registered User carrotcake1029's Avatar
    Join Date
    Apr 2008
    Posts
    404
    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");
    }

  9. #9
    Registered User
    Join Date
    Jun 2008
    Posts
    8
    ok sweet thanks for the help guys

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple memory game problem
    By Eamusuta in forum C++ Programming
    Replies: 2
    Last Post: 06-21-2005, 07:59 AM
  2. simple compiling problem
    By waxydock in forum C++ Programming
    Replies: 2
    Last Post: 03-26-2005, 10:33 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Replies: 5
    Last Post: 12-03-2003, 05:47 PM
  5. Knight's Tour Recursion Problem
    By thephreak6 in forum C++ Programming
    Replies: 1
    Last Post: 10-14-2003, 09:18 AM