Funzioni e Ricorsione

Funzioni

Intuizione

Il primo step per capire un concetto complesso e' avere un'intuizione dell'idea che sta alla base:

Esempio

La Aggiungiamo2AlTuoNumero&Co e' una azienda che si occupa di aggiungere 2 ai valori forniti dai clienti!

Sintassi

Vediamo la sintassi python per definire una funzione:

def agg2(x):
        return x+2

La direttiva return serve per "restituire" il valore specificato a chi ha chiamato la funzione 4(il "cliente");

Definizioni

Alcuni termini con cui prendere confidenza:

Esempio

Vediamo un altro esempio di funzione, questa volta con:

2 parametri in input;

2 diversi valori di ritorno;

def f(x1, x2):
        if x1 != x2:
                print("Diversi!")
                return False
        else:
                print("Uguali!")
                return True

Come usare una funzione

Una funzione puo' essere chiamata (function call) rispettando la sua signature, o "identita'":

def f(x1, x2):
        if x1 != x2:
                print("Diversi!")
                return False
        else:
                print("Uguali!")
                return True

a = 2
b = 3
if (f(a,b)):
        print("Congratulazioni!")
else:
        print("Ahia!")

La signature di \(f\) ci ricorda che la funzione richiede 2 parametri, \(x1\) e \(x2\).

Se non rispettiamo questa regola, Python si arrabbia e ci da errore!

a = 2
b = 3
if (f(a)):
        print("Congratulazioni!")
else:
        print("Ahia!")

TypeError: f() missing 1 required positional argument: 'x2'

Esercizio

Scrivere una funzione che dato un numero intero \(n\), restituisca una lista contenente i divisori di \(n\). Ad esempio, dato \(n=16\), restituisca \([1,2,4,8,16]\).

Soluzione:

def divisori(x):
        l = []
        for i in range(1, x+1):
                if x % i == 0:
                        l.append(i)
        return l

print(divisori(16))

Ragioniamo

Quali potrebbero essere i problemi ("falle di sicurezza") di questo codice?

Type Checking (1/2)

def divisori(x):
        return [i for i in range(1,x+1) if x % i == 0] 

print(divisori("16"))

Type Checking (2/2)

Python e' un linguaggio a tipizzazione dinamica debole,

Le variabili possono riferirsi a valori in memoria di qualsiasi tipo;

Nella funzione divisori abbiamo dato per scontato che l'utente abbia inserito un valore intero;

Se diamo in input alla funzione un valore che non supporta l'operatore "%" come una stringa, viene sollevato un errore a runtime (a tempo di esecuzione);

Memoria

def retid(x):
        return id(x)

x = 3
print(id(x) == retid(x))

Cosa stampa?

True!

Ricordiamoci pero' che la \(x\) nel corpo del main e la \(x\) nella funzione sono due variabili diverse, anche se puntano allo stesso oggetto in memoria.

Facciamo un'altro piccolo test, cosa ci aspettiamo che stampi il seguente codice?

def retid(x):
        x = 2
        return id(x)

x = 3
print(id(x) == retid(x))
print(x)

False
3

Nella fuzione il puntatore all'oggetto 3 viene modificato e collegato all'oggetto 2. Il puntatore originale (la \(x\) del main) rimane inalterato!

def retid(x):
        l.append(5)
        return id(x)

l = [1,2,3,4]
print(retid(l) == id(l))
print(l)

Cosa viene stampato?

True
[1, 2, 3, 4, 5]

La \(x\) nella funzione punta allo stesso oggetto a cui si riferisce la \(l\)

Se modifichiamo l'oggetto in memoria (aggiungiamo un elemento alla lista) allora ci accorgiamo della modifica anche stampando \(l\)

Esercizio

Date due stringhe definiamo la loro distanza come il numero di caratteri da modificare per ottenere l'una dall'altra. Ad esempio, "abcde" e "xbcdx" hanno distanza 2.

Scrivere una funzione che ritorni la distanza tra due stringhe prese in input.

Soluzione

def distance(w1, w2):
        counter = 0
        for i in range(len(w1)):
                if w1[i] != w2[i]:
                        counter += 1
        return counter

Usando le list comprehension:

def distance(w1, w2):
        l = [1 if w1[i] != w2[i] else 0 for i in range(len(w1))]
        return sum(l)

Esercizio (1/2)

Scrivere una funzione che data una lista di valori come \(l = [2,2,6,2,3,7,1,3,3,12]\) ritorni il numero di volte in un'elemento in posizione \(i\) e' divisore degli elementi in posizione \(i-1\) e \(i+1\). Nel caso d'esempio dovrebbe ritornare 3.

Esercizio (2/2)

Soluzione

In questo caso basta sfruttare la funzione scritta nella parte 1!

Ricorsione

Intuizione

Le funzioni possono richiamare se stesse!

La ricorsione puo' essere uno scoglio duro con cui scontrarsi

In realta' c'e' un modo per capire meglio l'idea che sta alla base della ricorsione

Bisogna immaginarsi le funzioni come processi o procedure indipendenti, che semplicemente agiscono nel modo che specifichiamo noi nel codice;

La funzione non e' il codice!

Un esempio classico

La sequenza di fibonacci e' il mario rossi della ricorsione;

Ragioniamo

Qual'e' l'unica cosa che cambia da una chiamata di funzione all'altra?

L'input!

Il modo in cui le funzioni ragionano e' lo stesso, semplicemente sanno dare la risposta subito soltanto per degli input particolari (solo se \(n<2\));

Esercizio

Provare a scrivere in autonomia il codice che dato un intero \(n\) restituisce l'ennesimo valore della sequenza di fibonacci

Soluzione

def fib(n):
        if n < 2:
                return n
        else:
                return fib(n-1) + fib(n-2)

print(fib(7))

Esercizio

Scrivere una funzione ricorsiva che sia utile per calcolare la somma di una lista di valori interi. Ovviamente e' vietato usare la funzione sum o i cicli for / while.

Soluzione

def f(l):
        if len(l) == 1:
                return l[0]
        else:
                return l[0] + f(l[1:])

print(f([1,2,3,4,5]))

Esercizio

Scrivere una funzione che prenda in input una lista di interi e ritorni True se la lista e' palindroma, False altrimenti. Una lista e' palindroma se e' uguale alla sua inversa (leggendola al contrario rimane uguale).