C#多次旋转数组递归（左，右）

Question

递归实现对我来说是一个令人困惑的主题。我想了解如何将普通方法准确地“翻译”为递归方法，经过一些研究后我仍然有点困惑，尤其是在第一步（递归停止的地方）。

这个任务是左右旋转一个数组： [TestCase(new[] { 1, 2 }, new[] { Direction.Left, Direction.Left, Direction.Right }, ExpectedResult = new[] { 2, 1 })]

我不想对此使用 linq，我们可以使用 Array.Copy 和 indices 而不是我的标准方法。

这是我要翻译的代码：

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

这是我在尝试递归的单独程序中的小代码：

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

Answer 1

免责声明：我已经在评论中确定，我认为这不是使用递归实际上是明智之举的“好”示例。所以，我不会关注那个或其他细节。只是纯粹的“如何进行递归”。

让我们开始您的方法：

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

现在，我要把它改成：

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

开始通话：int[] result = ShiftRecursively(source, directions);

注意这只是一种可能的递归场景。基本上我们可以区分，何时触发下一步与应用当前突变的时间有关。这意味着：

您可以应用当前突变并将该结果用作下一个递归步骤的输入。
或者您可以将输入传递给下一个递归步骤并改变结果。
或者你甚至可以两者都做。

选择哪一个取决于应用程序。

Answer 2

让我们从一般情况开始： shift 左（正）或右（负）：

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

那么我们准备实施您的签名：

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

如果你坚持递归解决方案，这对问题来说效率不高：

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

C#多次旋转数组递归（左，右）

C# rotate array recursive (left, right) multiple times

c#

arrays

recursion

enums

rotation