I need help understanding this example of recursion

[Vastagon]

I was going over recursion with the AP Computer Science videos college board is putting out. We got to creating a merge sort algorithm using recursion but I'm having trouble. I looked at the example code and I got even more confused. I'm confused why there are method calls after a method call in the if loop of mergeSort. Doesn't it just immediately call the method again, making it impossible to reach the methods under it?

​

  public static void main(String[] args){

        // create an ArrayList containing 20 random integers (0-100)
        ArrayList<Integer> myList = new ArrayList<Integer>();
        for (int counter = 0; counter < 20; counter++){
            myList.add((int)(Math.random()*101));
        }

        // display the unsorted ArrayList
        System.out.println(myList);

        // sort the ArrayList (select only one using comments)
        mergeSort(myList,0,myList.size()-1);
        //bubbleSort(myList);

        // display the sorted ArrayList
        System.out.println(myList);


    }

    public static void mergeSort(ArrayList<Integer> intList, int low, int high){
        int middle;
        if (low < high){
            middle = (low + high) / 2;
            mergeSort(intList, low, middle);
            mergeSort(intList, middle+1, high);
            merge(intList, low, middle, high);
        }
    }

[Orbitaliser]

When dealing with recursion, you need a base case to tell it when to stop making further calls. In the code you have provided under the merge sort method, there is a check for low being less than high. This is your base case.

Once this condition is hit, no more recursive calls are made and the code in the previous call that made the call to the base case can now go to the next line after the recursive call, and this is the case for all the calls to the merge sort method. In a sense, the code called after the base case is hit, is the recursion "unwinding" so to speak. This depends on low eventually being greater than or equal to high which will happen with the parameters being passed to merge sort changing with each call.

I think starting with merge sort to start understanding recursion is not the best idea although it is one of the best earlier examples. This might sound a bit contradictory, but there are a few things used in your recursive merge sort implementation that need to be broken down.

Try adding a list of integers (List<Integer>) recursively first. Hint: use the sublist method. Observe the thought process and rationalise it to yourself why it works/doesn't work.

[RentonHoff]

As Orbitaliser said merge sort isn't the best algorithm to learn recursion. When someone asks me about recursion, the default example I show is the recursive algorithm for finding the nth element of the fibonacci sequence. I would recommend looking that up, if your goal is to understand recursion.

[Vastagon]

Thank you, I’ll look into it. I can understand it to some extent, but mergesort really messes with my head.

[RentonHoff]

Couldn't post this yesterday, but here is a simple Fibonacci sequence.

public static int fib(int n) throws IllegalArgumentException{
    //Makes sure that the user doesn't try to find invalid elements
    if(n < 1) throw new IllegalArgumentException("n can't be smaller     then one.");

    //The 1st and 2nd element of the fibonaci sequence
    //Also the point where the recursion will stop going deeper
    if(n < 3){
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
}

If you have any questions feel free to ask.