рекурсивный метод не выполняется должным образом

У меня есть задание по программированию для класса Java начального уровня (проблема суммы подмножества) - по какой-то причине мой рекурсивный метод не выполняется должным образом (он просто идет прямо в конец метода и распечатывает отсортированный список). Любая помощь будет оценена по достоинству - я новичок, и рекурсивные функции меня действительно сбивают с толку.

package programmingassignment3;

import java.io.*;
import java.util.*;

public class ProgrammingAssignment3 {

    static int TARGET = 10;
    static ArrayList<Integer> list = new ArrayList<>();
    static int SIZE = list.size();

    public static void main(String[] args) {
        populateSortSet();
        sumInt(list);
        recursiveSS(list);
    }//main

    public static void populateSortSet() {
        try {
            File f = new File("set0.txt");
            Scanner input = new Scanner(f);
            while (input.hasNext()) {
                int ele = input.nextInt();
                if (ele < TARGET && !list.contains(ele)) {
                    list.add(ele);
                }//if
            }//while
            Collections.sort(list);
        }//try
        catch (IOException e) {
            e.printStackTrace();
        }//catch
    }//populateSet

    public static void recursiveSS(ArrayList<Integer> Alist) {
        if (Alist.size() == SIZE) {
            if (sumInt(Alist) == TARGET) {
                System.out.println("The integers that equal " + TARGET + "are: " + Alist);
            } //if==TARGET  
        }//if==SIZE
        else {
            for (int i = 0; i < SIZE; i++) {
                ArrayList<Integer> list1 = new ArrayList<>(Alist);
                ArrayList<Integer> list0 = new ArrayList<>(Alist);
                list1.add(1);
                list0.add(0);
                if (sumInt(list0) < TARGET) {
                    recursiveSS(list0);
                }//if
                if (sumInt(list1) < TARGET) {
                    recursiveSS(list1);
                }//if
            }//for
        }//else
        System.out.println("echo" + Alist);
    }//recursiveSS

    public static int sumInt(ArrayList<Integer> Alist) {
        int sum = 0;
        for (int i = 0; i < SIZE - 1; i++) {
            sum += Alist.get(i);
        }//for
        if (Alist.size() == TARGET) {
            sum += Alist.get(Alist.size() - 1);
        }//if
        return sum;
    }//sumInt
}//class

