CODEWITHSUNDEEP
javaalgorithm
user4747724
user4747724

Reputation:

How can I get a recursive algorithm to return a value before it finishes running?

I have the algorithm below, the goal of which is to find all the possible permutation of a series of numbers given they can switch signs. When it reaches a leaf node in the tree it will call another method which iterates over a list to see if the sum of that permutation equals a number in the series. I'm also fiddling with an algorithm to see if a subset of a series is less than a given number. For example of 60, 35, and 40, the numbers 60 + 40 < 110. My problem is that once a branch in the tree is found to be what I need the other branches are still going to be explored. How can I interrupt this? Right now all I have is a system.exit(1);

public static int PlusMinus(Node start, Node node, int Sum){
    Node head = start;
    boolean Success = false;
    if(node != null){
         PlusMinus(head, node.next, node.item+Sum);
         PlusMinus(head, node.next, node.item*(-1)+Sum);
         return Sum;
    }

    else{
        Success = getSum(Sum,start);
        if(Success == true){
            System.out.println("Yes");
            System.exit(1);
            return 1;
        }
    }
    return 0;
}

Looking at the above, my original intention was to have it return the leaf node sum to the calling program. As I understand it from stepping through the program though, if the rightmost branch is the correct permutation it won't just end at that leaf node return value. It will still jump back to the parent and then proceed to test the next branch.

Upvotes: 1

Views: 86

Answers (1)

Eran
Eran

Reputation: 393811

Your return value should be a boolean, that indicates if you found the sum you were looking for. Since you are not using the current value being returned by your method, it looks like you don't need it.

public static boolean PlusMinus(Node start, Node node, int Sum){
    Node head = start;
    if(node != null) {
         // you should return true if either of the recursive calls returned true
         if (PlusMinus(head, node.next, node.item+Sum))
             return true;
         return PlusMinus(head, node.next, node.item*(-1)+Sum);
    } else {
        return getSum(Sum,start);
    }
}

EDIT :

I don't know what your getSum method does, but it looks like you don't need it. You should pass to the next recursive call either Sum-node.item or Sum+node.item, depending on the sign with which the current node should participate in the sum, and check if you reached 0 when you get to a leaf node.

public static boolean PlusMinus(Node start, Node node, int Sum){
    if(node != null) {
         // you should return true if either of the recursive calls returned true
         if (PlusMinus(head, node.next, Sum - node.item))
             return true;
         return PlusMinus(head, node.next, Sum + node.item);
    } else {
        return Sum == 0;
    }
}

Upvotes: 1

Related Questions