My goal is to write a recursive program that reverse the digits of an integer number. When I test the first element, the code works. However, it doesn't work well for the other two cases, e.g. it for reverse(456) it prints 321654 and for reverse(731) it prints 321654137.
I think the issue is with the public static variable reverted.
Can someone please help me to understand the problem and fix it?
using System;
public class Program
{
public static void Main(string[] args)
{
reverse(123);
reverse(456);
reverse(731);
}
public static int reverted=0;
public static void reverse(int number)
{
if (number!=0)
{
int remainder = number % 10;
reverted = (reverted*10)+remainder;
reverse(number/10);
}
else
Console.WriteLine(reverted);
}
}
My goal is to write a recursive program that reverse the digits of an integer number.
Since that is a goal that no one in industry would likely wish to attain, odds are good this is for a class. In particular, no sensible person would solve this problem, even if they had it, with recursion. So this is a lousy problem to teach recursion, because the non-recursive solution is so straightforward.
Odds are also good that you do not understand recursion very well. This is in some sense a great exercise because it requires that you use a special technique, called an accumulator, to achieve a recursive solution.
Moreover, your solution, even if you fixed the bug, does not produce the required number. It prints it, and that is completely different. We wish to be able to produce the result, not merely display it.
(This then brings up the interesting question of how to deal with numbers that fit into an int but whose reverses do not, like 1000000009. Let's ignore those issues for the time being.)
So let's start with the basics. Every recursive method has the same structure:
Let's naively apply this pattern to your problem and see what happens.
The base case is easy:
What's the recursive case? Suppose we have 157
It's not clear how to perform that last operation.
We need to be smarter.
Here's what you do. (I've left out the error checking that rejects negative numbers.)
static int ReverseHelper(int number, int accumulator) =>
number == 0 ?
accumulator :
ReverseHelper(number / 10, accumulator * 10 + number % 10);
public static int Reverse(int number) =>
ReverseHelper(number, 0);
Let's look at some cases.
Suppose number is 0. Then ReverseHelper returns 0, good. Zero works.
Suppose number is 3. Then we call ReverseHelper(3, 0) which calls ReverseHelper(0, 3), which returns 3. One-digit numbers work.
Suppose number is 35. We call ReverseHelper(35, 0), which calls ReverseHelper(3, 5), which calls ReverseHelper(0, 53), which returns 53. Two digit numbers work.
And so on.
Exercise: There is a straightforward way to deal with the problem of reversing an int where the reversal does not fit into an int; what is it?
You see I hope why this technique is called using an accumulator. The desired result is accumulated gradually as the recursion proceeds, and then returned when the recursion reaches its base case.
Now, notice how this technique relates to your original program. You are using a static field as your accumulator. Never do that! Ever! Recursive methods should not depend for their correctness on external state. Instead, pass the value that you will be consuming recursively down into the recursive call to a helper method.
Study this technique carefully. This is a powerful technique for writing recursive programs. In functional languages, such an operation is called fold or reduce; look to those for further inspiration. In C# it is called Aggregate and is used to produce a summary result on a sequence.
The recursive pattern using accumulators is:
Why is this technique so valuable? In C# this is less important, but in the tail recursive functional languages the compiler can often optimize recursive methods that use accumulators into more efficient code than non-tail-recursive methods, so that's something else to research.
It is valuable in C# because tail recursive methods that use accumulators can easily be turned into non-recursive methods by a simple process of program transformation.
Let's see how. We have:
static int ReverseHelper(int number, int accumulator) =>
number == 0 ?
accumulator :
ReverseHelper(number / 10, accumulator * 10 + number % 10);
Let's rewrite that as a statement:
static int ReverseHelper(int number, int accumulator)
{
if (number == 0)
return accumulator;
else
return ReverseHelper(number / 10, accumulator * 10 + number % 10);
}
}
Now let's make explanatory variables for all the subexpressions:
static int ReverseHelper(int number, int accumulator)
{
if (number == 0)
return accumulator;
else
{
int newNumber = number / 10;
int newAccumulator = accumulator * 10 + number % 10;
return ReverseHelper(newNumber, newAccumulator);
}
}
So far so good. But now we notice that we can turn the whole thing into a loop!
static int ReverseHelper(int number, int accumulator)
{
while (true)
{
if (number == 0)
return accumulator;
else
{
int newNumber = number / 10;
int newAccumulator = accumulator * 10 + number % 10;
number = newNumber;
accumulator = newAccumulator;
// And now the loop starts over!
}
}
}
And of course we see that this now has the form of the straightforward non-recursive solution to the problem.
This should give you a powerful insight into the nature of recursive programs:
Again, study these simple techniques carefully. Understanding the relationship between recursive and non-recursive programs is a key tool in CS theory.