Recursive implementation is a confusing subject for me, somewhat. I want to learn how can I exactly "Translate" a normal method to a recursive one, after some research I still am little confused, especially in the first step (where the recursion stops).
This task is to rotate an array to left and right:
[TestCase(new[] { 1, 2 }, new[] { Direction.Left, Direction.Left, Direction.Right }, ExpectedResult = new[] { 2, 1 })]
I don't want to use linq on this, we could use Array.Copy and indices instead of my standard approach.
So here's my code that I want to translate:
public static int[] Shift(int[] source, Direction[] directions)
{
if (source is null)
{
throw new ArgumentNullException(nameof(source));
}
if (directions is null)
{
throw new ArgumentNullException(nameof(directions));
}
if (directions.Length == 0)
{
return source;
}
else
{
for (int i = 0; i < directions.Length; i )
{
switch (directions[i])
{
case Direction.Left:
var temp1 = source[0];
for (var j = 0; j < source.Length - 1; j )
{
source[j] = source[j 1];
}
source[source.Length - 1] = temp1;
break;
case Direction.Right:
var temp2 = source[source.Length - 1];
for (int j = source.Length - 1; j > 0; j--)
{
source[j] = source[j - 1];
}
source[0] = temp2;
break;
default:
throw new InvalidOperationException($"Incorrect {directions[i]} enum value.");
}
}
return source;
}
}
And this is my little code on a seperate programtrying recursion:
public static int[] Shift(int[] source, Direction[] directions)
{
if (source is null || directions is null)
{
throw new ArgumentNullException(nameof(source));
}
ShiftRecursively(source, source.Length, directions, directions.Length);
}
public static int ShiftRecursively(int[] sourceShift, int n, Direction[] currentDirection, int iterations)
{
if (iterations == 0)
{
}
if (currentDirection == Direction.Left)
{
// Handle "left" shift.
}
else if (currentDirection == Direction.Right)
{
// Handle "right" shift.
}
else
{
throw new InvalidOperationException($"Incorrect {currentDirection} enum value.");
}
}
CodePudding user response：
Disclaimer: I already established in comments, that I do not think this is a "good" example of where using recursion would actually be a smart thing to do. So, I'll not focus on that or other details. Just pure "how to do the recursion".
Let's start on your approach:
public static int ShiftRecursively(int[] sourceShift, int n, Direction[] currentDirection, int iterations)
{
// "n" is superfluent, here.
// I guess you are trying to model a stop-condition here?
if (iterations == 0)
{
}
// this is ok vv
if (currentDirection == Direction.Left)
{
// Handle "left" shift.
}
else if (currentDirection == Direction.Right)
{
// Handle "right" shift.
}
else
{
throw new InvalidOperationException($"Incorrect {currentDirection} enum value.");
}
// Now what's missing is the next layer of recursion ...
}
Now, what I would change that into:
public static int[] ShiftRecursively(int[] sourceShift, Direction[] directions, int iteration = 0)
{
// Stopping condition
if( iteration == directions.Length ) return sourceShift;
// iteration shall be increased in each recursion step,
// so we need to check if there are steps left to take.
// If not: Stop recursion = just return input.
// Data mutation
Direction currentDirection = directions[iteration];
// => factored out the application of 1 shift operation.
// Makes your code "cleaner".
int[] resultShift = Shift(sourceShift, currentDirection);
// Next layer of recursion
return ShiftRecursively(resultShift, directions, iteration 1);
}
Starting call : int[] result = ShiftRecursively(source, directions);
Note that this is only one type of possible recursion scenarios. Basically we can differenciate, when the next step is triggered in relation to when the current mutation is applied. That means:
- You can apply the current mutation and use that result as input for next recursion step.
- Or you can pass input to next recursion step and mutate the result.
- Or you can do even both.
Which one to chose depends on the application.
CodePudding user response：
Let's start from general case: shift left (postive) or right (negative):
public static T[] MakeShift<T>(T[] source, int shift) {
if (source is null)
throw new ArgumentNullException(nameof(source));
if (source.Length == 0)
return Array.Empty<T>();
// A pinch of modular arithmetics:
// - negative shifts are converted into Length Shift
// - on large shifts (|Shift| > Length) we take remainder
shift = (shift % source.Length source.Length) % source.Length;
T[] result = new T[source.Length];
Array.Copy(source, shift, result, 0, source.Length - shift);
Array.Copy(source, 0, result, source.Length - shift, shift);
return result;
}
Then we are ready to implement your signature:
public static int[] Shift(int[] source, Direction[] directions) {
if (source is null)
throw new ArgumentNullException(nameof(source));
if (directions is null)
throw new ArgumentNullException(nameof(directions));
int moves = 0;
// No Linq .Sum(), just a loop as we want
foreach (var dir in directions)
moves = (dir == Direction.Left ? 1 : -1);
return MakeShift(source, moves);
}
If you insist on recoursive solution, which is not efficient for the problem:
private static int[] ShiftRecursively(int[] source, Direction[] directions, int index) {
if (index < 0 || index >= directions.Length)
return source;
return ShiftRecursively(MakeShift(
source,
directions[index] == Direction.Left ? 1 : -1,
directions,
index 1));
}
public static int[] ShiftRecursively(int[] source, Direction[] directions) {
if (source is null)
throw new ArgumentNullException(nameof(source));
if (directions is null)
throw new ArgumentNullException(nameof(directions));
return ShiftRecursively(source, directions, 0);
}