Recursive code

This is a discussion on Recursive code within the C++ Programming forums, part of the General Programming Boards category; Having searched about a dozen times, and read 9 pages on this search before finding it, I found a code ...

  1. #1
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209

    Recursive code

    Having searched about a dozen times, and read 9 pages on this search before finding it, I found a code that can return the binary value for a number you feed in. However, it's recursive, and I don't understand how it works. Any chance of getting it explained ?

    Code:
    long bin_conv(int number)
    {
    int remainder;
    long ans=0;
    if (number == 0)
    return 0;
    remainder = number % 2;
    number = number / 2;
    ans = bin_conv(number) * 10 + remainder;
    return ans;
    }
    Thanks.

  2. #2
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    Lets see...

    remainder = remainder % 2;

    it its odd remainder = 1 even remainder = 0

    whatever number you have divides by two umm well yeah it works...
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  3. #3
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209
    I've tried, and I still don't see where some of the stuff comes from I don't understand how the unfinished function can call itself again and enter an unfinished value into "ans", the answer...

  4. #4
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209
    I have no problem with a function calling itself, however, when I annotate this code and run it, I understand that the remainder when divided by 2 is the binary code. Why is it multiplied by 10 then, and, well, I just don't see how this works. Any chance of this code being non-recursive ?

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,794
    You can maybe use a bitset:
    Code:
    #include <bitset>
    #include <limits>
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    long bin_conv(int number)
    {
        bitset<numeric_limits<int>::digits> bits(number);
        return atol(bits.to_string().c_str());
    }
    
    int main()
    {
        cout << bin_conv(45) << endl;
        return 0;
    }
    Output is:
    101101

    [edit]Changed numeric_limit to read numeric_limits[/edit]
    Last edited by hk_mp5kpdw; 07-30-2003 at 10:48 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  6. #6
    Registered User
    Join Date
    Jul 2003
    Posts
    7
    Wow. This is a really silly way to do this. As someone pointed out earlier, the *10 is there just because they are representing the binary number with a decimal number that happens to "look" the same. What makes this incredibly silly is the limits this places on the inputs it can compute.

    On to your question, it seems that you just aren't comfortable with recursion. Here's a short example of a recursive function that adds up the integers from 0 to whatever you give it.

    int sum (int x) {
    if (x == 0) {
    return 0;
    } else {
    return x +sum(x-1);
    }
    }


    At it's core, it's the exact same concept as the converter you've got. How can it possibly be that you call a function again before another call to it finishes? Well, it's really quite simple. The function gets defined by the programmer, and then eventually gets loaded into the computer. When it eventually gets called, the computer starts executing instructions one at a time until it's done. Makes perfect sense under most cases, right? But what happens if the function calls itself? Well, here's the catch. It's not really calling "itself." That is to say, the thing that's running is not calling itself, it's calling a function who's definition happens to be the same.

    In some respects its very similar to other looping constructs like FOR or WHILE in that just because computer is executing identical lines of code, it's not necessarily (and probably isn't) executing the same thing.

    Hrm. Well, recursion is a somewhat difficult thing to explain without feed back or questions asked, so I'll stop here. And for the more pedantic out there, I know I was a bit loose with the explanation and terminology, but I think it's much more important to get the gist of it all first. Details after you see the big picture.

    ~SK

  7. #7
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    First i would suggest you to lear more about recursion.. Learn about stacks and how recursion functions use stacks to call them selves again and again....


    I think you are confused with the same variables holding different state in each recursion...... The same variables have different states in each reccursive loop and is maintained in a stack.. if you are not understanding anything... i recomed you buy a Data Structures book..

  8. #8
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209
    Indeed, I didn't know about the different states, but I found that out when someone helped me look through it, and we worked it out. Thanks !

  9. #9
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    I posted an example that converts binary to decimal non-recursivly you may want to check out my post.

  10. #10
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209
    Yes, I saw it, thanks, but I really needed to understand this one. The problem was, I was thinking it was a loop, not calling itself elsewhere.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 03-21-2006, 06:52 AM
  2. Recursive Function in Pseudo Code
    By smitsky in forum Tech Board
    Replies: 3
    Last Post: 10-24-2004, 10:17 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM
  5. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21