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 ?

Be careful of the term infinite recursion. Normally this is not possible as excessive recursion will inevitably cause the call stack to overflow. — Luke Joshua Park
– Luke Joshua Park, Commented Dec 3, 2015 at 21:06
Note that list2 is always empty, since you initialize it with ArrayList<Integer> list2 = new ArrayList<>(list); when list is still empty. This means your iteration over list2 does nothing. I'm assuming this is not the intended behavior. — Eran
– Eran, Commented Dec 3, 2015 at 21:12
@MutatingAlgorithm I don't know. I don't understand what your algorithm is supposed to do. for example, for(int i = 0; i < list2.size(); i++) does nothing because list2 is empty. — njzk2
– njzk2, Commented Dec 3, 2015 at 21:13
Possible duplicate of What is a debugger and how can it help me diagnose problems — Raedwald
– Raedwald, Commented Dec 18, 2015 at 19:39

Siyual · Accepted Answer · 2015-12-18 19:14:26Z

4

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).

edited Dec 18, 2015 at 19:14

Siyual

17k8 gold badges47 silver badges60 bronze badges

answered Dec 3, 2015 at 21:29

njzk2

39.4k7 gold badges72 silver badges111 bronze badges

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

1 Comment

Yassin Hajaj Over a year ago

Sometimes it is indeed better to offer a better answer like you do.

Community · Accepted Answer · 2017-05-23 11:59:11Z

1

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

edited May 23, 2017 at 11:59

CommunityBot

11 silver badge

answered Dec 3, 2015 at 21:42

Eric G

9261 gold badge10 silver badges30 bronze badges

Comments

Eran · Accepted Answer · 2015-12-03 21:59:05Z

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 
}

Slava Vedenin · Accepted Answer · 2015-12-03 21:41:51Z

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) {
...

Collectives™ on Stack Overflow

Infinite recursion in Java Program

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related