How to properly format recursion base case to limit infinite iterations?-CodePudding

RecursionError: maximum recursion depth exceeded while calling a Python object

I am trying to add any odd numbers to 'res' and multiply any even number to 'res' while going through a list using recursion.

Input is:

calc_res([3, 2, 2, 4, 15], 2))

Output should be: 95

Assume the first element is always odd, and ignore the element if it is 0.

My code as of now is:

def calc_res(some_list, res):
    i = 0
    if some_list[i] >= len(some_list):
        return
    if some_list[i] % 2 != 0:
        result = i   res
        return result   calc_res(some_list, res)
    if some_list[i] % 2 == 0:
        result = i * res
        return result   calc_res(some_list, res)

print(calc_res([3, 2, 2, 4, 15], 2))

CodePudding user response：

You need to pass your intermediate result as parameter to next recursion call.

And when no elements exists, you can just return res you passed in.

def calc_res(some_list, res):
    if len(some_list) == 0:
        # no remaining elements, just return the result.
        return res

    current_number = some_list[0]
    if current_number % 2 != 0:
        # this means that calc_res from the remaining of some list.
        # and current number's result is added to res, pass to next call.
        return calc_res(some_list[1:], res   current_number)
    else:
        if current_number == 0:
            return calc_res(some_list[1:], res)
        else:
            return calc_res(some_list[1:], res * current_number)

CodePudding user response：

Something like this may work better:

def calc_res(some_list, res, i=0):
    if i == len(some_list):
        return res
    if some_list[i] % 2 != 0:
        result = some_list[i]   res
    else:
        result = some_list[i] * res
    return calc_res(some_list, result, i   1)

print(calc_res([3, 2, 2, 4, 15], 2))

Here, we add a third argument to calc_res() which is the index i in some_list to process in a given call. If i has reached the end of some_list, we return res. Otherwise, we either add or multiply the i'th element of some_list and recursively call calc_res() with the updated result and an incremented value of i.

Other solutions are possible, such as avoiding i and instead passing smaller slices of some_list down the recursion stack, but an approach without slices uses less space.