Recursion loop runs again WITHOUT call to it in Java

Question

Can anyone see why this example of sorting recursion keeps running after second call to the recursive method. When i == high_index where they are both 2 after the second call for some reason this code I found on internet runs the same line again but with some weird values of i=4 and high_index=6. I just can't see the bug. All the recursion should stop after second time and the array should be sorted.

See line with comment //WHY DOES THIS LINE RUN TWICE IN A ROW WITH DIFFERENT VALUES?????

package dataClass;

import java.util.Arrays;
public class QuickSort {

    private int temp_array[];
    private int len;

    public void sort(int[] nums) {

        if (nums == null || nums.length == 0) {
            return;
        }
        this.temp_array = nums;
        len = nums.length;
        quickSort(0, len - 1, "First");
        //System.out.println("what");
    }
     private void quickSort(int low_index, int high_index, String one_two) {
        System.out.println("***" + low_index + " " + high_index);
        System.out.println(one_two);
        int i = low_index;
        int j = high_index;
        // calculate pivot number 
        int pivot = temp_array[low_index+(high_index-low_index)/2];
        // Divide into two arrays
        System.out.println(Arrays.toString(temp_array));
        while (i <= j) {
               while (temp_array[i] < pivot) {
                   System.out.println("This happens");
                i++;
            }
            while (temp_array[j] > pivot) {
                System.out.println("Or this happens");
                j--;
            }
            if (i <= j) {
                System.out.println("Execute");

                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
                System.out.println("i=" + i + " high_index=" + high_index);
            }
        }
        // call quickSort() method recursively

        if (low_index < j) {
            System.out.println("Running 1");
            System.out.println(j + " " + low_index);
            quickSort(low_index, j, "Run 1---------");            
        }


        System.out.println("**i=" + i + " **high_index=" + high_index);  // WHY DOES THIS LINE RUN TWICE IN A ROW WITH DIFFERENT VALUES?????
        System.out.println("Why run again without call to quickSort()?");
        if (i < high_index) {
            System.out.println("Running 2");
            System.out.println(i + " " + high_index);
            quickSort(i, high_index, "Run 2---------");
        }


    }

    private void exchangeNumbers(int i, int j) {
        int temp = temp_array[i];
        temp_array[i] = temp_array[j];
        temp_array[j] = temp;
    }

     // Method to test above
    public static void main(String args[])
    {
        QuickSort ob = new QuickSort();
        int nums[] = {7, -5, 3, 2, 1, 0, 45};
        System.out.println("Original Array:");
        System.out.println(Arrays.toString(nums));
        ob.sort(nums);
        System.out.println("Sorted Array");
        System.out.println(Arrays.toString(nums));
    }
}

Step through it with a debugger and all will be revealed. Hint: imagine there was a recursive call made within the first conditional block, and within that call there is no invocation of the second conditional block? 1) What was the last thing printed from within the recursive call? 2) What happens immediately after returning from that recursive call? — pjs
– pjs, Commented Jun 9, 2019 at 5:44
ahh now with the answer given that makes sense, it runs the first call to initial method and continues, actually it finishes all the previous calls with the last values within those calls for i, j, low and high index. thanks — Brian Wiley
– Brian Wiley, Commented Jun 9, 2019 at 6:51

TechFree · Accepted Answer · 2019-06-09 06:33:10Z

1

Though I did not really trace the full logic here, but I believe 'return' statement is missing. When control raaches the recursive method call invocation, the method is executed again. However, once this execution of recursive call is complete, execution of the original method call resumes, and there you see the unexpected behavior !

Return (break execution flow) at other places too when making recursive calls to prevent further code block execution as intended

if (low_index < j) {
            System.out.println("Running 1");
            System.out.println(j + " " + low_index);
            quickSort(low_index, j, "Run 1---------");
            //recursive code invoked, but prevent the control to process downstream code
            return;
        }

answered Jun 9, 2019 at 6:33

TechFree

3,0241 gold badge24 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursion loop runs again WITHOUT call to it in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related