Infinite recursion in Java Program

Question

The line of code return tournamentTreeKSelection(listToArray(list), k); is causing an infinite recursion in my program and I am unable to discover the exact cause.

import java.util.ArrayList;
import java.util.Arrays;

public class TournamentTree {

public static int tournamentTreeKSelection(int[] data, int k) {
    ArrayList<Integer> list = new ArrayList<>();
    ArrayList<Integer> list2 = new ArrayList<>(list);

        for(int i = 0; i < data.length - 1; i += 2) {
            list.add(max(data[i] , data[i + 1]));
        }

        if(list.size() % 2 != 0) list.add(-1);

        if(k > 1 && list.size() == 1) {
            for(int i = 0; i < list2.size(); i++)
                if(list2.get(i) == list.get(0))
                    list2.remove(i);

            return tournamentTreeKSelection(listToArray(list2),--k);
        }

        if(list.size() == 1) return list.get(0);

        return tournamentTreeKSelection(listToArray(list), k);

}

public static int max(int a, int b) {
    return a > b ? a : b;
}

public static int[] listToArray(ArrayList<Integer> arr) {
    int[] arr2 = new int[arr.size()];
    for(int i = 0; i < arr.size(); i++)
        arr2[i] = arr.get(i);

    return arr2;
}


}

I have done a hand trace using the array [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] and I am able to get down to a single element [10], why then is the run of the program causing a stack overflow ?

Answer 1

Here is how I would do that, considering more or less the same algorithm:

• find the max value
• if k is 1, return that value
• recurse with the list of values filtered of that max value, and k - 1.

Like that

public static int tournamentTreeKSelection(int[] data, int k) {
    int max = -1;
    for (int i : data) {
        max = Math.max(max, i);
    }
    if (k == 1) {
        return max;
    }
    List<Integer> results = new ArrayList<>();
    for (int i : data) {
        if (i != max) {
            results.add(i);
        }
    }
    return tournamentTreeKSelection(listToArray(results), k - 1);
}

The part where you select half of the item makes no sense to me, as you lose information of the relative position of the other elements. (So I just removed it).

Answer 2

A better answer to giving you a solution is for you to understand the concept of a binary heap (tournament tree).

There are plenty of questions asked on this site alone, and here is a good explanation of your problem.

Note - this is slighlty different, find up to kth largest elements

Answer

Answer 3

njzk2's answer is indeed simpler than what you are trying to do, since it eliminates the tournament tree concept.

If you are required to use the tournament implementation, I'll give you some pointers regarding why your code doesn't work.

Once you find the max number using the tournament method, you should remove it from the original list and then call the method again for an array of the remaining n-1 numbers and k-1, since your task is now to find the k-1'th highest number of the remaining numbers.

You try to do it with list2, but you are not initializing list2 correctly. You initialize it to be empty. You must keep track of the original array, so that you can remove from it the max element each time you find the max element of the remaining array. For this purpose, you should add another array parameter to your method. Initially it will contain the original array, and each time you find the maximum number, it will contain the array that you get by removing the maximum number.

Perhaps you can simplify the implementation by using two recursive methods, one method for finding the maximum number using a tourmant tree and a second method that would use the first one to find the k'th highest number.

This makes sense, since you have two different recursive steps that don't work well together - one reduces the array in half until you reach a single element while the other removes a single element from the array and reduces k, until k reaches 1.

public static int getKthElement (int[] data, int k)
{
    int max = findMaxByTournament (data);
    if (k == 1) {
        return max;
    } else {
        // create an array containing the lowest data.length-1 
        // elements of the data array
        int[] data2 = new int[data.length-1];
        boolean foundMax = false;
        int count = 0;
        for (int n : data) {
            if (n < max || foundMax) {
                data2[count++] = n;
            }
            if (n == max) {
                foundMax = true; // this flag is required in case more than
                                 // one element has the maximum value
            }
        }
        return getKthElement (data2, k - 1);
    }
}

public static int findMaxByTournament (int[] data)
{
    // here you do something similar to what you already did - find the
    // max number of each pair and call this method recursively with half
    // the elements until you have one remaining element 
}

Answer 4

I added comment to code (I find a lot of problem with recursion):

public static int tournamentTreeKSelection(int[] data, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>(list);


        for(int i = 0; i < data.length - 1; i += 2) {
            list.add(max(data[i] , data[i + 1]));
        }

        if(list.size() % 2 != 0) list.add(-1);



    if(k > 1 && list.size() == 1) { // if list.size() % 2 != 0, we never go to this, 
// because we never decrease list.count and never decrease k before this block  
            for(int i = 0; i < list2.size(); i++)
                if(list2.get(i) == list.get(0))
                    list2.remove(i);

            return tournamentTreeKSelection(listToArray(list2),--k);
        }

        // if we add two element or more in list, we never stop after that
        if(list.size() == 1) return list.get(0);

        // we never decrease k, so call tournamentTreeKSelection with same parameters -> it's run forever   
        return tournamentTreeKSelection(listToArray(list), k);    
}

// main problem that listToArray returns copy of list, but you run tournamentTreeKSelection(listToArray(list), k) with same parameters, if you listToArray returns int[] less that list, tournamentTreeKSelection can stop 
public static int[] listToArray(ArrayList<Integer> arr) {
...