Recursively Reversing Integer Digits

[faithful4ever]

Hello all,

Basically I'm trying to code a program that makes use of recursion to reverse an input integer, e.g. 123 will result in a display of 321.

I've coded the program this far, but it just displays the last digit only. Where have I gone wrong? I.e. Instead of 123 displaying 321, it displays just 3. I have done printf debugging, and my issue is how to make the program remember the first few digits and print them out as well, e.g. Rmb 2 and 1, and display these integers together with the 3 that is already printed.

Here's what I've done for the reverseDigits function:

void reverseDigits(int n, int *result) {
	int reverseNum = 0;
	int basePos = 1;

	if(n == 0) {
		printf("\n");
	}

	if(n != 0) {
		reverseDigits(n/10, result);
		reverseNum += (n%10)*basePos;
		basePos *= 10;
		printf("REVERSE NO.: %d\n\n", reverseNum);
	}
	*result = reverseNum;
}

Thanks!

[VernonDozier]

I'm not sure I understand the algorithm. In particular, line 12 appears to have no effect at all. You change the value of a local variable, then don't do anything with it. In line 11, basePos is 1, so you're multiplying by 1. Again, no effect. It seems like you can get rid of basePos altogether and nothing would change.

Also, why are your printing inside of the function or is that part of the debugging? I assume result is supposed to contain 321 at the end, right? That's the goal? If so, call the function and when it RETURNS, print it.

[WaltP]

The key to recursion is the value returned from the function. That's your main problem.

Next you haven't properly defined what the function is supposed to do. Does it
A) return a reversed value of the integer passed to it?
B) simply print out the individual digits in reverse order?
C) create the reversed value and print it?

The way recursion works is it will either
1) calculate one value then calls itself with the rest of the number
2) remove a digit, call itself with the new value, upon returning get the digit to from the value.

The way recursion remembers is all the values it calculates in 1 instance of the function remain in that instance. When the function calls itself, it makes a clone of the function complete with all new values. When the function returns, it back through all these instances which 'restores' the values from that instance.

[faithful4ever]

Hmm, it's supposed to be A, because in my main(), the user would have to enter an input.

Thing is, I have already called up the function recursively, and it seems to work except that instead of displaying the complete number, e.g. from 123 to 321, it just displays the first digit of the reversed integer (3) and terminates there.

I have a feeling it's my

*result = reverseNum;

line right?

Output: <as attached>

The key to recursion is the value returned from the function. That's your main problem.

Next you haven't properly defined what the function is supposed to do. Does it
A) return a reversed value of the integer passed to it?
B) simply print out the individual digits in reverse order?
C) create the reversed value and print it?

The way recursion works is it will either
1) calculate one value then calls itself with the rest of the number
2) remove a digit, call itself with the new value, upon returning get the digit to from the value.

The way recursion remembers is all the values it calculates in 1 instance of the function remain in that instance. When the function calls itself, it makes a clone of the function complete with all new values. When the function returns, it back through all these instances which 'restores' the values from that instance.

[faithful4ever]

Hmm, noted, I have modified my code as such:

void reverseDigits(int n, int *result) {
	int reverseNum = 0;

	if(n <= 0) {
		*result = n;
	} else {
		reverseNum += (n%10);
		reverseDigits(n/10, result);
		*result = reverseNum;
	}
}

However, it still outputs 123 as 3 instead of 321. Hmm, what am I missing out to concatenate the individual output digits together.

I'm not sure I understand the algorithm. In particular, line 12 appears to have no effect at all. You change the value of a local variable, then don't do anything with it. In line 11, basePos is 1, so you're multiplying by 1. Again, no effect. It seems like you can get rid of basePos altogether and nothing would change.

Also, why are your printing inside of the function or is that part of the debugging? I assume result is supposed to contain 321 at the end, right? That's the goal? If so, call the function and when it RETURNS, print it.

[histrungalot]

The way I see it is you have two things you have to keep track of: the result that you are building and in what 10's position you need to save the current modulo result in (basePos). You have the result but you need to build it not set (*result = reverseNum is not accumulating the answer, it is setting it, that is why you get the 3 as the end result right now). reverseNum += is good but you need to pass it out (hint *result). Then its just how to know what the value of basePos should be (hint think about returning something instead of void from reverseDigits).

[WaltP]

Read my post again. You didn't even consider half of it.

[faithful4ever]

Having read yours and WalterP's explainations, I have modified the code as such:

void reverseDigits(int n, int *result) {
	if(n!=0) {
		reverseDigits(n/10, result);
		*result = *result*10 + n%10;
	} else {
		*result = n;
	}
}

It now "accumulates" values, but now when user keys in 123, the output is still 123 and not 321. Hmm, where have I gone wrong semantically? :x

The way I see it is you have two things you have to keep track of: the result that you are building and in what 10's position you need to save the current modulo result in (basePos). You have the result but you need to build it not set (*result = reverseNum is not accumulating the answer, it is setting it, that is why you get the 3 as the end result right now). reverseNum += is good but you need to pass it out (hint *result). Then its just how to know what the value of basePos should be (hint think about returning something instead of void from reverseDigits).

[WaltP]

In my first post, first sentence, I clearly said

The key to recursion is the value returned from the function. That's your main problem.

Use the return statement -- that's what it's used for!!!

[faithful4ever]

Yeah, I know what you're getting at, but my lecturer wants me to use his template to code, and his template specifies

void reverseDigits(int n, int *result);

function prototype. You can't have a return value for a void function type. (Call by Reference is being done here.)

Otherwise, I had already gotten the solution if I used the return.

In my first post, first sentence, I clearly said

Use the return statement -- that's what it's used for!!!

[zeroliken]

Is it even possible to have a recursive function without a return statement? :-/

[VernonDozier]

>> Is it even possible to have a recursive function without a return statement?

If a function calls itself, it's recursive, return statement or not.

>> Yeah, I know what you're getting at, but my lecturer wants me to use his template to code, and his template specifies...

Point this out from the very beginning. No one has any idea what you're allowed to change and why unless you tell us.

>> where have I gone wrong semantically?

Without knowing your algorithm, it's hard to say what you're doing wrong. I can't see any attempt to reverse anything in the code. This is a paper and pencil exercise till you get the algorithm down.

[histrungalot]

Posted wong thing