Sasha Miko Sasha Miko - 1 month ago 11
C++ Question

Recursion Binary to Decimal - completely stuck

I am using C++ to write a program that uses recursion to convert a user input binary number to a decimal. I've played with this code for hours

(earlier I initialized

i
with
i = binary.length();
)

void bin2dec(string binary, int i)
{
double decNum=0;

if (i >= 0)
{
if (binary[i] = 0)
{
decNum = (decNum + 0);
}
else
{
decNum = (decNum + pow(2, (i-1)));
}
bin2dec(binary, i-1);
}
cout << decNum;
}


That is my recursion function. Unfortunately, I am stuck. The program runs but gives me incorrect values. For example, when I plug in 1 as the binary, I expect to get 1 decimal in return. But I get .5 number. Is my calculation wrong or am I using recursion incorrectly?

Thank you!

Upon receiving suggestions, I made the following changes. However, the program still returns an incorrect value.

void bin2dec(string binary, int i)
{
double decNum=0;
if (i >= 0)
{
if (binary[i] == 1)
{
decNum = (decNum + pow(2, i));
}
else if (binary[i] == 0)
{
decNum = (decNum + 0);
}
bin2dec(binary, i - 1);
cout << decNum;
}
}

Answer

Assuming you are using small endian, you should use pow(2, i). With i-1, you are going to have 1 in position 0 in the array, which means you will evaluate pow(2, -1), which is 0.5.

Consider this working example (https://ideone.com/pWVAGP):

int bintodec(string binary, unsigned int i = 0)
{
    int tot = 0;
    if (i < binary.length())
    {
        if (binary[i] == '1')
            tot = pow(2, i);
        else if (binary[i] != '0')
            throw "String is not formatted in binary";
        return tot + bintodec(binary, ++i);
    }
    return tot;
}

Note that it's possible to start at the end of the string and work backwards, but I prefer starting at 0 since I think it is simpler. To total up your additions, the easiest thing to do is return another call of the function, as I did at the end of the if(i < binary.length() block. Once you have hit the base case (in this case where i == binary.length()), return a 0, which is added to the total number but doesn't change it. Once the base case has returned, the others will begin returning their portion of the sum to the one above them, which keeps getting added back until it reaches the bottom of the call stack, which is the original calling function.

If you do not want to return the answer, you could change the function signature to void bintodec(int& tot, string binary, unsigned int i = 0) and keep adding the value to tot rather than returning it, but it requires that your caller gives you an int to modify.