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?

Have you considered convert it to char* and call a recursive function with a char*? It makes things easier probably, but I don't know if you were allowed to do this — Dan
– Dan, Commented Jul 5, 2012 at 15:08
@JoSo I think there can't be a leading 0 in a integer... so I guess it would be: 1230: 321 — JorgeeFG
– JorgeeFG, Commented Jul 5, 2012 at 15:14
If you are looking at hints on how to solve this kind of problem, my suggestions would be 1) Try to stick to a if(is_base_case){ basecase } else { recursive_case } structure. It gets natural with practice and 2) Learn how to convert tail recursion to while loops and vice versa. Many kinds of problems fall under this category — hugomg
– hugomg, Commented Jul 5, 2012 at 17:03

BLUEPIXY · Accepted Answer · 2012-07-05 15:19:21Z

3

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 ) );
}

answered Jul 5, 2012 at 15:19

BLUEPIXY

40.2k7 gold badges37 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

JorgeeFG Over a year ago

Works perfect, thank you. If it's not disturbing, could you explain how you thought it? Thanks!

cha0site Over a year ago

@Jorge: The idea is to recurse the other way around -- instead of handling the rightmost digit first, you handle the leftmost. That's what the loop does here and the log10/pow combination does in my answer. The rest comes rather naturally.

BLUEPIXY Over a year ago

@Jorge - i:10^floor(log10(num)), cha0site explained.

AnT stands with Russia · Accepted Answer · 2012-07-05 15:14:53Z

1

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;

edited Jul 5, 2012 at 15:14

answered Jul 5, 2012 at 15:09

AnT stands with Russia

323k44 gold badges548 silver badges793 bronze badges

2 Comments

Jay Over a year ago

+1. This was the answer, I also thought of. But, shouldn't it be (number of digits in tail - 1). For Ex: 321 has 3 digits, so it should be rest * pow(10, 2) when it executes for the last time.

AnT stands with Russia Over a year ago

@Jay: tail in this case is actually the remaining portion of the number (which has already been fed through the recursive call). I.e. if the original number was 321, then rest is 1, while tail is 23. So, deg will be 2, exactly as it should be. However, I already see a problem with this solution if tail ends up with leading zeros after inversion. The number of digits should be calculated before the recursive call. BLUEPIXY does it correctly in the accepted solution.

Jo So · Accepted Answer · 2012-07-05 15:05:09Z

0

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)

answered Jul 5, 2012 at 15:05

Jo So

26.9k6 gold badges45 silver badges60 bronze badges

Comments

cha0site · Accepted Answer · 2012-07-05 15:25:48Z

0

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.

edited Jul 5, 2012 at 15:25

answered Jul 5, 2012 at 15:04

cha0site

10.8k3 gold badges36 silver badges52 bronze badges

4 Comments

interjay Over a year ago

This is the same as Rafael Baptista's answer, and is just as wrong.

cha0site Over a year ago

@interjay: Actually, you're right. Let me think about this some more.

interjay Over a year ago

Yeah, it should work now, +1. I don't think the exam question is very good because it requires you to either use floating point to count the digits, or use a loop (which is silly when the point is to use recursion).

cha0site Over a year ago

@interjay: Agreed. Sadly, I think it's quite common, for some reason most "didactic" examples of recursion are not very good uses of recursion.

Kalai Selvan Ravi · Accepted Answer · 2012-07-05 15:28:15Z

0

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)

edited Jul 5, 2012 at 15:28

answered Jul 5, 2012 at 15:03

Kalai Selvan Ravi

2,8862 gold badges18 silver badges28 bronze badges

4 Comments

interjay Over a year ago

Your 2nd function doesn't really work, you aren't even using the result of the recursive call.

interjay Over a year ago

No, it won't work. You aren't even returning a value from the function. -1 for arguing when you obviously didn't test it.

Kalai Selvan Ravi Over a year ago

@interjay I have removed that function. After I tested it, I will post it.

interjay Over a year ago

OK, -1 removed. I don't think there is a simple way to answer the question without adding an extra parameter or counting the number of digits.

Me.Name · Accepted Answer · 2012-07-05 15:33:31Z

0

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);
    }

edited Jul 5, 2012 at 15:33

answered Jul 5, 2012 at 15:04

Me.Name

12.6k3 gold badges34 silver badges48 bronze badges

Comments

Jishnu Dev Roy · Accepted Answer · 2017-06-09 12:50:11Z

-1

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;
}

answered Jun 9, 2017 at 12:50

Jishnu Dev Roy

1

1 Comment

ohmu Over a year ago

Why are you using a global variable?

Collectives™ on Stack Overflow

C: Recursive function for inverting an int

7 Answers 7

3 Comments

2 Comments

Comments

4 Comments

4 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

3 Comments

2 Comments

Comments

4 Comments

4 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related