recursive exchange

Question

''' Implement a recursive troca_recursive function she gets a list and two numbers (take and put) and returns the list, changing the number take by the put

The first test takes the "simple case": lists with 0 or 1 element After passing it, implement the recursion using the two ideas below

troca_recursiva([5, resto],5,3) = [3]+troca_recursiva(resto);
troca_recursiva([8, resto],5,7) = [8]+troca_recursiva(resto)



    def troca_recursiva(lista, tirar, colocar):

Testing

    def test_500_troca_caso_facil(self):

         self.assertEqual(troca_recursiva([],5,2), [])
         self.assertEqual(troca_recursiva([1],5,4), [1])
         self.assertEqual(troca_recursiva([5],5,4), [4])


    def test_501_troca_funciona(self):
         self.assertEqual(troca_recursiva([0,1,2,1,4],1,7), [0,7,2,7,4])
         self.assertEqual(troca_recursiva([0,1,2,1,4],4,9), [0,1,2,1,9])
         self.assertEqual(troca_recursiva([1,1],1,2), [2,2])
         self.assertEqual(troca_recursiva([1,1],2,7), [1,1])
         self.assertEqual(troca_recursiva([0,1,2,1,4],5,3), [0,1,2,1,4])
         self.assertEqual(troca_recursiva([0,1,2,1,4],0,0), [0,1,2,1,4])
         self.assertEqual(troca_recursiva([0,1,2,1,4],9,9), [0,1,2,1,4])


    def test_502_troca_recursivo(self):
        sys.setrecursionlimit(50)
        try:
            troca_recursiva([1]*100,1,2)
            self.fail('a sua função é recursiva?')
        except RecursionError:
            print('')
            print('correto, sua funcao é recursiva')
        finally:
            sys.setrecursionlimit(1000)

My code is not running these last two tests

Answer 1

To create your recursive function, add an auxiliary parameter to the function signature to store the traversed indexes.

def troca_recursiva(values, old, new, index = 0):

Within a block try check if the element in position index is equal to the old value. If equal, replace it with the new value.

At the end of the process, return a new call from the same function with the same values, with the exception of the parameter index which must have its incremental value.

try:
    if values[index] == old:
        values[index] = new

    return troca_recursiva(values, old, new, index + 1)
# ...

If an exception occurs within the try like IndexError, means that the program has already recursively traversed all elements of the list. So you can just return the list without any modification.

except IndexError:
    return values

See the full code below:

def troca_recursiva(values, old, new, index = 0):

    try:
        if values[index] == old: 
            values[index] = new
        return troca_recursiva(values, old, new, index + 1)

    except IndexError:
        return values


values = [1, 5, 7, 3, 1, 6, 1, 1, 5, 2, 3]    # Lista com os valores
old, new = 1, 0                               # Troca 1 por 0

# Resultado: [0, 5, 7, 3, 0, 6, 0, 0, 5, 2, 3]
print(troca_recursiva(values.copy(), old, new))

Answer 2

^{First, remember that using recursion nay is the best way to solve this problem. A simple loop by the list would solve. Anyway...}

---

One way to solve is to make the function receive the index, as you indicated another answer (I would only change it to check if the index is at the edge of the list, instead of letting the IndexError). But if you want to follow your idea and not use the index as a parameter, the solution would be:

• check whether the first item on the list should be exchanged (and exchange it, if applicable)
• concatenate the first element with the swap result in the rest of the list

That is to say:

def troca_recursiva(lista, tirar, colocar):
    if not lista or tirar == colocar: # se a lista é vazia ou elementos são iguais, retorna ela mesma
        return lista

    # verifica se deve trocar o primeiro elemento
    primeiro = lista[0]
    if primeiro == tirar:
        primeiro = colocar

    # retorna lista com o primeiro elemento, concatenada com a troca do restante
    return [primeiro] + troca_recursiva(lista[1:], tirar, colocar)

First I check if the list is empty (if not lista, since empty lists are considered False), and if it is, return the list itself, because there is no reason to continue. And I also included a small improvement, which is to check if the old and new values are equal (in this case, it also doesn’t make sense to have all the work of exchanging, just return to the list itself, without modification).

Then I check if the first element should be exchanged (and change, if applicable). Then just create a list with the first element, and concatenate with the result of changing the rest of the list: lista[1:] creates a sub-list containing the second element onwards (or an empty list if there are no more elements).

This method is extremely inefficient because it creates multiple sub-lists. Also, many recursive calls can cause a pile burst (even though you can change the recursion limit with sys.setrecursionlimit, is still inefficient because of the creation of sub-lists).

---

Attention to a detail. I could to have made the exchange of the first element like this:

if lista[0] == tirar:
    lista[0] = colocar

Only that would modify the original list. Let’s see the difference:

def troca_recursiva_nao_muda_lista(lista, tirar, colocar):
    if not lista or tirar == colocar:
        return lista

    primeiro = lista[0]
    if primeiro == tirar:
        primeiro = colocar

    return [primeiro] + troca_recursiva_nao_muda_lista(lista[1:], tirar, colocar)

def troca_recursiva_muda_lista(lista, tirar, colocar):
    if not lista or tirar == colocar:
        return lista

    if lista[0] == tirar:
        lista[0] = colocar

    return lista[:1] + troca_recursiva_muda_lista(lista[1:], tirar, colocar)

lista = [0, 1, 2, 0]
print(troca_recursiva_nao_muda_lista(lista, 0, 7)) # [7, 1, 2, 7]
print(lista) # [0, 1, 2, 0] <- lista original intacta
print(troca_recursiva_muda_lista(lista, 0, 7)) # [7, 1, 2, 7]
print(lista) # [7, 1, 2, 0] <- somente o primeiro foi mudado

Note that using the first version, the original list is not modified. Already using the second version, the list is modified, but only the first element. This is because from the second element we are dealing with sub-lists created internally, and that no longer affect the original list. Still, you have to check whether or not you want to change the original list (the other answer "solves" this by creating a copy of the list with the method copy, But let’s face it, it’s the function that should take care of that detail, not who’s calling it - and if whoever calls the function forgets to pass the copy? The function should make it clear whether or not it modifies the list, and as we have seen, it is not so difficult to guarantee this).

---

Just for the record, see how much easier it would be without recursion (and with the advantage of not creating multiple sub-lists, nor having the risk of popping the stack):

def troca_muda_lista(lista, tirar, colocar):
    for i, n in enumerate(lista):
        if n == tirar:
            lista[i] = colocar
    # não preciso retornar porque modifiquei a própria lista

def troca_nao_muda_lista(lista, tirar, colocar):
    # retorna outra lista com os elementos modificados
    return [ colocar if n == tirar else n for n in lista ]

lista = [0, 1, 2, 0]
print(troca_nao_muda_lista(lista, 0, 7)) # [7, 1, 2, 7]
print(lista) # [0, 1, 2, 0] <- lista original intacta
troca_muda_lista(lista, 0, 7)
print(lista) # [7, 1, 2, 7] <- a lista foi modificada

The function that modifies the list is not returning anything because it doesn’t make much sense, since it modifies the list itself (it would be redundant to return the list itself, since it has already been modified within the function).