Récursivité en Python

En programmation, il existe un concept appelé récursivité - lorsqu'une fonction s'appelle elle-même.

Exemple . Récursivité simple avec compteur

Affichez les nombres de 1 à 10 en utilisant la récursivité :

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # ici la fonction s'appelle elle-même
		
	func()

Discutons du fonctionnement de ce code.

Nous avons une variable globale i et une fonction func, à l'intérieur de laquelle le contenu de la variable i est affiché dans la console, puis on lui ajoute un.

Si notre variable i est inférieure ou égale à 10, alors la fonction est appelée à nouveau. Puisque la variable i est globale, à chaque nouvel appel de la fonction, elle contiendra la valeur de la variable i définie lors de l'appel précédent.

Il en résultera que la fonction s'appellera elle-même jusqu'à ce que i devienne supérieur à 10.

Notez que dans notre cas, la fonction ne peut pas être lancée sans if - si cela est fait, on obtiendra un appel infini de fonctions.

Exemple . Récursivité pour afficher les éléments de listes imbriquées

Les récursivités sont le plus souvent utilisées pour parcourir des listes de différents niveaux d'imbrication. Supposons que nous ayons la liste suivante :

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

Créez une fonction qui la parcourra. Dans celle-ci, il faut d'abord définir une condition pour que l'élément qui est un primitif, c'est-à-dire un nombre simplement extrait de la liste, soit affiché dans la console. Et si l'élément est un objet complexe, par exemple une liste imbriquée, alors dans ce cas, la fonction doit s'appeler elle-même, c'est-à-dire qu'une récursivité se produira. Pour vérifier le type de l'élément, utilisons la fonction isinstance. Seulement pour notre exemple, dans le premier paramètre de isinstance, nous écrirons el, et le second - le type list :

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

Lors de l'appel de la fonction, une série de tous les nombres de la liste imbriquée sera affichée :

func(lst) # affichera 1, 2, ... 8, 9

Exemple . Récursivité pour les opérations sur les éléments de listes imbriquées

La récursivité peut également être utilisée pour diverses opérations sur les éléments de listes imbriquées. Supposons que nous ayons la liste suivante :

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

Obtenons la somme de tous ses éléments. Pour cela, déclarons dans la fonction une variable res, dans laquelle la somme des nombres s'accumulera. Dans la condition, écrivons que si l'élément est un objet complexe, alors il est passé en paramètre à la fonction func et est ajouté à la somme. Cela signifie que l'élément sera traité récursivement jusqu'à ce qu'il devienne un primitif. Et dans ce cas, il sera simplement ajouté à la somme enregistrée dans res :

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

Appelons la fonction et affichons son résultat dans la console :

print(func(lst)) # affichera 45

Exemple . Récursivité pour accumulation dans une liste

Avec la récursivité, on peut transformer des listes imbriquées en une seule liste unidimensionnelle. Supposons que nous ayons la liste suivante :

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

Écrivons dans la fonction une liste vide res, dans laquelle les éléments de la liste originale s'accumuleront. Ensuite, lançons une boucle et définissons une condition - si l'élément est une liste, alors il est passé à la méthode extend. Cette méthode ajoute les éléments d'une liste à la fin d'une seconde liste, c'est-à-dire que les éléments de la liste imbriquée iront à la fin de la liste 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))

Résultat du code exécuté :

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

Tâches pratiques

Affichez tous les éléments numériques d'un dictionnaire avec un niveau d'imbrication arbitraire :

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

Trouvez la somme des éléments du dictionnaire de la tâche précédente.

Obtenez une liste des éléments primitifs du dictionnaire de la tâche précédente.