Python recursion function parameters issue-CodePudding

I'm calling a function inside itself many times to solve the subset sum problem, using as it called, the recursion solution; anyway, I can't figure out why n (which is the number of elements of the array) value is getting decreasing at first, until it reach 0, which is I get it, but then, after calling it again within itself, it makes n value incremented. Why is that happening, as the whole function doesn't even have an increment contribution for the n value? Where n gets its increasing value from?

Here is the code:

def printAllSubsetsRec(arr, n, currentSubset, sum):
    # If remaining sum is 0, then print all
    # elements of current subset.

    if (sum == 0):
        i = 0
        sumOfValue = 0
        for value in currentSubset:
            i  = 1
            sumOfValue  = value
            if (i == len(currentSubset)):
                print(value, " = ", sumOfValue)
            else:
                print(value, end="   ")
        return True

    # If there are no elements in the array and the sum is not equal to 0.
    if (n == 0 and sum != 0):
        return None


    # I consider two cases for every element:
    # a) Excluding last element.
    # b) Including last element in current subset.
    # -------------------------------------------------

    # Excluding the last element:
    printAllSubsetsRec(arr, n - 1, currentSubset, sum)

    v = []   currentSubset
    v.append(arr[n - 1])

    # Including the last element:
    printAllSubsetsRec(arr, n - 1, v, sum - arr[n - 1])


#Main:
arr = [10, 7, 5, 18, 12, 20, 15]
sum = 35
n = len(arr)
currentSubset = []
printAllSubsetsRec(arr, n, currentSubset, sum)

The output should be:

18 7 10 = 35

12 18 5 = 35

20 5 10 = 35

15 20 = 35

Thanks in advance!

CodePudding user response：

Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutation, variable reassignment, and other side effects -

logical if without a corresponding else
mutation and reassignment of i and sumOfValue
side effects like print

Recursion doesn't have to be difficult or painful. Using functional disciplines we can write subsets(t,n) with inductive reasoning -

If the target sum n is zero, yield the empty solution
(inductive) otherwise n is negative or positive. If n is negative or the input array t is empty, we are out-of-bounds. stop iteration.
(inductive) n is positive and t has at least one element. For all s of the subproblem (t[1:],n-t[0]), prepend t[0] to s and yield. And yield all results of the subproblem (t[1:],n)

def subsets(t, n):
  if n == 0:
    yield ()                              #1
  elif n < 0 or not t:
    return                                #2
  else:
    for s in subsets(t[1:], n - t[0]):    #3
      yield (t[0], *s)
    yield from subsets(t[1:], n)

for s in subsets([10, 7, 5, 18, 12, 20, 15], 35):
  print(s)

(10, 7, 18)
(10, 5, 20)
(5, 18, 12)
(20, 15)

Notice -

All operations do not mutate or reassign variables
Side effects like print are traded for yield
Caller is free to utilize and transform the results any way desired

To format the results as an mathematical expression -

for s in subsets([10, 7, 5, 18, 12, 20, 15], 35):
  print("   ".join(map(str, s)), "=", 35)

10   7   18 = 35
10   5   20 = 35
5   18   12 = 35
20   15 = 35

To collect all outputs of a generator into a list, use list -

print(list(subsets([10, 7, 5, 18, 12, 20, 15], 35)))

[(10, 7, 18), (10, 5, 20), (5, 18, 12), (20, 15)]