How do I reverse the order of the digits of an integer using recursion in C programming?

Question

Problem statement :

Given a 32-bit signed integer, reverse digits of an integer.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [ −2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

I'm trying to implement the recursive function reverseRec(), It's working for smaller values but it's a mess for the edge cases.

int reverseRec(int x)
{
    if(abs(x)<=9)
    {
        return x;
    }
    else
    {
        return reverseRec(x/10) + ((x%10)*(pow(10, (floor(log10(abs(x)))))));
    }
}

I've implemented non recursive function which is working just fine :

int reverse(int x)
{
    long long val = 0;
    do{
        val = val*10 + (x%10);
        x /= 10;
    }while(x);

    return (val < INT_MIN || val > INT_MAX) ? 0 : val;
}

Here I use variable val of long long type to check the result with MAX and MIN of signed int type but the description of the problem specifically mentioned that we need to deal within the range of 32-bit integer, although somehow it got accepted but I'm just curious If there is a way to implement a recursive function using only int datatype ?

One more thing even if I consider using long long I'm failing to implement it in the recursive function reverseRec().

Answer 1

If there is a way to implement a recursive function using only int datatype ?
(and) returns 0 when the reversed integer overflows

Yes.

For such +/- problems, I like to fold the int values to one side and negate as needed. The folding to one side (- or +) simplifies overflow detection as only a single side needs testing

I prefer folding to the negative side as there are more negatives, than positives. (With 32-bit int, really didn't make any difference for this problem.)

As code forms the reversed value, test if the following r * 10 + least_digit may overflow before doing it.

---

An int only recursive solution to reverse an int. Overflow returns 0.

#include <limits.h>
#include <stdio.h>

static int reverse_recurse(int i, int r) {
  if (i) {
    int least_digit = i % 10;
    if (r <= INT_MIN / 10 && (r < INT_MIN / 10 || least_digit < INT_MIN % 10)) {
      return 1; /// Overflow indication
    }
    r = reverse_recurse(i / 10, r * 10 + least_digit);
  }
  return r;
}

// Reverse an int, overflow returns 0
int reverse_int(int i) {
  // Proceed with negative values, they have more range than + side
  int r = reverse_recurse(i > 0 ? -i : i, 0);
  if (r > 0) {
    return 0;
  }
  if (i > 0) {
    if (r < -INT_MAX) {
      return 0;
    }
    r = -r;
  }
  return r;
}

Test

int main(void) {
  int t[] = {0, 1, 42, 1234567890, 1234567892, INT_MAX, INT_MIN};
  for (unsigned i = 0; i < sizeof t / sizeof t[0]; i++) {
    printf("%11d %11d\n", t[i], reverse_int(t[i]));
    if (t[i] != INT_MIN) {
      printf("%11d %11d\n", -t[i], reverse_int(-t[i]));
    }
  }
}

Output

          0           0
          0           0
          1           1
         -1          -1
         42          24
        -42         -24
 1234567890   987654321
-1234567890  -987654321
 1234567892           0
-1234567892           0
 2147483647           0
-2147483647           0
-2147483648           0

Answer 2

You could add a second parameter:

int reverseRec(int x, int reversed)
{
    if(x == 0)
    {
        return reversed;
    }
    else
    {
        return reverseRec(x/10, reversed * 10 + x%10);
    }
}

And call the function passing the 0 for the second parameter. If you want negative numbers you can check the sign before and pass the absolute value to this function.

Answer 3

I am assuming by reversing an integer you mean turning 129 to 921 or 120 to 21.

You need an initial method to initialize your recursive function. Your recursive function must figure out how many decimal places your integer uses. This can be found by using log base 10 with the value and then converting the result to a integer.

• log10 (103) approx. 2.04 => 2

Modulus the initial value by 10 to get the ones place and store it in a variable called temp Subtract the ones place from the initial value and store that in a variable called newStart.

• divide this value by 10

Subtract one from the decimal place and store in another variable called newDecimal.

Return the ones place times 10 to the power of the decimal place and add it to the function where the initial value is newStart and the decimalPlace is newDecimal.

#include <stdio.h>
#include <math.h>

int ReverseInt(int startValue, int decimalPlace);

int main()
{
    int i = -54;
    int positive = i < 0? i*-1 : i;
    double d = log10(positive);
    int output = ReverseInt(positive,(int)d);
    int correctedOutput = i < 0? output*-1 : output;
    printf("%d \n",correctedOutput);
    return 0;
}

int ReverseInt(int startValue, int decimalPlace)
{
    if(decimalPlace == 0)
    {
        return startValue;
    }
    int temp = startValue % 10;
    int newStart = (startValue -temp)/10;
    int newDecimal = decimalPlace -1;
    
    
    int value = temp*pow(10,decimalPlace);
    return value + ReverseInt(newStart,newDecimal);
}

Answer 4

It's late and nothing better does not come into my mind. No float calculations. Of course, integer has to be big enough to accommodate the result. Otherwise it is an UB.

int rev(int x, int partial, int *max)
{
    int result;
    if(x / partial < 10 && (int)(x / partial) > -10)
    {
        *max = partial;
        return abs(x % 10) * partial;
    }
    result = rev(x, partial * 10, max) + abs(((x / (int)(*max / partial)) % 10) * partial);
    return result;
}

int reverse(int x)
{
    int max;
    return rev(x, 1, &max) * ((x < 0) ? -1 : 1);
}


int main(void){
  
  printf("%d", reverse(-456789));
}

https://godbolt.org/z/M1eezf

unsigned rev(unsigned x, unsigned partial, unsigned *max)
{
    unsigned result;
    if(x / partial < 10)
    {
        *max = partial;
        return (x % 10) * partial;
    }
    result = rev(x, partial * 10, max) + (x / (*max / partial) % 10) * partial;
    return result;
}

unsigned reverse(unsigned x)
{
    unsigned max;
    return rev(x, 1, &max);
}


int main(void){
  
  printf("%u", reverse(123456));
}

when using long long to store the result all possible integers can be reversed

long long rev(int x, long long partial, long long *max)
{
    long long result;
    if(x / partial < 10 && (int)(x / partial) > -10)
    {
        *max = partial;
        return abs(x % 10) * partial;
    }
    result = rev(x, partial * 10, max) + abs(((x / (int)(*max / partial)) % 10) * partial);
    return result;
}

long long reverse(int x)
{
    long long max;
    return rev(x, 1, &max) * ((x < 0) ? -1 : 1);
}


int main(void){
  
  printf("%d reversed %lld\n", INT_MIN, reverse(INT_MIN));
  printf("%d reversed %lld\n", INT_MAX, reverse(INT_MAX));
}

https://godbolt.org/z/KMfbxz

Answer 5

In trying to learn C programming I programed this question and get some correct results and some incorrect. I don't see the reason for the difference.

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <math.h>  // requires adding link to math -lm as in: gcc b.c -lm -o q11

    int ReverseInt(int startValue, int decimalPlace)
    {
        if(decimalPlace == 0)  // if done returns value
        {
            return startValue;
        }
    int temp = startValue % 10;  // gets units digit
    int newStart = (startValue -temp)/10; // computes new starting value after removing one digit
    int newDecimal = decimalPlace -1;
    
    
    int value = temp*pow(10,decimalPlace);
    return value + ReverseInt(newStart,newDecimal);  // calls itself recursively until done
    }


    int main()
    {
        int x, decimalP, startValue;
        printf("Input number to be reversed \n Please note number must be less than 214748364 :");
        scanf("%d", &x);
        if (x > 214748364)
        {
            printf("Input number to be reversed \n Please note number must be less than 214748364 :");
            scanf("%d", &x);
        }
        decimalP = round(log10(x));  // computes the number of powers of 10 -  0 being units etc.
        startValue = ReverseInt(x, decimalP);  // calls function with number to be reversed and powers of 10
        printf("\n reverse of %d is %d \n", x, startValue);
    }

Output is: reverse of 1234 is 4321 but then reverse of 4321 is 12340