Recursive function does not return proper variable, returns None

Question

I am creating a program that accepts an array and reverses it, it must include a recursive function. I am having an issue where it is returning None instead of the reversed array. Running it through a debugger and creating stop points at the return and the call of the recursive function shows that it does indeed reverse the function properly, but fails to return the array, is there something I am missing or have done wrong for it to not return the array? Code:

def reverse(my_list, index = 0):
     if index == len(my_list)//2: #The program will return the list as soon as it reaches the middle entry
         return my_list
     elif index <len(my_list)/2:
        temp = my_list[index]
        my_list[index] = my_list[(len(my_list)-1)-index]
        my_list[(len(my_list)-1)-index] = temp
        reverse(my_list,index+1)

def main():
    myList = [0,1,2,3,4,5,6,7,8,9]
    print(str(myList))
    print(str(reverse(myList)))

if __name__ == '__main__':
    main()

You forgot that you had to `return reverse(my_list,index+1)`. Correct it and your code works perfectly. — Thierry Lathuille, Dec 08 '19 at 20:38
Also note that your original list ```my_list``` will also be reversed because of how lists work, so you could instead of returning the new list - ```print(new_list)```. — Joshua Nixon, Dec 08 '19 at 20:47

score -1 · Answer 1 · answered Dec 08 '19 at 21:14

This is actually a Data structure and algorithm lesson about stacks and recursion.

function calls are stored on the call stack. The call stack is a specific implementation of the stack data structure. It is a LIFO (Last in, first out) data structure, meaning that function calls placed on the top of the call stack are also the first to be popped off.a stack is like a deck of cards. It is more convenient to place and draw cards from the top of the stack of cards.

in other words you can think of it as a plate that every piece of data gets stacked over the other one . So when you call recursion every time the function is called the data is stored on the call stack on top of each other like layers So the last condition that ends the recursion and return the value is on the top stack but once the return method is called the stacks gets destroyed to free up memory

remember

The first stack that gets destroyed is the top one which has the data and it keeps going till the last stack which has no data to return so it returns None So in order to make the script save the data you have on the top stack you have to return that stack's value which it will pass the saved data from one stack to another till the break of recursion You need to return the recursive result:

return reverse(my_list,index+1)

otherwise the function simply ends after executing that statement, resulting in None being returned.

In Python, any function that ends without a return statement implicitly returns None.

Output:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]                                                                                                                              
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

score -2 · Answer 2 · answered Dec 08 '19 at 20:42

As Thierry Lathuille already said, you missed a return in line 8, so that you correct code should look like this:

def reverse(my_list, index=0):
    if index == len(my_list) // 2:  # The program will return the list as soon as it reaches the middle entry
        return my_list
    elif index < len(my_list) / 2:
        temp = my_list[index]
        my_list[index] = my_list[(len(my_list) - 1) - index]
        my_list[(len(my_list) - 1) - index] = temp
        return reverse(my_list, index + 1)


def main():
    myList = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    print(str(myList))
    print(str(reverse(myList)))


if __name__ == '__main__':
    main()

Recursive function does not return proper variable, returns None

2 Answers2