CODEWITHSUNDEEP
pythonpython-3.xrecursion
pks
pks

Reputation: 125

Recursively reverse a list in place

For the below code, even though reverse(s) returns the reversed string, the string itself is not reversed.

s = ["h", "e", "l", "l", "o"]
def reverse(s):
    if len(s) == 0:
        return
    if len(s) == 1:
        return s;
    temp = s[0]
    s = reverse(s[1:])
    s.append(temp)
    return s

print(reverse(s))
print(s)

Output

['o', 'l', 'l', 'e', 'h'] #reverse(s)
['h', 'e', 'l', 'l', 'o'] #s

As per this, Python: How do I pass a string by reference?. I understand i need to set s= reverse(s) and then the list gets reversed and this works alright.

But why is s getting reversed for this one? 

s = ["h", "e", "l", "l", "o"]
def reverse(s, index):
    if index >= len(s) or len(s) == 0:
        return
    reverse(s, index + 1)
    s.insert((len(s) - 1 - index), s.pop())


reverse(s, 0)
print(s)

Output

['o', 'l', 'l', 'e', 'h']

While debugging I have found out that for the first piece of code when the handle comes back to the print statement, s becomes the original list, but for the second piece of code, s remains reversed. I am not sure what is happening here Any help is appreciated!

Upvotes: 2

Views: 129

Answers (1)

Jean-François Fabre
Jean-François Fabre

Reputation: 140148

The first method never changes the original s argument, as it slices it (using s[0] and s[1:]), thus making copies (and when you're calling s.append(temp), s is already a copy)

The second method keeps changing the original s argument (with s.pop() and s.insert())

If you want to avoid that the second method changes the original argument, create a wrapper method that creates a copy beforehand (which also avoids showing the auxiliary index argument)

def reverse(s):
    def internal_reverse(s, index):
        if index >= len(s) or len(s) == 0:
            return
        internal_reverse(s, index + 1)
        s.insert((len(s) - 1 - index), s.pop())

    s2 = s[:] # s[:] is a way to copy the input
    internal_reverse(s2, 0)  
    return s2

Upvotes: 3

Related Questions