C++ I need to write a function that converts hexidecimal to decimal and uses recursion and I keep getting runtime errors

Question

This is for a class so it has to use recursion, I've written a working code iteratively, but I can't get it to work in recursion and I'm really lost. I've been working on this for a week. Any guidance or suggestions at all would be extremely helpful.

This is my function, I need to take in the hexadecimal as a char pointer and output it's corresponding decimal. I'm constantly getting either stack overflow or memory allocation runtime errors, can anyone identify what's wrong and steer me in the right direction?

 int hexToDecimal(const char *hex, int offset, int power){
  if(offset >= 0){
    hexChar = *(hex+offset);

    if( isalpha(hexChar) ) {
      hexChar = toupper(hexChar);
      hexNum = hexChar - asciiCharOffset;
    } else { 
      hexNum = hexChar - asciiIntOffset;
    }   
    return hexToDecimal(hex, offset--, power++) +  hexNum * (int)pow(16,power); 

  } else {
    return 0;
  }
}

Answer 1

I have not compiled it, but first glance tells me that the corresponding line should be:

return hexToDecimal(hex, offset-1, power+1) +  hexNum * (int) pow(16,power-1);    

Because in your case, you are calling yourself ad infinitum (being called with, lets say offset 6, if you pass offset-- it will still pass 6 because it will decrement after it gives the value to the function).

Also, the post-increment will give you undefined behavior for the call pow(16,power) later in the same expression, because (taking the example of power=6 again), it may be pow(16,6) or pow(16,7) depending on the compiler.

All that aside, there's also risk, that pow() will give you false (rounded down) value when converting to int (it may turnn out that pow(16,2) returns 255.9999999 and you end up with (int)255, there's ample evidence and solutions here on stackoverflow, just search for pow).

EDIT (in reply to comments):

Finally, introducing the magical printf debugger:

int hexToDecimal(const char *hex, int offset, int power){
  if(offset >= 0){
    char hexChar = *(hex+offset);
    int hexNum, 
        recursed;

    if( isalpha(hexChar) ) {
      hexChar = toupper(hexChar);
      hexNum = hexChar - asciiCharOffset;
    } 
    else { 
      hexNum = hexChar - asciiIntOffset;
    }   
    recursed= hexToDecimal(hexNum, offset-1, power+1); 

    printf("%d + %d * %d\n", recursed, hexNum, (int)pow(16,power-1));

    return recursed +  hexNum * (int)pow(16,power-1); 

  } else {
     return 0;
  }
}

Answer 2

You're using post-increment here:

  return hexToDecimal(hex, offset--, power++) 

Post-increment (and post-decrement) will increment/decrement the variable (i.e. it will actually change offset and power), but the inc/dec will happen after the variable is evaluated.

I.e.:

int i = 5;
std::cout << "i = " << i;     // prints 'i = 5'
std::cout << "\ni = " << i++; // still prints 'i = 5' and then changes i to be 6
std::cout << "\ni = " << i;   // prints 'i = 6'

You don't actually want to modify offset and power -- you want to pass a different value for these to the next hexToDecimal call.

You can catch these kind of mistakes if you make the method parameters const, i.e.:

int hexToDecimal(const char*hex, const int offset, const int power);

I recommend making parameters const when you have no intention to modify them. That way the compiler can help you catch a lot of common mistakes.

Answer 3

use predecrement in the the function argument . Use --offset in the argument. if u use offset-- then intial value of offset is passed to function and then offset is decreased.