4

Estou tentando criar uma função recursiva que inverta a ordem de uma determinada lista. Como sou iniciante, acredito que esteja cometendo erros durante a construção da função.

    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]

Ao printar o size, percebi que ele não se altera durante a execução, retornando assim apenas o ultimo elemento da lista original, vide código acima. Realmente fiquei sem saída aqui.

2 Respostas 2

5

Só lembrando que recursão não é a melhor maneira de inverter uma lista, e ao longo da resposta entenderemos os motivos.


A ideia básica de recursão é você resolver um problema resolvendo instâncias menores do mesmo problema e combinando os resultados (exceto se for recursão em cauda, que não precisa combinar nada). No caso de inverter uma lista, o raciocínio seria:

  1. pegar o último elemento da lista e colocá-lo no início
  2. juntar isso com o inverso do restante da lista
    • para inverter o restante da lista, pegue do primeiro ao penúltimo elemento e volte ao primeiro passo

Existem alguns casos básicos nos quais não é preciso do passo 1 e nem do 2: quando a lista for vazia, por exemplo.

Traduzindo isso para código, fica assim:

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]

Primeiro eu testo se a lista é vazia, com if not lista - isso funciona porque uma lista vazia é considerada um valor falso. Então se a lista for vazia, eu retorno a própria lista, pois não há o que inverter.

Se a lista não for vazia, eu faço o passo 2 descrito acima. No caso, eu usei a sintaxe de slice para construir sub-listas:

  • lista[-1:] constrói outra lista contendo apenas o último elemento de lista
  • lista[:-1] constrói outra lista contendo do primeiro ao penúltimo elemento de lista

Sendo assim, eu pego o último elemento da lista e junto com o inverso do restante da lista.


Para exemplificar, suponha que eu chame inverter([1, 2]):

  • a lista [1, 2] não é vazia, não entra no if not lista
  • lista[-1:] retorna [2], e é concatenada com o resultado de inverter(lista[:-1])
    • como lista[:-1] retorna [1], é feita uma chamada recursiva para inverter([1])
    • a lista [1] não é vazia, não entra no if not lista
    • lista[-1:] retorna [1], e é concatenada com o resultado de inverter(lista[:-1])
      • como lista[:-1] retorna [], é feita outra chamada recursiva para inverter([])
      • a lista [] é vazia, retorna ela mesma
    • [1] é concatenada com uma lista vazia, o resultado é [1]
  • [2] é concatenada com [1], o resultado é [2, 1]

Repare que são criadas várias sub-listas, o que torna esse algoritmo bem ineficiente. Outro detalhe é que se a lista for muito grande, isso pode causar um estouro de pilha (e nem precisa ser uma lista tão grande assim).


Até dá para eliminar a última chamada recursiva, testando se a lista tem um elemento (pois neste caso não precisa inverter também, basta retornar a própria lista):

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

Mas ainda sim temos os problemas de criar várias sub-listas e poder ter estouro de pilha quando a lista é suficientemente grande.

Mas repare que em nenhum dos casos eu preciso passar o tamanho da lista como parâmetro da função. Ele não é necessário, e mesmo que fosse, você precisaria testar se ele está na faixa de valores correta para que não ocorra um IndexError.


Um detalhe do algoritmo acima é que ele retorna outra lista, contendo os elementos invertidos. Mas se quiser alterar os elementos da própria lista, basta fazer:

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]

A ideia é trocar o primeiro elemento de lugar com o último, depois o segundo com o penúltimo, e assim por diante, até chegar ao meio da lista (len(lista) / 2). Aqui não temos o problema de criar várias sub-listas, mas ainda há o problema do estouro de pilha.

Uma curiosidade deste algoritmo é que dá para escolher os índices a partir dos quais ocorrerá a inversão:

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]

Ou ainda:

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]

Se o segundo e terceiro parâmetros não forem passados, a função assume que a inversão será feita do primeiro elemento (índice 0) ao último (índice -1).


Enfim, apesar de ser possível, recursão não é a melhor solução para inverter uma lista. Para ver formas melhores, leia aqui.

1
  • obrigado pela ajuda. Após ler seu comentário e testar, consegui fazer o código funcionar. Obrigado.
    – zangs
    26/10/2019 às 16:27
2

Um primeiro problema do seu código é que o clone será sempre resetado a cada execução porque dentro da função existe a linha clone = []. Dessa forma, todos appends que você fez serão apagados. Para corrigir isto, eu criei uma função mais externa para inicializar uma única vez a lista clone.

Um outro problema é na condicional if size == 0. Lembre-se que no Python, os elementos começam a partir de 0. Então se você quiser criar uma condicional para parar ao chegar no último elemento, você deverá substituir 0 por -1.

Já no bloco else, você colocou a chamada da função inverter antes do clone.append. Você deveria fazer o contrário para que o elemento de maior index fosse acrescentado à lista clone e depois disso ser acrescentado o de menor index.

Veja esse código abaixo que eu fiz (Funciona):

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]
4
  • Agradeço Jean, realmente ajudou bastante e esclareceu algumas dúvidas!
    – zangs
    26/10/2019 às 14:20
  • @zangado Vc chegou a testar o código acima? Ele nem sequer funciona: ideone.com/Ibzwi2
    – hkotsubo
    26/10/2019 às 14:21
  • @hkotsubo o código de fato não funciona, o que me ajudou foram as pontuações e explicações que ele fez. Acredito que o código tenha sido uma ideia de como fazer.
    – zangs
    26/10/2019 às 16:24
  • Funciona sim pessoal e sim @hkotsubo, eu testei o código. O problema é que quando eu escrevi a resposta, eu troquei o nome da função diversas vezes para ficar bonito e esqueci de trocar o nome da função na chamada. Já corrigi o código na resposta. Peço perdão a todos, e se clicou em "Essa resposta não é útil" por causa do código, peço para que reavaliem a minha resposta. 26/10/2019 às 19:19

Você deve fazer log-in para responder a esta pergunta.

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