Recursão em Python

Na programação, existe um conceito chamado recursão - quando uma função chama a si mesma.

Exemplo . Recursão simples com contador

Vamos exibir números de 1 a 10 usando recursão:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # aqui a função chama a si mesma
		
	func()

Vamos discutir como este código funciona.

Temos uma variável global i e uma função func, dentro da qual o conteúdo da variável i é impresso no console, e então uma unidade é adicionada a ela.

Se nossa variável i for menor ou igual a 10, a função é chamada novamente. Como a variável i é global, a cada nova chamada da função ela terá o valor da variável i definido na chamada anterior.

Isso fará com que a função continue chamando a si mesma até que i seja maior que 10.

Observe que, no nosso caso, a função não pode ser executada sem if - se fizermos isso, obteremos uma chamada infinita de funções.

Exemplo . Recursão para exibir elementos de listas aninhadas

Recursões são mais frequentemente usadas para percorrer listas de vários níveis de aninhamento. Suponha que temos a seguinte lista:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Vamos criar uma função que a percorrerá. Ela deve primeiro definir uma condição para que o elemento, que é um primitivo, ou seja, simplesmente um número extraído da lista, seja impresso no console. E se o elemento for um objeto, por exemplo, uma lista aninhada, então neste caso a função deve chamar a si mesma, ou seja, ocorrerá uma recursão. Para verificar o tipo do elemento, usaremos a função isinstance. Mas para o nosso exemplo, no primeiro parâmetro de isinstance escreveremos el, e no segundo - o tipo list:

def func(lst):
	for el in lst:
		if isinstance(el, list):
			func(el)
		else:
			print(el)

Ao chamar a função, uma sequência de todos os números da lista aninhada será exibida:

func(lst) # exibirá 1, 2, ... 8, 9

Exemplo . Recursão para operações com elementos de listas aninhadas

Recursões também podem ser usadas para várias operações com elementos de listas aninhadas. Suponha que temos a seguinte lista:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Vamos obter a soma de todos os seus elementos. Para isso, na função, declararemos uma variável res, na qual a soma dos números será acumulada. Na condição, escreveremos que se o elemento for um objeto complexo, então ele será passado como parâmetro para a função func e adicionado à soma. Isso significa que o elemento ficará em recursão até se tornar um primitivo. E neste caso, ele será simplesmente adicionado à soma armazenada em res:

def func(lst):
	res = 0
	for el in lst:
		if isinstance(el, list):
			res += func(el)
		else:
			res += el
	return res

Vamos chamar a função e exibir seu resultado no console:

print(func(lst)) # exibirá 45

Exemplo . Recursão para acumulação em uma lista

Com recursão, podemos descompactar listas aninhadas em uma única lista unidimensional. Suponha que tenhamos a seguinte lista:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Vamos definir na função uma lista vazia res, na qual os elementos da lista original serão acumulados. Em seguida, iniciaremos um loop e definiremos uma condição - se o elemento for uma lista, então ele será passado para o método extend. Este método anexa elementos de uma lista ao final de uma segunda lista, ou seja, os elementos da lista aninhada serão colocados no final da lista res:

def func(lst):
	res = []
	for el in lst:
		if isinstance(el, list):
			res.extend(func(el))
		else:
			res.append(el)
	return res
	
print(func(lst))

O resultado do código executado:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Problemas práticos

Exiba todos os elementos numéricos de um dicionário com nível arbitrário de aninhamento:

{
	'a': {
		'b': 1,
		'c': 2,
		'd': {
			'e': 3,
			'f': 4
		}
	},
	'j': {
		'h': 5,
		'k': 6,
	},
	'l': 7
}

Encontre a soma dos elementos do dicionário do problema anterior.

Obtenha uma lista dos elementos primitivos do dicionário do problema anterior.