Double Recursion in one method Java

Question

I am pretty sure that I thoroughly understand how the methods with only one recursion work.

Ex) calculating factorial

public int factorial(int n){  //factorial recursion
    if(n==0){
        return 1;
    }
    else{
        return n*factorial(n-1);
    }
}

For these methods, I can even picture what's going on in the stacks and what values are being returned at each stack level.

But Whenever, I encounter methods with Double Recursions, the nightmare begins.

Below is a recursion problem with double recursions from coding bat.

Ex) Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target? If yes, true. If no, false. You use 3 parameters; starting index start, An int Array nums, target int value target.

Below is the solution for this problem.

public boolean groupSum(int start, int[] nums, int target) {
    if (start >= nums.length) return (target == 0);
    if (groupSum(start + 1, nums, target - nums[start])) return true;
    if (groupSum(start + 1, nums, target)) return true;
    return false;
}

My take to understand this solution is this. Say I was given an array {2,4,8} with starting index = 0, and target value 10. So (0,{2,4,8},10) goes in through the method, the function gets re-called at

if (groupSum(start + 1, nums, target - nums[start])) return true;

so it becomes (1,{2,4,8},8) and it does over and over until start index hits
3. when it hits 3. The stack at the last level(?) goes to the second recursive call. And this is where I start losing track of what's happening.

Can anybody break this down for me? And when people use double recursion,(I know it's very inefficient and in practice, almost no one uses it for its inefficiency. But just in an attempt to understand it.)can they actually visualize what's going to happen? or do they just use it hoping that the base case and recursion would work properly? I think this applies generally to all the ppl who wrote merge sort, tower of hanoi alogrithm etc..

Any help is greatly appreciated..

you're inventing terminology here. It ain't no "double recursion" - what you've shown is an ordinary recursion. Also, like a wise person once said, `to understand recursion, you have to first understand recursion`. — , Mar 03 '16 at 12:24
well I guess I haven't understood recursion. So please enlighten me. — Hello, Mar 03 '16 at 12:24
be my guest: http://stackoverflow.com/questions/3021/what-is-recursion-and-when-should-i-use-it https://en.wikipedia.org/wiki/Recursion http://stackoverflow.com/questions/126756/examples-of-recursive-functions — , Mar 03 '16 at 12:26
It is not 'double' recursion because the 2nd call to `groupSum()` within `groupSum()` does not make the stack twice as deep. — NickJ, Mar 03 '16 at 12:28
sorry for the wrong choice of word. I thought it would be 'double' since it uses recursion twice. — Hello, Mar 03 '16 at 12:29

Eran · Accepted Answer · 2016-03-03T12:35:24.703

5

The idea of a double recursion is to break the problem into two smaller problems. Once you solve the smaller problems, you can either join their solutions (as is done in merge sort) or choose one of them - which is done in your example, which only requires the second smaller problem to be solved if solving the first smaller problem didn't solve the full problem.

Your example tries to determine if there is a subset of the input nums array whose sum is the target sum. start determines which part of the array is considered by the current recursive call (when it's 0, the entire array is considered).

The problem is broken to two, since if such a subset exists, it either contains the first element of the array (in which case the problem is reduced to finding if there's a sub-set of the last n-1 elements of the array whose sum is target minus the value of the first element) or doesn't contain it (in which case the problem is reduced to finding if there's a sub-set of the last n-1 elements of the array whose sum is target).

The first recursion handles the case where the subset contains the first element, which is why it makes a recursive call that would look for the target sum minus the first element in the remaining n-1 elements of the array. If the first recursion returns true, it means that the required subset exists, so the second recursion is never called.

The second recursion handles the case where the subset doesn't contain the first element, which is why it makes a recursive call that would look for the target sum in the remaining n-1 elements of the array (this time the first element is not subtracted from the target sum, since the first element is not included in the sum). Again, if the second recursive call returns true, if means that the required subset exists.

edited Mar 03 '16 at 12:35

answered Mar 03 '16 at 12:29

Eran

387,369
54
702
768

I think the function could have 1 improvement - it could check `target == 0` on the first line and `return true` immediately since we already reached the target - currently it unnecessarily loops through the whole array. What do you think? – radoh Mar 03 '16 at 12:34
Thank you for the reply. But could you explain why it was divided into two with or without the first element? why weren't the other elements considered? – Hello Mar 03 '16 at 12:35
@LookAtTheBigPicture There are many ways to break the problem into smaller pieces. You can consider the first two elements, and then the problem would be broken into four parts (based on whether both, none or any one of the first two elements appear in the subset having the target sum). That would make the code more complicated, though. – Eran Mar 03 '16 at 12:38
@Eran this might sound quite strange and I'm not even sure if I'm asking it right but.. like I said in the question. When people do use double recursion. Do they visualize what's gona happen to the bottom level? Take this problem for example, I just vaguely know that it will break the problem into two parts with/without the first element, but not precisely know what stacks will be made and what each stack will return. – Hello Mar 03 '16 at 12:45
@LookAtTheBigPicture You don't have to follow all the recursive calls in order to understand what's going on (though you might want to follow it with some small input in order to convince yourself that it actually works). It's enough to understand how each recursive call solves a smaller problem, understand that the stopping condition solves the problem for the edge case (empty array in your example), and understand how the solutions of the smaller problems are used to solve the original problem. – Eran Mar 03 '16 at 12:51

score 2 · Answer 2 · answered Mar 03 '16 at 13:56

Well if you want to visualize it, usually it's kind of like a tree. You first follow one path through the tree until the end, then step one back and pick a different path (if possible). If there is none or you are happy with your result you just take another step back and so on.

I don't know if this helps you but when I learned recursion, it helped to just think of my method as already working. So I thought: Great, so basically my method is already working, but I can't call it with the same parameters and have to make sure I return the right value for these exact parameters by using different ones.

If we take that example: At first we know that if we have no numbers to look at left, then the answer depends on if the target is 0. (first line)

Now what do we do with the rest? Well... we'd need to think about it for a moment. Just think about the very first number. Under what circumstances is it part of the solution? Well that would be if you could create target-firstnumber with the rest of the numbers. Because then when you add firstnumber, you reach target. So you try to see if that's possible. If so, it's solvable. (second line)

But if not, it's still possible that the first number just isn't important for the solution. So you have to try again to build the target without that number. (third line)

And that's basically all there is to this.

Of course to think like this you need two things: 1. You need to believe that your method already works for other parameters 2. You need to make sure your recursion terminates. That's the first line in this example but you should always think about if there is any combination of parameters that will just create an endless recursion.

score 1 · Answer 3 · answered Mar 03 '16 at 12:28

1

Try to understand it like this: Recursion can be rewritten as a while-loop. where the condition of the while is the negation of the stop-condition of the recursion.

As already said, there is nothing called double recursion.

answered Mar 03 '16 at 12:28

adranale

2,835
1
21
39

Double Recursion in one method Java

3 Answers3