person Rebekah Williamson    schedule 03.10.2014    source источник
comment
Пожалуйста, удалите все эти ужасные комментарии (например, //if и //class) из вашего кода. Они только загромождают и не добавляют ценности. Рекурсия начинается с определения условия остановки. Что это за то, что вы пытаетесь сделать? Можете ли вы объяснить задачу о сумме подмножеств на английском языке?   -  person duffymo    schedule 03.10.2014
comment
@duffymo нет правильного или неправильного мнения относительно закрывающих комментариев в скобках. автор говорит, что она на вводном уроке программирования. если это поможет ей вспомнить, как сочетаются фигурные скобки, то это хорошая практика. я иногда использую его в C, когда мои вложенные #ifdef сбиваются с толку.   -  person Woodrow Barlow    schedule 03.10.2014
comment
@WoodrowBarlow - я думаю, что есть. Ни одна профессия не допускает такого беспорядка. Для этого и нужны настоящие IDE. Даже Eclipse может справиться с этим за вас. Это стоит услышать.   -  person duffymo    schedule 03.10.2014
comment
Комментарии в закрывающей фигурной скобке действительно требуются моему профессору. Я все еще работаю над этим - спасибо за отзыв.   -  person Rebekah Williamson    schedule 06.10.2014


Ответы (3)


Вот как бы я это сделал. Я надеюсь, что это разъясняет условие остановки и рекурсию. Как видите, статические методы не проблема:

import java.util.ArrayList;
import java.util.List;

/**
 * Demo of recursion
 * User: mduffy
 * Date: 10/3/2014
 * Time: 10:56 AM
 * @link http://stackoverflow.com/questions/26179574/recursive-method-not-properly-executing?noredirect=1#comment41047653_26179574
 */
public class RecursionDemo {

    public static void main(String[] args) {
        List<Integer> values = new ArrayList<Integer>();
        for (String arg : args) {
            values.add(Integer.valueOf(arg));
        }
        System.out.println(String.format("input values : %s", values));
        System.out.println(String.format("iterative sum: %d", getSumUsingIteration(values)));
        System.out.println(String.format("recursive sum: %d", getSumUsingRecursion(values)));
    }

    public static int getSumUsingIteration(List<Integer> values) {
        int sum = 0;
        if (values != null) {
            for (int value : values) {
                sum += value;
            }
        }
        return sum;
    }

    public static int getSumUsingRecursion(List<Integer> values) {
        if ((values == null) || (values.size() == 0)) {
            return 0;
        } else {
            if (values.size() == 1) { // This is the stopping condition
                return values.get(0);
            } else {
                return values.get(0) + getSumUsingRecursion(values.subList(1, values.size())); // Here is recursion
            }
        }
    }
}

Вот случай, который я использовал для проверки:

input values : [1, 2, 3, 4, 5, 6]
iterative sum: 21
recursive sum: 21

Process finished with exit code 0
person duffymo    schedule 03.10.2014

То, что вы делаете на уровне класса:

static ArrayList<Integer> list = new ArrayList<>();
static int SIZE = list.size();

означает, что SIZE будет инициирован как 0 и останется 0 (даже если вы добавите элементы в список).

Это означает, что код внутри for-loop будет выполнен 0 раз.

Попробуйте что-то вроде:

public class ProgrammingAssignment3 {
    private static int initialSize;

    //...
    public static void populateSortSet() {
        //populate the list
        initialSize = list.size();
    }

Таким образом, вы не устанавливаете значение переменной size до тех пор, пока список не будет фактически заполнен.

При этом в вашем коде есть довольно много других странных вещей, поэтому я думаю, вам нужно точно указать, что вы пытаетесь решить здесь.

person Tobb    schedule 03.10.2014
comment
это из-за статического ключевого слова? - person Woodrow Barlow; 03.10.2014
comment
Нет, то же самое и с нестатическими переменными. Вы назначаете int по значению, а не по ссылке, поэтому он будет иметь значение размера списка на момент назначения. - person Tobb; 03.10.2014
comment
о, я даже не заметил, что OP создал переменную для размера. Я взглянул на код и предположил, что вы имеете в виду, что list.size() всегда будет равен нулю, и был сбит с толку. - person Woodrow Barlow; 03.10.2014
comment
Суть проблемы суммы подмножества, как объяснил мой профессор, состоит в том, чтобы ввести набор данных (список массивов - импортированный из файла .txt), а затем найти подмножество этого списка, которое в сумме составляет целевое целое число, обязательно удаляя любые повторяющиеся элементы и любые элементы, превышающие целевое целое число. Например, S={2, 6, 8, 5, 1, 10} и Target = 9, есть два подмножества (решения): S1={2, 6, 1} и S2={8, 1}. - person Rebekah Williamson; 06.10.2014

Спасибо всем. Я очень ценю помощь. Я понял проблему, и решение выглядит следующим образом (комментарии с закрывающей фигурной скобкой удалены для удовольствия от чтения @duffymo):

public class ProgrammingAssignment3 {

    static int TARGET = 6233;
    static ArrayList<Integer> set = new ArrayList<>();
    static int SIZE;
    static int count = 0;

    public static void populateSortSet() {
        try {
            File f = new File("set3.txt");
            Scanner input = new Scanner(f);
            while (input.hasNext()) {
                int ele = input.nextInt();
                if (ele < TARGET && !set.contains(ele)) {
                    set.add(ele);
                }
            }
            Collections.sort(set);
            SIZE = set.size();
            System.out.println("The original sorted set: " + set + "\t subset sum = " + TARGET);
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void recursiveSS(ArrayList<Integer> list) {
        if (list.size() == SIZE) {
            if (sumInt(list) == TARGET) {
                System.out.print("The Bit subset is: " + list + "\t");
                System.out.println("The subset is: " + getSubset(list));
                count++;
            }  
        }
        else {
            ArrayList<Integer> list1 = new ArrayList<>(list);//instantiate list1
            ArrayList<Integer> list0 = new ArrayList<>(list);//instantiate list0
            list1.add(1);
            list0.add(0);
            if (sumInt(list0) <= TARGET) {
                recursiveSS(list0);
            }
            if (sumInt(list1) <= TARGET) {
                recursiveSS(list1);
            }
        }
    }

    public static int sumInt(ArrayList<Integer> list) {
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == 1) {
                sum += set.get(i);
            }
        }
        return sum;
    }

    public static ArrayList<Integer> getSubset(ArrayList<Integer> list) {
        ArrayList<Integer> l = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == 1) {
                l.add(set.get(i));
            }
        }
        return l;
    }
}
person Rebekah Williamson    schedule 13.11.2014