Recursion never ends even with return statement

Go To StackoverFlow.com

1

I may not understand what the return statement does(I thought it just returned a variable and allowed me to exit the loop). I'm trying to get a better understanding of recursions but this never seems to exit.

import java.util.Arrays;
import java.util.List;

public class main {

    public static void main(String[] args) {
        System.out.println("Starting..");
        List<Integer> list_to_start = Arrays.asList(new Integer[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}); 
        String[] name_of_list_to_start = new String[] {"grapes", "Strawberries", "Raspberries", "Blackberries", "Pineapples", "Oranges", "Prunes", "Pears", "cherries", "Peaches", "Apples"};       
        System.out.println(list_to_start.size());
        counter(list_to_start.size(), list_to_start, name_of_list_to_start);
    }

    private static void counter(int length, List<Integer> list_to_start, String[] name_of_list_to_start) {
        // TODO Auto-generated method stub
        if (length == 0) {
            System.out.println("List is empty now");
            for (int i = 0; i>=list_to_start.size(); i++) {
                System.out.println(name_of_list_to_start[i] + " = " + list_to_start.get(i));
            }
            return;
        }   
        Integer x_lenght = (Integer) list_to_start.get(length-1);
        for (int i = 0; i<=5; i++) {
            //System.out.println(i);
            if (length != 0 ) {
                list_to_start.set((length-1), i);
                counter((length-1), list_to_start, name_of_list_to_start);
                list_to_start.set((length-1), 0);
            }
        }
    }
}

Basically what I'm trying to do is, using a recursion, figure out all the combinations of 0-5 for 10 different fruits(this is just for me to learn, not homework..not a student).

Any idea what I'm doing wrong? Why is this program not stopping with the return statement?

update: in case anyone ever has the same problem, here's the working version of the above code(keeping the broken code so the answers make sense):

import java.util.Arrays;
import java.util.List;

public class main {

    public static void main(String[] args) {
        System.out.println("Starting..");
        List<Integer> list_to_start = Arrays.asList(new Integer[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}); 
        String[] name_of_list_to_start = new String[] {"grapes", "Strawberries", "Raspberries", "Blackberries", "Pineapples", "Oranges", "Prunes", "Pears", "cherries", "Peaches", "Apples"};       
        System.out.println(list_to_start.size());
        counter(list_to_start.size(), list_to_start, name_of_list_to_start);
    }

    private static void counter(int length, List<Integer> list_to_start, String[] name_of_list_to_start) {
        // TODO Auto-generated method stub
        if (length == 0) {
            //System.out.println("List is empty now");
            for (int i = 0; i<list_to_start.size(); i++) {
                //(name_of_list_to_start[i] + " = " + list_to_start.get(i));
                int k = i +2;
                int y = k -1;
            }
            //System.out.println("********");
            return;
        }   
        Integer x_lenght = (Integer) list_to_start.get(length-1);
        for (int i = 0; i<=5; i++) {
            //System.out.println(i);
            if (length != 0 ) {
                list_to_start.set((length-1), i);
                counter((length-1), list_to_start, name_of_list_to_start);
                list_to_start.set((length-1), 0);
            }
        }
    }
}
2012-04-04 03:27
by Error_404
The line

for (int i = 0; i>=list_to_start.size(); i++) {

will cause exceptions when listtostart.size() == - Riley Lark 2012-04-04 03:37

@RileyLark I'm not reducing listtostart only length. currently I don't get any error, it just keeps going and going. - Error_404 2012-04-04 03:40
Ok. You might still reconsider whether that line does what you want it to - Riley Lark 2012-04-04 03:43


3

Are you sure this is an infinite loop, and not just a really long sequence?

On each level you loop 5 times, branching to another recursion each time. You have 10 levels, so you'll have a total of 5^10 function calls at the bottom level, or 9,765,625 System.out.println calls!

Your return statement is not in a loop. The return statement exits the current function call... but you have over 10 million function calls here, so it has to return a lot of times.

2012-04-04 03:40
by Riley Lark
Weird..when I leave it running it goes for over 5 minutes(on my macbook core duo) but when I remove the System.out.println("List is empty now"); it ends right away without displaying the list of the results..I'm even more confused now - Error_404 2012-04-04 03:43
It could just be that the System.out.println takes so long that it overloads your output buffer... your code will print "List is empty now" 10 million times - Riley Lark 2012-04-04 03:46
I think your right, didn't realize it would take so long. Amit's answer also helped as well(you were right, I had my symbol the wrong way in my if for loop)..thanks so much everyone - Error_404 2012-04-04 03:48
This type of problem is much easier to track down if you can step through the code with a visual debugger such as NetBeans - Mark Fraser 2012-04-04 03:50


3

Your condition in the for loop when length = 0 should be

i<list_to_start.size()

and as Riley said, your recursion needs to be tweaked somewhat.

2012-04-04 03:42
by Chetter Hummin
As written in the original post, the loop doesn't execute at al - Riley Lark 2012-04-04 03:48
@RileyLark My mistake. I meant the number of calls due to recursion, but typed loop instead! Thanks - Chetter Hummin 2012-04-04 03:49
Ads