Recursion to Python List Inversion

Question

I’m trying to create a recursive function that reverses the order of a certain list. As a beginner, I believe I’m making mistakes during the construction of the function.

    def inverter(lista, size):
        clone = []
        if size == 0:
            clone = lista
            return clone
        else:
            inverter(lista, size-1)
            clone.append(lista[size])
            return clone

l = [1,2,3,4,5]
s = len(l) - 1
#[5]

When printing the size, I realized that it does not change during the execution, thus returning only the last element of the original list, see code above. I really got stuck here.

Answer 1

^{Just remembering that recursion is not the best way to invert a list, and throughout the answer we will understand the reasons.}

---

The basic idea of recursion is you solve a problem by solving smaller instances of the same problem and combining the results (except if it is tail recursion, that does not need to combine anything). In case of reversing a list, the reasoning would be:

1. take the last element from the list and put it at the beginning
2. join this with the inverse of the rest of the list
   • to invert the rest of the list, take the first to the penultimate element and return to the first step

There are some basic cases where you don’t need step 1 or step 2: when the list is empty, for example.

Translating that into code, it goes like this:

def inverter(lista):
    if not lista: # lista vazia, retorna ela mesma
        return lista
    return lista[-1:] + inverter(lista[:-1])

lista = inverter([1, 2, 3, 4, 5])
print(lista) # [5, 4, 3, 2, 1]

First I test if the list is empty, with if not lista - that works because an empty list is considered a false value. So if the list is empty, I return to the list itself, because there is nothing to invert.

If the list is not empty, I do step 2 described above. In this case, I used the syntax of Slice to build sub-lists:

• lista[-1:] builds another list containing only the last element of lista
• lista[:-1] builds another list containing from the first to the penultimate element of lista

So I take the last element of the list and along with the inverse of the rest of the list.

---

For example, suppose I call inverter([1, 2]):

• the list [1, 2] is not empty, does not enter the if not lista
• lista[-1:] returns [2], and is concatenated with the result of inverter(lista[:-1])
  • as lista[:-1] returns [1], a recursive call is made to inverter([1])
  • the list [1] is not empty, does not enter the if not lista
  • lista[-1:] returns [1], and is concatenated with the result of inverter(lista[:-1])
    • as lista[:-1] returns [], another recursive call is made to inverter([])
    • the list [] is empty, returns itself
  • [1] is concatenated with an empty list, the result is [1]
• [2] is concatenated with [1], the result is [2, 1]

Note that several sub-lists are created, which makes this algorithm very inefficient. Another detail is that if the list is too large, this can cause a pile overflow (and it doesn’t even have to be such a long list).

---

You can even delete the last recursive call by testing if the list has an element (because in this case you don’t need to invert either, just return the list itself):

def inverter(lista):
    if len(lista) <= 1: # lista vazia ou com um elemento, retorna ela mesma
        return lista
    return lista[-1:] + inverter(lista[:-1])

But we still have the problems of creating several sub-lists and can have battery burst when the list is large enough.

But note that in none of the cases do I need to pass the list size as a function parameter. It is not necessary, and even if it were, you would need to test if it is in the correct range of values so that there is no IndexError.

---

One detail of the above algorithm is that it returns another list, containing the inverted elements. But if you want to change the elements of the list itself, just do:

def inverter(lista, first=0, last=-1):
    if first >= len(lista) / 2:
        return
    lista[first], lista[last] = lista[last], lista[first]
    inverter(lista, first + 1, last - 1)

lista = [1, 2, 3, 4, 5]
inverter(lista)
print(lista) # [5, 4, 3, 2, 1]

The idea is to swap the first element of place with the last, then the second with the penultimate, and so on, until you get to the middle of the list (len(lista) / 2). Here we do not have the problem of creating several sub-lists, but there is still the stack overflow problem.

A curiosity of this algorithm is that you can choose the indexes from which the inversion will occur:

lista = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
inverter(lista, 2, -3)
print(lista) # [1, 2, 8, 7, 6, 5, 4, 3, 9, 10]

Or else:

lista = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
inverter(lista, 2)
print(lista) # 1, 2, 10, 9, 8, 6, 7, 5, 4, 3]

If the second and third parameters are not passed, the function assumes that the inversion will be made of the first element (index 0) last (index -1).

---

Anyway, although it is possible, recursion is not the best solution to invert a list. To see better ways, read here.

Answer 2

A first problem with your code is that the clone will always be reset at each execution because within the function there is the line clone = []. That way, all appends you made will be deleted. To fix this, I created a more external function to initialize the list once clone.

Another problem is on parole if size == 0. Remember that in Python, elements start from 0. So if you want to create a condition to stop when arriving at the last element, you must replace 0 with -1.

Already in the Else block, you placed the function call inverter before the clone.append. You should do the opposite so that the highest index element is added to the list clone and after that the lowest index shall be added.

See this code below that I made (Works):

def inverter(lista):
    clone = []

    def adiciona(lista, index):

        # Enquanto não chegar no último elemento, o index receberá o 
        # valor dele -1 e o elemento do index atual será adicionado à lista clone.

        if index > -1:
            clone.append(lista[index])
            adiciona(lista, index-1)

    # Adiciona à lista clone os elementos da lista original só que invertido.        
    adiciona(lista,len(lista)-1)
    return clone

lista = [1,2,3,4,5]
lista = inverter(lista)

print(lista) # A saída é [5,4,3,2,1]