Recursion reverse list without return value

Question

I hit the below issue when I write a recursive function to reverse a list in-place. I could change the input parameter.

def reverse_string(s):
    if len(s) <= 1:
        return
    else:
        s[0], s[-1] = s[-1], s[0]
        reverse_string(s[1:-1])


s = ['A','B','C','D','E','F']
reverse_string(s)
print(s)

The output is

['F', 'B', 'C', 'D', 'E', 'A']

It looks the changes I made in recursion are rolled back after the recursion call returns. I don't understand why. Can anybody help?

Answer 1

Slicing a list creates a new list, so modifying the sliced list has no effect on the original list. Instead, you can make the function accept an offset as a second parameter, so that swapping of the items according to the offset from either ends of the list are performed on the original list:

def reverse_string(s, offset=0):
    if len(s) > offset * 2:
        s[offset], s[-offset - 1] = s[-offset - 1], s[offset]
        reverse_string(s, offset + 1)

so that:

s = ['A', 'B', 'C', 'D', 'E', 'F']
reverse_string(s)
print(s)

outputs:

['F', 'E', 'D', 'C', 'B', 'A']

Answer 2

Since s[::-1] is a suggested answer for reversing, we need to explain reverse too because it's the fastest method to reverse a slice (in-place)

s = ['A','B','C','D','E','F']
s.reverse()
print(s)
# ['F', 'E', 'D', 'C', 'B', 'A']

Answer 3

Hopefully this is just for a recursion exercise, this is a rather inefficient implementation of python's built-in reversing a list by using negative increments

s = ['A','B','C','D','E','F']
print(s[::-1])

For your recursion, see blhsing's answer.

Answer 4

To understand how your current code is not working, here's a version using the same algorithm that does work. It just adds some extra steps so that you deal appropriately with the list you slice out of the main list on each call:

def reverse_string(s):
    if len(s) <= 1:
        return
    else:
        s[0], s[-1] = s[-1], s[0]
        slice = s[1:-1]       # slicing a list creates a new, independent list object
        reverse_string(slice) # this call modifies the new list in place, leaving s unchanged
        s[1:-1] = slice       # so we have to assign the modified slice back to s ourselves

Note that while this does work, it's horribly inefficient, since both the slicing and the slice assignment require copying large parts of the list on each recursive call. The other answers give more efficient solutions that involve always modifying the same list, just using specific indexes rather than always swapping s[0] and s[-1].

It's also worth noting that while this is how list objects behave when you slice them, other objects in Python can act differently. A slice from a numpy array is another array, but arrays are shallow "views" of the underlying data. Modifying a slice of an array in place often does modify the data in the array it came from too. That can be good or bad, depending on whether you expect it or not!