Python recursive function doesn't return

Question

I'm trying to sharpen my noob Python skills by trying a problem my son has in his college CS class. The goal is to create a function that uses recursion to process a list. The function must accept a list of arbitrary length and return a new list in which each element is the sum of itself and the elements to its right. So, if you input the list [5, 3, 2, 4], the function should return [14, 9, 6, 4].

I've written the following code in Python, and it works fine if I put a "print" command in the recursive function to show the final value, but it won't pass its return values. The end result is "None."

Why don't the variables return properly?

def RecursiveProcess(ListIn2, target): #Recursive function that adds to target value the value to its right
    if target > -1:  #stop function if index is below 0
        ListIn2[target] = ListIn2[target] + ListIn2[target+1]  #Add value to the right of target to the target value 
        ListIn2 = RecursiveProcess(ListIn2, target-1) #Call the function again with lower taget value to process the next value
    else:
        return ListIn2  #return the changed list

def ProcessList(ListIn):  #helper function to pass the list and the position of penultimate value
    return RecursiveProcess(ListIn, len(ListIn)-2) #return the changed list

print ProcessList([5, 10, 11, 6, 7, 1, 2, 4, 6, 7])  #initiate recursion and print result

idjaw · Accepted Answer · 2016-03-14T19:42:03.640

You need to actually return your RecursiveProcess. Look below at your modified code.

You aren't exactly doing anything recursively if all you do is call the function and store the value in ListIn2. You will keep overwriting your previous data. By returning, you will end up getting your recursive behaviour:

def RecursiveProcess(ListIn2, target): #Recursive function that adds to target value the value to its right
    if target > -1:  #stop function if index is below 0
        ListIn2[target] = ListIn2[target] + ListIn2[target+1]  #Add value to the right of target to the target value
        return RecursiveProcess(ListIn2, target-1) #Call the function again with lower taget value to process the next value
    else:
        return ListIn2  #return the changed list

l = [5, 10, 11, 6, 7, 1, 2, 4, 6, 7]
d = RecursiveProcess(l, len(l)-2)
print(d) # [59, 54, 44, 33, 27, 20, 19, 17, 13, 7]

score 2 · Answer 2 · answered Mar 14 '16 at 19:38

2

The problem is that you don't actually do a recursion (every call to the same function returns the result) but since lists are mutable you don't need to:

def ProcessList(ListIn):
    RecursiveProcess(ListIn, len(ListIn)-2) #this will change the list in place!
    return ListIn

that's all to get it working like expected. Because each element is updated in the "recursion" so there is no need to pass the pointer to the list around. And also the result is what is expected:

# [59, 54, 44, 33, 27, 20, 19, 17, 13, 7]

answered Mar 14 '16 at 19:38

MSeifert

145,886
38
333
352

Nice catch on that. +1 – idjaw Mar 14 '16 at 19:43
Thanks! I "feared" that Python would not require the recursion and have a more pythonic answer. :-) My son's class is in Java. Since I'm learning Python, I thought I'd give it a try in Python. – trinkner Mar 14 '16 at 20:07

score 1 · Answer 3 · answered Mar 14 '16 at 19:31

You aren't returning in your general case. Try:

def RecursiveProcess(ListIn2, target): 
    if target > -1:
        ListIn2[target] = ListIn2[target] + ListIn2[target+1]  
        ListIn2 = RecursiveProcess(ListIn2, target-1) 
        return ListIn2 #Actually need to return in the general case
    else:
        return ListIn2

Python recursive function doesn't return

3 Answers3

Linked

Related