recursion reverse number order

Can someone help me or point me in the right direction. I need to make a function using recursion to reverse a value that has been read in from a file.
so for example, if the file reads in 123 then the output will be 321.

I have done the recursion to print out the values in the same order, but how can I modify it to print the reverse order

1
2
3
4
5
6
7
8
//This is not in reverse order but I want to see how I can mod my code to do so
 int PRINT_REVERSE(int n)
{
	if(n > 10)
	   return n +  PRINT_REVERSE(n % 10);
		
	return 0;
}


I was thinking something along the lines where the recursion reverses the stack once the condition is reached (n > 10) or that it somehow reverses the numbers as it travels down the stack to reach the condition.

Thank you for the help
I am terrible at this but my take on it would be... if 'cheating' with a static variable is not a problem for you.

1
2
3
4
5
6
7
8
9
10
11
int pr(int n, bool reset = true)
   {
	   static int result = 0;
            if(reset) result = 0;
	   result *=10;
	   result +=n%10;	   
	   if(n>10)
		   pr(n/10, false);    	   
	   return result;	   
   }
   


Fixed that.
Last edited on
There is a really elegant solution to this that can be written in a single return statement and it'll work for negative numbers too.

Hint: Pass two parameters: n and result which is 0 by default.
Divide n by 10, multiply result by 10 and add the last digit of n to it, and pass those again.
Do this until n is zero.
Last edited on
mine does not work for negatives, BTW. Should be easy to fix that if you need to.
Ihatov I'm still new at recursion and don't know all the 'rules' but, are you referring to passing in n and result int PRINT_REVERSE(int n, int result)

if so, how does that work? does it send the 1st calculation back out the function and then back in again to make the numbers swap places?

or should I declare a variable 'result' inside my function?

thank for the help
It sounds a lot like what I did except instead of the static/bool nonsense, just use result as a parameter to the same effect.

so roughly like:

int rev(int n, int result = 0)
{
stuff
rev(n/10, result);
}

Yes int PRINT_REVERSE(int n, int result=0) is exactly what I was referring to.
Note: I added result = 0 because I also said result should be 0 by default.
This will enable you to call the function with just one argument: PRINT_REVERSE(43241). The other is used internally.

if so, how does that work? does it send the 1st calculation back out the function and then back in again to make the numbers swap places?

PRINT_REVERSE() needs to calculate new_n and new_result the way I described and pass those to another PRINT_REVERSE() and save what it returns to new_return. You don't have to do anything with new_return, you just return it. All in all, you need to do this:

int new_n = <calculate>
int new_result = <calculate>
int new_return = PRINT_REVERSE(new_n, new_result);
return new_return;


And oh, we need to check if n == 0 and return result in that case! Otherwise the recursion would go to infinity.
Now the complete code looks like this:
1
2
3
4
5
6
7
8
int PRINT_REVERSE(int n, int result=0) {
	if (n == 0)
		return result;
	int new_n = /*calculate new n*/;
	int new_result = /* calculate new result*/;
	int new_return = PRINT_REVERSE(new_n, new_result);
	return new_return;
}

How does this work?
The first thing it does is check if n is zero. If it's not, it calculates new_n and new_result and gives those to another PRINT_REVERSE().

This other PRINT_REVERSE() does the same thing. It checks if n is zero and if it's not, it calculates new_n and new_result and gives those to a yet another PRINT_REVERSE et cetera. et cetera.

This goes on until a PRINT_REVERSE() is hit where (n == 0).
This one will break the recursion because it's not going to call PRINT_REVERSE again, it'll just return result.

Because it didn't call another PRINT_REVERSE() it'll instead cause the PRINT_REVERSE() that's level above to return result too.
And that one will cause the PRINT_REVERSE() above it return result as well.
There's now a domino effect going on going all the way up to your original call to PRINT_REVERSE() causing that one to return as well and finally ending the process.

However. What guarantees that n is definitely going to get to zero?
What guarantees is the way new_n is calculated which you're going to see after you fill in the blanks.


By the way

This is basically how all recursive algorithms are constructed.
You first decide on how you want to end the recursion.
So you check, and if you're not satisfied yet then you just calculate things a bit and try again.

All recursive functions are going to look like this:
1
2
3
4
5
6
7
8
9
10
11
12
int recursion(...){
	//are we satisfied with what was passed to us?
	if (<satisfied>) 
		return something;

	//no we're not so we're going to calculate things a bit and try again.
	<calcualations>

	//hopefully, the other one will do better than us!
	int result = recursion(...);
	return result;
}
Last edited on
Registered users can post here. Sign in or register to post.