带case语句的递归程序Big O复杂度是否与迭代版本一致为O(n)？

你的判断完全正确，该递归实现的时间复杂度确实是O(n)，和对应迭代版本的时间复杂度一致。

推理过程 #

你提供的实现代码如下：

public static int recursion(int i, int j, String swap) {
    int[] testList = {0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21};
    if (j == 10) {
        return testList[10];
    }
    if (i == 10 ) {
        swap = "Yes";
    }

    switch (swap) {
        case "No":
            System.out.print(testList[i] + " ");
            i -= 1;
            break;
        case "Yes":
            System.out.print(testList[j] + " ");
            j += 1;
            break;
    }
    return recursion(i, j, swap);
}
public static void main(String[] args){
    String swap = "No";
    int i = 20;
    int j = 0;
    System.out.println(recursion(i, j, swap) + " ");
}

执行逻辑和复杂度分析：

• 整个递归过程只会执行和数组长度相等的调用次数：
  1. 初始状态下swap为No，i从20开始倒序打印，累计执行11次递归调用后i降到10，swap切换状态
  2. 状态切换后j从0开始正序打印，累计执行10次递归调用后j升到10，触发终止条件返回
• 每次递归调用内部仅包含条件判断、分支选择、变量修改、打印这几个*O(1)*级别的操作，没有额外的嵌套遍历开销
• 总执行次数和数组规模n呈严格线性关系，所以时间复杂度为O(n)。

补充说明：Java本身不优化尾递归，所以这段代码的空间复杂度为O(n)（递归栈占用空间），比迭代版本的*O(1)*空间复杂度更高，但这是空间维度的差异，不影响时间复杂度的结论。

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