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:
- pegar o último elemento da lista e colocá-lo no início
- 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.