Error: variable not storing modified value on recursion-CodePudding

I am finding count of all the ways a target is reached. In base case, i am updating the value but when returning, it is taking the initial value only. How to change it to updated value, Kindly help me making changes in this code only and let me know how can i store so that it can return the modified value.

Input list:[1,2,3] target:3 Output: 2 as [1,2] and [3] will make it 3

def counter(ind,grid,target,count):
    if target==0:               #if target becomes 0(achieved)
        count =1
        return count
    if ind==0:                      #if ind=0 is reached and target=value at that index(achieved)
        if target==grid[ind]:
            count =1
            return count
        else:
            return

    nottake=counter(ind-1,grid,target,count)        #not taking the index's value
    take=0
    if target-grid[ind]>=0:                             #only if value at index is smaller that target
        take=counter(ind-1,grid,target-grid[ind],count)     #taking the index's value
    return count
grid=[1,2,3]
target=3
ind=len(grid)-1
print(counter(ind,grid,target,0))   #output should be 2 but i am getting 0

CodePudding user response：

The idea is to consider two cases: not taking the value at index ind, and taking the value at index ind. For each case, we recursively call the counter function with the updated values of ind, target, and count as appropriate. Finally, we return the sum of the two cases.

def counter(ind, grid, target, count):
    if target==0:               #if target becomes 0(achieved)
        count =1
        return count

    if ind==0:                      #if ind=0 is reached and target=value at that index(achieved)
        if target==grid[ind]:
            count =1
            return count
        else:
            return

    # not taking the index's value
    nottake = counter(ind-1, grid, target, count)

    # taking the index's value
    take = 0
    if target-grid[ind]>=0:                             
        take = counter(ind-1, grid, target-grid[ind], count)

    # return the sum of the two cases
    return nottake   take

Here is an example of how to use the function:

grid = [1, 2, 3]
target = 3
ind = len(grid)-1
print(counter(ind, grid, target, 0))   # should print 2

CodePudding user response：

For starters, please format your code with Black. It's difficult to understand code that's scrunched together. Also, use default values to avoid burdening the caller with fussy indices and extra parameters.

This approach exhibits a common mistake with recursion: trying to pass the result downward through the recursive calls as well as upward. Just pass the result upward only, and pass parameters/state downward.

Doing so gives:

from functools import cache

@cache
def count_ways(available_numbers, target, i=0):
    if target == 0:
        return 1
    elif target < 0:
        return 0
    elif i >= len(available_numbers):
        return 0

    take = count_ways(available_numbers, target - available_numbers[i], i   1)
    dont_take = count_ways(available_numbers, target, i   1)
    return take   dont_take


if __name__ == "__main__":
    print(count_ways(available_numbers=(1, 2, 2, 1, 3, 4) * 70, target=7))

This is clearly exponential since each recursive call spawns 2 child calls. But adding a cache (formerly lru_cache(maxsize=None) prior to CPython 3.9) avoids repeated calls, giving a linear time complexity as long as the list fits within the stack size. Use a bottom-up dynamic programming approach if it doesn't