Ricorsione in Python

Nella programmazione esiste un concetto chiamato ricorsione - quando una funzione chiama se stessa.

Esempio . Ricorsione semplice con contatore

Visualizziamo i numeri da 1 a 10 utilizzando la ricorsione:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # qui la funzione chiama se stessa
		
	func()

Discutiamo come funziona questo codice.

Abbiamo una variabile globale i e una funzione func, all'interno della quale il contenuto della variabile i viene stampato in console, e poi ad essa viene aggiunto uno.

Se la nostra variabile i è minore o uguale a 10, la funzione viene chiamata nuovamente. Poiché la variabile i è globale, ad ogni nuova chiamata della funzione in essa sarà presente il valore della variabile i impostato durante la chiamata precedente.

Risulterà che la funzione chiamerà se stessa finché i non diventerà maggiore di 10.

Si noti che in questo caso non è possibile avviare la funzione senza if - se si fa così, si otterrà una chiamata infinita di funzioni.

Esempio . Ricorsione per visualizzare elementi di liste annidate

Le ricorsioni sono più spesso utilizzate per l'iterazione di liste con diversi livelli di annidamento. Supponiamo di avere la seguente lista:

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

Creiamo una funzione che la iteri. In essa, per prima cosa, dobbiamo impostare una condizione in modo che un elemento che è un primitivo, cioè un numero semplicemente estratto dalla lista, venga stampato in console. E se l'elemento è un oggetto complesso, ad esempio una lista annidata, allora in questo caso la funzione deve chiamare se stessa, cioè avverrà una ricorsione. Per verificare il tipo di elemento utilizziamo la funzione isinstance. Solo per il nostro esempio nel primo parametro di isinstance scriveremo el, e come secondo - il tipo list:

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

Quando si chiama la funzione, verrà stampata una serie di tutti i numeri della lista annidata:

func(lst) # stamperà 1, 2, ... 8, 9

Esempio . Ricorsione per operazioni con elementi di liste annidate

Le ricorsioni possono essere utilizzate anche per varie operazioni con elementi di liste annidate. Supponiamo di avere la seguente lista:

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

Calcoliamo la somma di tutti i suoi elementi. Per fare ciò, nella funzione dichiariamo una variabile res, in cui verrà accumulata la somma dei numeri. Nella condizione specificheremo che se l'elemento è un oggetto complesso, allora viene passato come parametro alla funzione func e aggiunto alla somma. Ciò significa che l'elemento entrerà in ricorsione finché non diventerà un primitivo. E in questo caso verrà semplicemente aggiunto alla somma memorizzata in res:

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

Chiamiamo la funzione e stampiamo il suo risultato in console:

print(func(lst)) # stamperà 45

Esempio . Ricorsione per accumulo in una lista

Con la ricorsione è possibile espandere le liste annidate in una singola lista unidimensionale. Supponiamo di avere la seguente lista:

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

Scriviamo nella funzione una lista vuota res, in cui verranno accumulati gli elementi della lista originale. Successivamente avviamo un ciclo e impostiamo una condizione - se l'elemento è una lista, allora verrà passato al metodo extend. Questo metodo aggiunge gli elementi di una lista alla fine di una seconda lista, cioè gli elementi della lista annidata andranno alla fine della 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))

Risultato del codice eseguito:

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

Compiti pratici

Visualizza tutti gli elementi numerici di un dizionario con un livello arbitrario di annidamento:

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

Trova la somma degli elementi del dizionario del problema precedente.

Ottieni una lista degli elementi primitivi del dizionario del problema precedente.