C: Recursive function for inverting an int

Question

I had this problem on an exam yesterday. I couldn't resolve it so you can imagine the result...

Make a recursive function: int invertint( int num) that will receive an integer and return it but inverted, example: 321 would return as 123

I wrote this:

int invertint( int num ) {
  int rest = num % 10;
  int div = num / 10;
  if( div == 0 ) {
     return( rest );
  }
  return( rest * 10 + invert( div ) )
}

Worked for 2 digits numbers but not for 3 digits or more. Since 321 would return 1 * 10 + 23 in the last stage.

Thanks a lot!

PS: Is there a way to understand these kind of recursion problems in a faster manner or it's up to imagination of one self?

Answer 1

int invertint( int num ) {
  int i ;

  for(i=10;num/i;i*=10);
  i/=10;
  if(i == 1) return num;
  return( (num % 10) * i + invertint( num / 10 ) );
}

Answer 2

Your mistake is that in the last statement you are multiplying rest by 10. Why only 10? You need to shift the rest digit by as many digits as there are left in the remaining part of the number. You are shifting by only 1. No wonder it works only for 2-digit numbers.

The last part should be done along the lines of

int tail = invert( div );
int deg = /* number of digits in `tail` */;
return rest * (int) pow(10, deg) + div;

Answer 3

The problem is with return(rest * 10 + invert(div)). You can't do the multiplication yourself. The factor depends on the number of times the function is recursed, thus you have to provide the carry as a second argument to your function (carry is initialized with 0)

Answer 4

If you do it the other way, you won't need a counter.

int invertint(int num)
{
    if (0 == num || 0 == num % 10) {
        return num / 10;
    }
    int digits = floor(log10(num)) + 1;
    int modulus = pow(10, digits - 1);
    return invertint(num % modulus) * 10 + num / modulus;
}

Note that this isn't as simple as I originally thought - I had to use math.

Answer 5

int reverse(int no,int rev)
{
if(no!=0)
return reverse(no/10,rev*10+no%10);
else
return rev;
}

call this method as reverse(numberToReverse,0)

Answer 6

Just as an alternative, this could be done without recursion.

    int invertint(int num)
    {
        int res = 0;
        while (num != 0)
        {                
            res = res * 10 + (num % 10);
            num /= 10;
        }
        return res;
    }

But since recursion was the assignment, given the int(int) signature, easiest would be with a pow(log10)) variation (provided that you're allowed to include math.h ? )

    int invertint(int num)
    {
        if (num == 0) return 0;
        return invertint(num / 10)  +  (int)pow(10, (int)log10(num)) * (num % 10);
    }

Answer 7

This is the simplest approach.

int sum=0;
int reverse(int n)
{
    if(n>0)
    {
        sum=(sum*10)+(n%10);
        reverse(n/10);
    }
    return sum;
}