Recursive code

[Korhedron]

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 ?

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.

[JaWiB]

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...

[Korhedron]

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...

[Korhedron]

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 ?

[hk_mp5kpdw]

You can maybe use a bitset:

#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]

[SereneKaos]

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

[vasanth]

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..

[Korhedron]

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 !

[curlious]

I posted an example that converts binary to decimal non-recursivly you may want to check out my post.

[Korhedron]

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.