tracing recursion

Question

Я изучаю рекурсию и затрудняюсь в поиске рекурсии. Вот моя проблема, и у меня есть решение, которое работает отлично. Я застрял в какой-то момент и не смог продолжить трассировку.

проблема: Учитывая массив из ints, можно ли выбрать группу некоторых из int, чтобы группа суммировалась с заданной целью.

Решение:

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; 
     } 

начало = 0 (где мы должны запустить массив)

НУМС [] = {10,8,6} мишень = 16

Пожалуйста, помогите мне с отслеживанием проблемы?

Answer 1

Начало нумерацией линий

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; 
    } 

Вот исполнение (при условии, это то, что вы просите):

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 

Число перед рекурсивным вызовом только индекс I Используется для отслеживания глубины. Надеюсь, это понятно.

Answer 2

Возможно, было бы полезно подумать о том, что код постоянно вызывает функцию, пока не достигнет цели (или false). Результат «самого внутреннего» вызова вернет либо true (или target == 0).

С, что ниже условие или не будет достигнута:

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