-3

''' Implemente uma função recursiva troca_recursiva ela recebe uma lista e dois numeros (tirar e colocar) e retorna a lista, trocando o numero tirar pelo colocar

O primeiro teste pega o "caso simples": listas com 0 ou 1 elemento Depois de passar ele, implemente a recursao usando as duas ideias abaixo

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):

Testes

    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)

Meu código não ta rodando esses dois ultimos testes

2 Respostas 2

2

Para criar a sua função recursiva, adicione na assinatura da função um parâmetro auxiliar para guardar os índices percorridos.

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

Dentro de um bloco try verifique se o elemento na posição index é igual ao valor antigo. Se for igual, substitua ele pelo valor novo.

No final do processo, retorne uma nova chamada da mesma função com os mesmos valores, com exceção do parâmetro index que deve ter seu valor incrementado.

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

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

Caso ocorra uma exceção dentro do try que seja do tipo IndexError, significa que o programa já terá percorrido recursivamente todos os elementos da lista. Sendo assim, você pode apenas retornar a lista sem modificação alguma.

except IndexError:
    return values

Veja o código completo abaixo:

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))
8
  • Isso não é recursão. Recursão é iterar individualmente por cada elemento da lista seguindo um critério. Quando você faz if not old in values: e index = values.index(old) você a cada iteração da função você reitera duas vezes pela entrada aumentando a complexidade do algorítimo. Está bem errado. Commented 12/05/2020 às 1:37
  • Você está certo, eu não tinha pensado nisto. Corrigi a resposta, você pode dar uma olhada ? Commented 12/05/2020 às 1:53
  • 1
    ISSOOOO!!! Está certinho. Commented 12/05/2020 às 1:56
  • Ei Augusto se estiver com tempo, você pode ir lá no chat e tentar me ajudar com um problema de incompatibilidade entre alguns programas que eu uso e o .NET Framework 4.8 ? Commented 12/05/2020 às 1:57
  • Depois, agora estou assistindo Black Cover. Dá para explorar esse índice de forma que não precise tratar exceção para sair da recursão. Commented 12/05/2020 às 2:00
1

Primeiramente, vale lembrar que usar recursão não é o melhor jeito de resolver esse problema. Um loop simples pela lista resolveria. Enfim...


Uma forma de resolver é fazer a função receber o índice, como indicou a outra resposta (eu só a mudaria para verificar se o índice está nos limites da lista, em vez de deixar estourar o IndexError). Mas se quiser seguir a sua ideia e não usar o índice como parâmetro, a solução seria:

  • verificar se o primeiro elemento da lista deve ser trocado (e trocá-lo, se for o caso)
  • concatenar o primeiro elemento com o resultado de trocar no restante da lista

Ou seja:

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)

Primeiro eu verifico se a lista é vazia (if not lista, já que listas vazias são consideradas False), e se for, retorna a própria lista, pois aí não há motivo para continuar. E também incluí uma pequena melhoria, que é verificar se os valores antigo e novo são iguais (nesse caso, também não faz sentido ter todo o trabalho de trocar, basta retornar a própria lista, sem modificação).

Depois eu verifico se o primeiro elemento deve ser trocado (e troco, se for o caso). Aí basta criar uma lista com o primeiro elemento, e concatenar com o resultado da troca do restante da lista: lista[1:] cria uma sub-lista contendo do segundo elemento em diante (ou uma lista vazia, caso não hajam mais elementos).

Esse método é extremamente ineficiente porque cria várias sub-listas. Além disso, muitas chamadas recursivas podem causar um estouro de pilha (mesmo com você podendo mudar o limite de recursão com sys.setrecursionlimit, ainda sim é ineficiente por causa da criação das sub-listas).


Atenção para um detalhe. Eu poderia ter feito a troca do primeiro elemento assim:

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

Só que isso modificaria a lista original. Vamos ver a diferença:

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

Repare que usando a primeira versão, a lista original não é modificada. Já usando a segunda versão, a lista é modificada, mas apenas o primeiro elemento. Isso porque a partir do segundo elemento estamos lidando com as sub-listas criadas internamente, e que não afetam mais a lista original. Ainda sim, você tem que verificar se quer ou não alterar a lista original (a outra resposta "resolve" isso criando uma cópia da lista com o método copy, mas convenhamos que é a função que deveria cuidar desse detalhe, e não quem a está chamando - e se quem chamar a função esquece de passar a cópia? A função deve deixar claro se ela modifica ou não a lista, e como vimos, não é tão difícil assim garantir isso).


Só para constar, veja como seria muito mais fácil sem recursão (e com a vantagem de não ficar criando várias sub-listas, nem ter o risco de estourar a pilha):

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

A função que modifica a lista não está retornando nada porque não faz muito sentido, já que ela modifica a própria lista (seria redundante retornar a própria lista, sendo que ela já foi modificada dentro da função).

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .