如何使用递归实现数组填充 替代循环填充的递归方法求解

实现思路 #

递归的核心逻辑是拆分问题：

• 我们要填充从索引currentIndex开始的子数组，填入的初始值为currentValue
• 终止条件：currentIndex超出数组长度时，直接返回数组
• 递归逻辑：先给当前索引位置赋值为currentValue，再递归填充下一个索引，填入值减1即可

完整代码实现 #

static void Main(string[] args)
{
    int n = 6;
    int[] nums = new int[n];
    // 调用递归方法，从索引0开始，初始填入值为n
    nums = FillArrayRecursive(nums, 0, n);
    
    for(int i = 0;i < nums.Length; i++)
    {
        Console.WriteLine(nums[i]); // 输出6,5,4,3,2,1
    }
}

/// <summary>
/// 递归填充数组的方法
/// </summary>
/// <param name="nums">待填充的数组</param>
/// <param name="currentIndex">当前要填充的数组索引</param>
/// <param name="currentValue">当前索引要填入的值</param>
/// <returns>填充完成的数组</returns>
static int[] FillArrayRecursive(int[] nums, int currentIndex, int currentValue)
{
    // 递归终止条件：索引超出数组范围，结束递归
    if (currentIndex >= nums.Length)
    {
        return nums;
    }
    // 给当前位置赋值
    nums[currentIndex] = currentValue;
    // 递归填充下一个位置，值减1
    return FillArrayRecursive(nums, currentIndex + 1, currentValue - 1);
}

复杂度说明 #

• 时间复杂度：O(n)，总共需要执行n次赋值操作，和循环版本一致
• 空间复杂度：O(n)，递归调用栈最多会有n层，比循环版本的O(1)额外空间要高，这也是递归实现的常见取舍

如果你不想额外传入索引参数，也可以把方法封装成和你原有调用方式一致的重载版本：

// 对外暴露的方法，和你原来的调用参数完全一致
static int[] fillArray(int[] nums, int n)
{
    return FillArrayRecursive(nums, 0, n);
}

// 内部递归实现的私有方法
private static int[] FillArrayRecursive(int[] nums, int currentIndex, int currentValue)
{
    if (currentIndex >= nums.Length) return nums;
    nums[currentIndex] = currentValue;
    return FillArrayRecursive(nums, currentIndex + 1, currentValue - 1);
}

内容的提问来源于stack exchange，提问作者Joe Kennedy