递归实现冒泡排序：n递增的写法是否符合递归规范？

问题描述 #

我在编写递归实现冒泡排序的方法时，将基准情况设为数组长度，递归调用时n从0递增至array.length-1。但看到他人的代码均将基准情况设为1，递归时n从array.length递减至1。我知道两种写法的递归次数相同、输出结果一致，但查阅递归定义发现输入应逐渐减小，而我的代码中n是递增的，因此疑惑：即便输出正确，我的写法是否错误？

我的代码 #

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleRecursion(int arr[],int n){
        if (n==arr.length){
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = 0;i<arr.length-1-n;i++){
            if (arr[i]>arr[i+1]){
                int temp;
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        bubbleRecursion(arr, n+1);
    }

    public static void main(String[] args) {
        int[] array = {3,1,4,1,5,9,2,6};
        bubbleRecursion(array,0);
    }
}

他人代码 #

public class BubbleSort {
    public static void sortingRecursion(int[] arr, int n){
        if (n == 1){
            return;
        }
        for (int i = 0;i < n-1;i++){
            if (arr[i]>arr[i+1]){
                int temp;
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        sortingRecursion(arr, n-1);
    }

    public static void main(String[] args) {
        int[] array = {3,1,4,1,5,9,2,6};
        sortingRecursion(array, array.length);
        System.out.println(Arrays.toString(array));
    }
}

解答 #

你的写法完全正确，不存在错误，只是递归的「问题规模」定义角度不同而已。

递归的核心是把问题拆解为规模更小的子问题，直到触达基准情况，但这里的「规模大小」不是看参数的数值增减，而是看参数对应的待处理问题的范围：

• 他人的代码中，n代表当前需要处理的数组长度，每次递归n-1，意味着待排序的未有序部分长度在减小，符合直观的「问题规模缩小」；
• 你的代码中，n代表已经完成排序的尾部元素个数，每次递归n+1，本质是未排序的前半部分长度在递减（arr.length-1-n就是未排序区间的上限），问题规模同样在缩小，只是用已完成的部分来衡量而已。

两种写法的逻辑等价：

1. 他人代码每次把最大的元素「冒」到当前未排序区间的末尾；
2. 你的代码每次也是把最大的元素冒到末尾，n记录已经排好的尾部元素数量，所以循环的上限是arr.length-1-n，避免重复处理已经有序的尾部。

另外，你的代码在基准情况时直接打印数组，而他人代码是返回后再处理打印，这只是输出时机的差异，不影响排序逻辑的正确性。

总结：递归的核心是问题规模的拆解，参数的增减只是表象，只要每次递归都在逼近基准情况，且逻辑正确，就没有问题。你的实现完全符合递归的要求，是正确的写法。

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