CODEWITHSUNDEEP
javarecursion
user1229441
user1229441

Reputation: 354

tracing recursion

I am learning recursion and having hard time in tracing recursion. Here is my problem and I have the solution which is working perfectly fine. I am stuck at some point and not able to proceed with tracing.

problem: 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.

Solution:

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

start = 0 (where we have to start the array)

nums[]={10,8,6} target = 16

Please help me with tracing of the problem?

Upvotes: 2

Views: 405

Answers (2)

Jillian Hoenig
Jillian Hoenig

Reputation: 247

It might be helpful to think of the code as continually calling the function, until it reaches either the target (or false). The result of "innermost" call will return either true (or target == 0).

With that the condition below will or won't be met:

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

Upvotes: 0

Tudor
Tudor

Reputation: 62439

Start by numbering the lines

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

Here's the execution (assuming this is what you are asking for):

1 call groupSum1(0, {10, 8, 6}, 16)
    1. 0 < 3 next
2 call groupSum1(1, {10, 8, 6}, 6)
    1. 1 < 3 next
3 call groupSum1(2, {10, 8, 6}, -2)
    1. 2 < 3 next
4 call groupSum1(3, {10, 8, 6}, -8)
    1. 3 == 3 return false to call 3      
back to call 3 in line 2.
5 call groupSum1(3, {10, 8, 6}, -2)
    1. 3 == 3 return false to call 3
back to call 3 in line 3.
    return false to call 2
back to call 2 in line 2.
6 call groupSum1(2, {10, 8, 6}, 6)
    2 < 3 next
7 call groupSum1(3, {10, 8, 6}, 0)
    3 == 3 return true to call 6
back to call 6 in line 2.
    return true to call 2
back to call 2 in line 3.
    return true to call 1
back to call 1 in line 2.
    return true

The number in front of the recursive call is just an index I'm using to keep track of depth. I hope it's understandable.

Upvotes: 3

Related Questions