How to correctly implement bubble sort recursively?-CodePudding

I'm writing a method to realize bubble sort with recursion, and my base case is "the length of array", in that case, I have to recursively call the function from "0" to array.length-1, however, as I went through the codes from other people, I found them all using the base case "1",and that is running the recursion from array.length to "1". I know both of our recursion run the same number of times and get the same result, but I'm just a bit confused, does it mean my understanding of recursion is wrong ?

my code :

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

bubbleRecursion(array,0);

others' code:

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


sortingRecursion(array, array.length);

I then looked up the definition of recursion, it seems that the input should get smaller and smaller every time, but my code is increasing the value of n every time, so now I'm a bit confused, does it mean my code is a wrong answer though the output is correct?

Could anyone help me? thank you

CodePudding user response：

the input should get smaller and smaller every time, but my code is increasing the value of n every time

That is true, but since your use of n is different than in the other version, you still reduce the input at every time: the loop condition will kick in sooner at each next recursion, since array.length - 1 - n will get smaller. So no worries, also your version makes the problem smaller at each recursive step.

as I went through the codes from other people, I found them all using the base case "1"

This makes sense, as the loop condition will be false in that case: i < n - 1 will be false when n is 1.

You could do the same in your version by changing the base case test to if (n==array.length-1).

It doesn't mean your current base case test is terribly wrong though. It just means that when n is array.length-1 the loop will still be executed, but it will not iterate, because the loop condition is immediately false. And then the next recursive call will hit the base case anyway. So it just means there is one more recursive call that doesn't do anything.

CodePudding user response：

Your base case should be if (n == 0) return;

Solution

public static void sortingRecursion(int[] arr, int n){
  if (n == 0){
     return;
  }
  for (int i = 0;i < n;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);
}

Usage

int array[] = {5, 4, 7, 2, 8};
sortingRecursion(array, array.length - 1);
System.out.println(Arrays.toString(array));

Output

[2, 4, 5, 7, 8]

Edited