Using Python, I want to print only positive integers on the list through recursion-CodePudding

I'm studying recursion now, and my head is about to explode trying to use it.

If lst = [-1, -4, 0, 3, 6], my expecting output is result = [3, 6].

I tried this,

def positive(lst):
    result = []
    if not lst:
        return result
    else:
        if lst[0] > 0:
            result.append(lst[0])
        return positive(lst[1:])

But output is empty list. like result = [ ].

CodePudding user response：

In your recursive part, positve() always return a further call to itself. Therefore, you always get the result of the final call to positive(), i.e., an empty list.

A solution that does not change your interface is as below, but at the cost of moving list every time.

def positive(lst):
    result = []
    if lst:
        if lst[0] > 0:
            result.append(lst[0])
        result.extend(positive(lst[1:]))
    return result

lst = [-1, -4, 0, 3, 6]
print(positive(lst))
# [3, 6]

Edit: Because we add at most one value each time, we can use insert instead of extend to update result with lower cost.

def positive2(lst):
    if not lst:
        return []
    result = positive2(lst[1:])
    if lst[0] > 0:
            result.insert(0, lst[0])
    return result

CodePudding user response：

You are not passing your cache down through recursion

def positive(lst, result):
    if not lst:
        return result
    else:
        if lst[0] > 0:
            result.append(lst[0])
        return positive(lst[1:], result)


lst_in = [-1, -4, 0, 3, 6]
result = []
res = positive(lst_in, result)
print(res)

In your version, result's scope was limited to a single function execution. You need to have a common cache(in your case result list). You can do that by passing it down to each function, or defining it in global scope