Ricorsione

La ricorsione sono funzioni che chiamano loro stesso. Ma perchè dovremmo fare mai una cosa del genere?

#supponiamo di dover sommare tutti i numeri di una lista
 
lista=[1,2,5,13,4]
 
#normalmente dovreste fare una cosa tipo
def somma_di_lista(lista)
	somma_totale=0
	for x in lista:
		somma_tutale+=x
	return somma_totale
 
#e cioè scorriamo la lista, ed ogni elemento di quella lista lo accumuliamo in una variabile chiamata somma_totale
 

Questa è un’ottima idea, ma non funziona sempre

lista=[1,2,3,[4,7,1],3,5]
 
print(somma_di_lista(lista)) #ERRORE
 

Mi da errore perchè quando trova la lista non può sommarla come farebbe con un normale numero. Quello che vorremmo dire alla funzione è tipo: qunado becchi un numero, bene, sommalo agli altri, ma quando becchi un’altra lista, entra dentro, trova la somma dei numeri in quella lista, e poi prosegui con gli altri numeri.

 
def deep_somma_di_lista(lista) #questa funzione prende una lista e mi da la somma dei suoi elementi
	somma_totale=0
	for elemento in lista:
		if type(elemento)==int:
			somma_totale+=elemento
		elif type(elemento)==list:
			#dammi la somma di quella lista
	return somma_totale
 

AH! se solo avessi una funzione che prende una lista in input e restituisce la somma dei suoi elementi… Ma io in realtà ce l’ho! La sto programmando ora!

def deep_somma_di_lista(lista) #questa funzione prende una lista e mi da la somma dei suoi elementi
	somma_totale=0
	for elemento in lista:
		if type(elemento)==int:
			somma_totale+=elemento
		elif type(elemento)==list:
			somma_totale+=deep_somma_lista(elemento)
			#voglio sommare alla somma totale, la somma degli elementi della lista interna
	return somma_totale

Questo può sembrare una mano che si disegna da sola (e per certi versi lo è) ma allo stesso tempo è una figata pazzesca, perché mi ha risolto in maniera molto elegante un problema che sarebbe stato non banale da risolvere.

una funzione ricorsiva per il massimo di una lista

lista=[1,3,6,2,4,1,87,9,1]
 
def massimo(lis):
	massimo=0
	for elemento in lis:
		if elemento > massimo : massimo = elemento
	return massimo
 
print(massimo(lista))

Tutto molto figo, ma, se la lista fosse una cosa del tipo:

lista=[1,2,10,[5,7,81],1,42,3]

Eh cazzi amari, se non usi la ricorsione.

lista=[1,2,10,[5,7,81],1,42,3]
 
def massimo_ricorsivo(lista):
	massimo=0
	for elemento in lista:
		if type(elemento)==int and elemento > massimo: massimo=elemento
		elif type(elemento)==list:
			if massimo_ricorsivo(elemento)>massimo: massimo= massimo_ricorsivo(elemento)
	return massimo
 
print(massimo_ricorsivo(lista))

ricorsione per l’ordinamento

AKA Merge sort