Parte 2

Introduzione al linguaggio Python

Introduzione a Python ed istruzioni elementari

Caratteristiche di Python

● Il Python è un linguaggio ideato da Guido Von Rossum nel 1989

● E' usato come linguaggio di scripting● E' imperativo, ad oggetti e anche un po'

funzionale● E' interpretato● E' usato in un ambiente interattivo, quindi è

possibile dare dei comandi in modo immediato● Caratteristica (quasi) unica: l'indentazione è

obbligatoria

Uso interattivo di Python

● Si possono digitare direttamente espressioni o istruzioni: sono valutate/eseguite direttamente

● >>> 2+2● 4● >>> 3+4*5-1● 22● >>> (7+2)*9● 81

Operatori

● operatori matematici + - * / % (resto della divisione) ** (elevamento a potenza)

● Nota che / calcola● il quoziente della divisione se entrambi gli operandi

sono numeri interi: 7/2 fa 3● la divisione senza resto se almeno un operando è

un numero reale: 7.0/2 fa 3.5

Funzioni matematiche

● Dopo aver dato il comando import math si possono usare● math.sqrt radice quadrata● math.log logaritmo naturale● math.exp funzione esponenziale● math.sin seno● math.cos coseno● ...

Assegnamento

● Per assegnare un valore ad una variabile V la sintassi èV=E

● ove E è l'espressione che indica il valore da assegnare a V

● Dopo l'esecuzione di V=E, V assume il valore che in quel momento ha E

● Se in seguito E cambia valore, V non cambia

Esempi

● >>> a=1

● >>> a

● 1

● >>> b=3

● >>> b

● 3

● >>> a=b+1

● >>> a

● 4

● >>> b=7

● >>> a

● 4

Casi particolari

● E' lecito che V stessa compaia in E● Ad esempio a=a+1 incrementa il valore di a di 1

● >>> a=8● >>> a● 8● >>> a=a+1● >>> a● 9

Vita delle variabili

● In Python una variabile inizia a esistere quando le viene assegnato un valore per la prima volta

● Le variabili cosiddette globali (quelle definite da linea di comando) durano per sempre, a meno che siano cancellate con il comando del

● Le variabili possono assumere valori anche di tipi diversi● a=1

poi● a='ciao'

Istruzione print

● Scrive uno o più dati sullo schermo

print 1+1

print a*b

print 'Ciao, mondo !'

print a+1,' ',b

print 4,● con la virgola in fondo non va a capo

Funzione input

● La funzione input serve a leggere dei dati da tastiera

>>> a=input('inserisci un numero ')

inserisci un numero 7

>>> a

7● input funziona solo per numeri, per leggere

stringhe usare raw_input

digitato dall'utente

Definizione di funzione (senza parametri)

E' possibile definire una funzione con il comando def

def area_rettangolo():base=input(“inserisci la base “)altezza=input(“inserisci l'altezza “)area=base*altezzaprint “L'area e' “,area

Chiamata di funzione

E' possibile richiamare la funzione

>>> area_rettangolo()inserisci la base 5inserisci l'altezza 4L'area e' 20

digitati dall'utente

Definizione di funzioni con parametri

E' possibile definire una funzione con uno o più parametri

def ipotenusa(cateto1,cateto2):somma_quadr=cateto1**2+cateto2**2return math.sqrt(somma_quad)

● L'istruzione return indica quant'è il risultato della funzione

Chiamata di funzioni

● >>> ipotenusa(3,4)● 5● >>> x=ipotenusa(12,5)● >>> x● 13● >>> a=5● >>> ipotenusa(a,a+7)● 13

argomenti

Corrispondenza tra parametri e argomenti

● La chiamata ipotenusa(3,4)fa corrispondere

ipotenusa(cateto1,cateto2)● la funzione ipotenusa la prima volta è eseguita

con i parametri cateto1=3 e cateto2=4● la seconda con cateto1=12 e cateto2=5● la terza con cateto1=5 e cateto2=12

Condizioni

● Operatori di confronto< > <= >= == !=

● Risultato True o False● Con le stringhe si usa l'ordine lessicografico● Ad esempio

● 'mara'<'marco' perchè

m a r am a r c o

e 'a'<'c'

Condizioni ed istruzioni condizionali

Condizioni

● Non confondere == (uguaglianza) con = (assegnamento)● a=b fa diventare a uguale a b, non produce nessun

risultato● a==b si chiede se a è uguale a b, ha come risultato

True o False

Esempi

● Posto a=8, b=5, c=3● >>> a==8● True● >>> a>=8● True● >>> b+c==a● False● >>> a*b<c● False

Esempi

● >>> a%2==0 si chiede se a è pari● True ● >>> c%2==0● False● >>> b%3==0● False

Operatori logici

● Per creare condizioni composte si usano gli operatori and, or e not

● L'operatore and ha la seguente tabella di verità

● C1 and C2 è True se e solo se sia C1 che C2 sono True

● C1 and C2 and … Cn è True se e solo se tutte le condizioni Ci sono True

False True

False False False

True False True

Operatori logici

● L'operatore or ha la seguente tabella di verità

● C1 or C2 è True se e solo se almeno uno tra C1 e C2 è True

● C1 or C2 or … Cn è True se e solo se almeno una condizione Ci è True

False True

False False True

True True True

Operatori logici

● L'operatore not inverte una condizione: not True fa False, not False fa True

● Leggi di De Morgan● not (C1 and C2) = (not C1) or (not C2)● not (C1 or C2) = (not C1) and (not C2)

Esempi

● Sempre nel caso a=8, b=5, c=3● >>> a==3 and b<6● False● >>> a!=3 and b<6● True● >>> a!=3 or b<6● True● >>> not a==8● False

Istruzioni condizionali

● L'istruzione condizionale in Python è if● Esistono tre tipi di istruzione if

● if...else● if senza else● if...elif...else

If...Else

● Sintassiif C: S1else:

S2● C è una condizione● S1 e S2 sono due sequenze di istruzioni,

rientrate a destra rispetto a if e a else● se C vale True, esegue S1, se invece C è False,

esegue S2

Semantica

● E' equivalente all'istruzione “Se” del nostro pseudo-codice

● Corrisponde al diagramma di flusso

Esempio ● per calcolare il massimo tra due numeri

def massimo(a,b):if a>b: m=aelse: m=breturn m

● >>> massimo(3,4)● 3● >>> massimo(9,5)● 9

Esempio

● per calcolare il massimo di tre numeri possiamo usare vari modi

def massimo3(a,b,c):if a>=b and a>=c:

m=aelse:

if b>c:m=b

else:m=c

return m

eseguito se non e' vero che a>=b e a>=c

Altra versione

● Oppure

def massimo3(a,b,c):m1=massimo(a,b)# m1 contiene il massimo tra a e bm=massimo(m1,c)return m

commento

Esempio

● per calcolare il massimo tra 4 numeri possiamo calcolare i massimi parziali tra i primi due e tra gli altri due, e poi il massimo dei due massimi

def massimo4(a,b,c,d):m1=massimo(a,b)m2=massimo(c,d)m=massimo(m1,m2)return m

Esempio

● Determiniamo se un anno è bisestile

def bisestile(anno):if anno%4==0 and (anno%100!=0 or anno

%400==0):return True

else:return False

Istruzione if

● Se nella parte else non c'è niente da eseguire, la si può omettere (if senza else)

if C: S

● La prima istruzione dopo la sequenza (quindi incolonnata con if) non è else

● Equivale aif C: Selse: pass

non fare niente

Semantica

● Corrisponde al diagramma di flusso

Esempio

● Vediamo un diverso modo di calcolare il massimo tra 3 numeri

def massimo3(a,b,c):m=aif b>m:

m=b# m è il più grande tra a e bif c>m:

m=creturn m

Esempio

● Analogamente per 4 numeri

def massimo4(a,b,c,d):m=aif b>m:

m=bif c>m:

m=cif d>m:

m=dreturn m

Esempio● Risolviamo un'equazione di II grado discutendo il

delta

def eq2grado(a,b,c):delta=b**2-4*a*cif delta>0:

x1=(-b-math.sqrt(delta))/(2*a)x2=(-b+math.sqrt(delta))/(2*a)print x1,x2

else:if delta==0:

x=-b/(2*a)print x,x

else: # delta<0print “soluzioni complesse”

Istruzione if-elif-else● L'esempio precedente si può risolvere in modo

più compatto con un'istruzione diversa● If-elif-else serve a codificare una serie di if in

cascata● In molti linguaggi (Pascal, C, Java, ecc.) non

c'è, ma al suo posto c'è un'istruzione che permette una scelta tra più alternative (case/switch)

Sintassi di If-elif-else

● La sintassi èif C1:

S1elif C2:

S2elif C3:

S3…elif Cn:

Snelse:

S0

C1,C2,...,Cn condizioniS1,S2,...,Sn,S0 sequenze di istruzioni

nota:unica ifuna o più elifunica else opzionale alla

fine

Semantica

● L'esecuzione di if-elif-else funziona così● Valuta C1, se è vera esegue S1● Altrimenti valuta C2 e se è vera esegue S2● Altrimenti valuta C3 e se è vera esegue S3● …● Altrimenti valuta Cn e se è vera esegue Sn● Altrimenti (se c'è la parte else) esegue S0

Semantica● Per n=4 corrisponde al diagramma di flusso

Esempio

● La soluzione dell'equazione di II grado diventa

def eq2grado(a,b,c):delta=b**2-4*a*cif delta>0:

x1=(-b-math.sqrt(delta))/(2*a) x2=(-b+math.sqrt(delta))/(2*a) print x1,x2

elif delta==0: x=-b/(2*a) print x,x

else: # qui delta<0 print “soluzioni complesse”

Esempio

● Determinare il numero di giorni in un mese

def lungh_mese(m):if m==4 or m==6 or m==9 or m==11:

ngiorni=30elif m==28:

ngiorni=28else:

ngiorni=31return ngiorni

se l'anno non è bisestile

Esempio

● Per classificare un triangolo in equilatero, isoscele o scaleno, in base ai tre lati a,b,c

def tipo_triangolo(a,b,c):if a==b and b==c:

tipo='equilatero'elif a==b or a==c or b==c:

tipo='isoscele'else:

tipo='scaleno'return tipo

so già che non è equilatero

Esempio

● per classificare una temperatura

def commenta_temperatura(t):if t<-10: commento='freddissimo'elif t<0: commento='molto freddo'elif t<10: commento='freddo'elif t<20: commento='fresco'elif t<30: commento='caldo'else: commento='molto caldo'

per 0<=t<10

per -10<=t<0

Istruzioni iterative:ciclo for

Istruzioni iterative

● In Python esistono due istruzioni iterative● while, per l'iterazione non limitata● for, per l'iterazione limitata

● Entrambe eseguono una sequenza di istruzioni S per un certo numero di volte

● Nell'iterazione limitata il numero di ripetizioni è noto a priori (quando il ciclo inizia)

● In quella non limitata lo si sa solo a fine ciclo

Istruzione for

● L'iterazione limitata stabilisce a priori il numero iterazioni

● E' molto diffuso usare una variabile (detta indice) che varia in un insieme finito

● Nella forma più semplice in Python l'intervallo è costituito da numeri interi e indicato con range(A,B)

● Attenzione: l'intervallo va da A (incluso) a B (escluso)range(A,B)={A, A+1, A+2, ..., B-2, B-1}

Istruzione for● Sintassi

for I in range(A,B):S

● ove I è la variabile indice, A e B sono espressione intere, con A≤B, S è una sequenza

● S è eseguita B-A volte● la prima volta con I=A● la seconda volta con I=A+1● la terza volta con I=A+2● …● l'ultima volta con I=B-1

Semantica del for

● L'esecuzione del ciclo for comporta i seguenti passi

1) inizializza la variabile I al valore di A

2) se I>=B il ciclo termina

3) (altrimenti) esegui S

4) incrementa I di 1

5) torna al passo 2)● Se A>=B, non esegue nulla

Semantica● Corrisponde al seguente diagramma di flusso

Esempio

● >>>for i in range(1,6):print i

● 1● 2● 3● 4● 5

Esempio

● Calcolare la somma dei numeri naturali da 1 a n

● L'algoritmo standard per calcolare una sommatoria è ● si usa una variabile accumulatore (somma)● all'inizio somma vale 0● si generano ad uno ad uno i dati da sommare● ogni dato è addizionato a somma

Esempio

def somma_interi(n):somma=0for i in range(1,n+1):

somma=somma+ireturn somma

● range ha come estremo superiore n+1 perché si vogliono sommare i numeri fino a n incluso (range(1,n+1) va da 1 a n)

● vediamo cosa accade quando n=5

Esempio

● Ecco l'andamento delle variabili i e somma

i somma

0

1 0+1=1

2 1+2=3

3 3+3=6

4 6+4=10

5 10+5=15

Esempio

● Per sommare dati ottenuti mediante in funzione dell'indice i si usa un procedimento analogo

● Ad esempio per sommare i quadrati dei numeri tra 1 e n

def somma_quadrati(n):somma=0for i in range(1,n+1):

somma=somma+i**2return somma

Esempio

● Supponiamo di voler calcolare la somma di n numeri che l'utente immette da tastiera

● Non c'è bisogno che i dati siano inseriti tutti in memoria, è sufficiente che l'utente ne digiti un dato per volta e che tale dato sia addizionato alla variabile somma

Esempio

def somma_numeri(n):somma=0for i in range(0,n):

dato=input('inserisci un numero ')somma=somma+dato

return somma● range(0,n) ha lo stesso numero di elementi di

range(1,n+1), cioè n

Esempio

● Nelle stesse condizioni di prima vogliamo trovare il massimo elemento

● Partiamo che il massimo è il primo dato letto da tastiera

● Poi aggiorniamo il massimo con i dati letti via via

Esempio

def massimo_numeri(n):dato=input('inserisci un numero')mass=datofor i in range(1,n):

dato=input('inserisci un numero')if dato>mass:

mass=datoreturn mass

● range(1,n) perché si devono leggere n-1 dati (il primo è già stato letto prima del ciclo)

Esempio

● Per calcolare il fattoriale di un numero intero n>0 dobbiamo calcolare il prodotto di tutti i numeri tra 1 e n.

● In modo analogo a somma_interi otteniamo

def fattoriale(n):prodotto=1for i in range(1,n+1):

prodotto=prodotto*ireturn prodotto

Esempio

● Per calcolare il coefficiente binomiale di due numeri interi n,k con n>0 e 0≤k≤n si può usare la definizione

● Otteniamo così una funzione che richiama tre volte la funzione fattoriale

nk =n !

k ! n−k !

Esempio

def coeff_binom(n,k):f1=fattoriale(n)f2=fattoriale(k)f3=fattoriale(n-k)cb=f1/(f2*f3)return cb

● Servono n+k+(n-k)=2n moltiplicazioni

Esempio

● E' possibile usare meno moltiplicazioni tramite la formula

def coeff_binom(n,k):prodotto=1for h in range(n-k+1,n+1):

prodotto=prodotto*hcb=prodotto/fattoriale(k)return cb

nk =∏

h=n− k1

n

h

k !

Cicli annidati

● In alcune situazioni serve inserire un ciclo for dentro un altro ciclo for

● Si dice che i due cicli sono annidati● Si distingue il ciclo più esterno e quello più

interno● Vediamo ora un esempio

Esempio

Visualizzare la tabella pitagorica

def tabella_pitagorica(): for r in range(1,11): for c in range(1,11): print r*c, print

● La seconda print serve per andare a capo alla fine di ogni riga della tabella

Risultato

1 2 3 4 5 6 7 8 9 10

2 4 6 8 10 12 14 16 18 20

3 6 9 12 15 18 21 24 27 30

4 8 12 16 20 24 28 32 36 40

5 10 15 20 25 30 35 40 45 50

6 12 18 24 30 36 42 48 54 60

7 14 21 28 35 42 49 56 63 70

8 16 24 32 40 48 56 64 72 80

9 18 27 36 45 54 63 72 81 90

10 20 30 40 50 60 70 80 90 100

Caratteristiche dei cicli annidati

● Si devono usare indici distinti● Il ciclo esterno (indice r) è eseguito 1 volta, con

10 iterazioni● Il ciclo interno (indice c) è eseguito 10 volte,

ognuna con 10 iterazioni● L'istruzione interna (print r*c,) è eseguita

10*10=100 volte● L'istruzione print è eseguita 10 volte

Caratteristiche dei cicli annidati● Si può immaginare che l'indice c varia con un velocità 10

superiore rispetto all'indice r

● Se si scrivono i valori di r e di c si ottiene(1 , 1) (1 , 2) (1 , 3) (1 , 4) (1 , 5) (1 , 6) (1 , 7) (1 , 8) (1 , 9) (1 , 10)

(2 , 1) (2 , 2) (2 , 3) (2 , 4) (2 , 5) (2 , 6) (2 , 7) (2 , 8) (2 , 9) (2 , 10)

(3 , 1) (3 , 2) (3 , 3) (3 , 4) (3 , 5) (3 , 6) (3 , 7) (3 , 8) (3 , 9) (3 , 10)

(4 , 1) (4 , 2) (4 , 3) (4 , 4) (4 , 5) (4 , 6) (4 , 7) (4 , 8) (4 , 9) (4 , 10)

(5 , 1) (5 , 2) (5 , 3) (5 , 4) (5 , 5) (5 , 6) (5 , 7) (5 , 8) (5 , 9) (5 , 10)

(6 , 1) (6 , 2) (6 , 3) (6 , 4) (6 , 5) (6 , 6) (6 , 7) (6 , 8) (6 , 9) (6 , 10)

(7 , 1) (7 , 2) (7 , 3) (7 , 4) (7 , 5) (7 , 6) (7 , 7) (7 , 8) (7 , 9) (7 , 10)

(8 , 1) (8 , 2) (8 , 3) (8 , 4) (8 , 5) (8 , 6) (8 , 7) (8 , 8) (8 , 9) (8 , 10)

(9 , 1) (9 , 2) (9 , 3) (9 , 4) (9 , 5) (9 , 6) (9 , 7) (9 , 8) (9 , 9) (9 , 10)

(10 , 1) (10 , 2) (10 , 3) (10 , 4) (10 , 5) (10 , 6) (10 , 7) (10 , 8) (10 , 9) (10 , 10)

Cicli annidati

● E' possibile che il range del ciclo interno dipenda dall'indice del ciclo esterno

● Ad esempio vogliamo disegnare un triangolo rettangolo isoscele sullo schermo con lato pari a L, tramite il carattere #

def disegna_triangolo(L):for r in range(1,L+1):

for c in range(1,r+1):print '#',

print

alla riga r scrive r cancelletti

Risultato con L=15

#

# #

# # #

# # # #

# # # # #

# # # # # #

# # # # # # #

# # # # # # # #

# # # # # # # # #

# # # # # # # # # #

# # # # # # # # # # #

# # # # # # # # # # # #

# # # # # # # # # # # # #

# # # # # # # # # # # # # #

# # # # # # # # # # # # # # #

Istruzioni iterative:ciclo while

Istruzione while● L'iterazione non limitata usa una condizione per

determinare la fine del ciclo● Nel ciclo while

● condizione vera → il ciclo continua● condizione falsa → il ciclo termina

● La condizione è valutata prima di ogni iterazione

● Casi limite● la condizione è falsa all'inizio del ciclo: 0 iterazioni● la condizione è sempre vera: ciclo infinito (il

programma non termina !!!)

Istruzione while

● Sintassiwhile C:

S

in cui C è una condizione e S è una sequenza di istruzioni

● Semantica

1) valuta C

2) se è falsa esci dal ciclo

3) (altrimenti) esegui S

4) torna al punto 1

Semantica del while

● In termini di diagramma di flusso

Esempio

Il classico algoritmo di Euclide per il calcolo del massimo comun divisore

def euclide(a,b):while a != b:

if a>b:a=a-b

else:b=b-a

return a

Esempio

● Una versione migliorata sfrutta il fatto che se a è (molto) più grande di b, al posto di sottrarre più volte, si può direttamente calcolare il resto della divisione di a per b

● A questo punto a sarebbe diventato più piccolo di b

● Per evitare la if si può semplicemente mettere il resto al posto di b e mettere b al posto

● Il ciclo termina quando b diventa 0

Versione migliorata

def euclide_veloce(a,b):while b!=0:

resto=a%ba=bb=resto

return a

Esempio

● Vogliamo sommare tutti i numeri inseriti dall'utente da tastiera senza sapere a priori quanti sono

● L'utente inserirà il valore 0 per segnalare la fine dei dati

● Per usare un while il primo dato va letto prima del ciclo

Esempio

def somma_numeri():somma=0msg='inserisci un numero (0 per terminare)'dato=input(msg)while dato!=0:

somma=somma+datodato=input(msg)

return somma

Esempio

● Calcolare la radice quadrata r di un numero reale a>0 con il seguente metodo iterativo● si parte con un'approssimazione anche grossolana,

ad esempio r=a● ad ogni passo r è sostituito da● si va avanti fintantoché il valore vecchio di r non

diventa praticamente uguale a quello nuovo

12 r ar

Esempio

def radice_approx(a):r=ar_old=0while abs(r-r_old)>=0.0001:

r_old=rr=0.5+(r+a/r)

return r

Esempio

● Vogliamo controllare se un dato numero intero n è un numero primo

● Un numero n è primo se gli unici suoi divisori sono 1 e n stesso

● Posso controllare se n è divisibile per qualche numero d compreso tra 2 e n-1

● Appena ne trovo uno, so che il numero non è primo ed esco dal ciclo

● Posso stabilire che il numero è veramente primo solo alla fine del ciclo

Esempio

def primo(n):trovato=Falsed=2while d<n and not trovato:

if n%d==0:trovato=True

else:d=d+1

return not trovato

Esempio

● Dato un numero intero n, trovare la somma delle cifre

● Ad esempio se n=1234, il risultato è 1+2+3+4=10

● Per risolvere l'esercizio si noti che dividendo n per 10● il resto è l'ultima cifra (nell'esempio 4)● il quoziente è composto dalle altre cifre

(nell'esempio 123)

Esempio

def somma_cifre(n):somma=0while n!=0:

resto=n%10somma=somma+reston=n/10

return somma

for e while● Il ciclo

for I in range(A,B): S

corrisponde aI=Awhile I<B:

SI=I+1

● In generale l'iterazione limitata è un caso particolare di quella non limitata

● Non vale il viceversa: esistono casi in cui il while non si può ricondurre al for

break e continue

● L'istruzione break interrompe un ciclo: l'esecuzione riprende dall'istruzione successiva al ciclo

● L'istruzione continue passa all'iterazione successiva

● Vediamo un esempio di uso di break nella verifica se un numero è primo

Esempio

def primo(n):trovato=Falsefor d in range(2,n):

if n%d==0:trovato=Truebreak

return not trovato

Sequenze e stringhe

Sequenze

● Una sequenza (detta in Python in modo improprio “lista”) è una collezione di elementi

● Normalmente nei linguaggi di programmazione si usano gli array, sequenze di elementi dello stesso tipo

● In Python è possibile usare anche sequenze eterogenee, cioè formate da elementi di tipo diverso (non faremo esempi del genere)

Sequenze

● >>> a=[1,5,3,4,2,8]● >>> a● [1,5,3,4,2,8]● >>> b=['Roma','Milano','Firenze','Napoli']● >>> len(a)● 6● >>> len(b)● 4

numero di elementi

Indici

● Ogni elemento di a è identificato da un indice che parte da 0

● L'ultimo elemento ha indice pari alla lunghezza di a meno 1

● In questo caso non esiste la posizione di indice 6 !!!

contenuto 1 5 3 4 2 8

indice 0 1 2 3 4 5

Sequenze ed indici

● >>> a[0]

● 1

● >>> a[2]

● 3

● >>> b[2]

● Firenze

● >>> a[6]

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

IndexError: list index out of range

errore: l'elemento numero di 6 di a non esiste !

Sequenze ed indici

>>> a[0]=9

>>> a

>>> [9,5,3,4,2,8]

>>> a[1]=a[2]+7

>>> a

>>> [9,10,3,4,2,8]

Concatenazione

● >>> a=[1,2,3]● >>> b=[7,8]● >>> c=a+b● >>> c● [1,2,3,7,8]● >>> d=b+a● >>> d● [7,8,1,2,3]

concatena a con b

Accodamento

● >>> a=[7,11,34,52]● >>> a.append(9)● >>> a● [7,11,34,52,9]● >>> a.append(15)● >>> a● [7,11,34,52,9,15]

Cancellazione

● Per cancellare un elemento basta usare il comando “del”

● Ad esempio con a=[7,11,34,52,9,15] il comando del a[2] produce la sequenza [7,11,52,9,15]

● Il vecchio a[2] (cioè 34) è stato eliminato e gli elementi successivi sono stati retrocessi di una posizione verso sinistra

● E' quindi poco costoso cancellare l'ultimo elemento, mentre è molto costoso cancellare il primo

Scorrere una sequenza con un ciclo for

● Supponiamo di voler calcolare la somma degli elementi di una sequenza A

● Serve un modo per accedere a tutti gli elementi● L'idea è quella di usare un ciclo for che fa

variare l'indice tra 0 e n-1, ove n è il numero di elementi di A

● Ad ogni passo si addiziona A[i] ad una variabile somma

Esempio

def somma_sequenza(A):n=len(A)somma=0for i in range(0,n):

somma=somma+A[i]return somma

Esempio

● Supponiamo di voler calcolare il massimo elemento di A

● In tal caso conviene inizializzare il massimo parziale “mass” con il primo elemento di A

● Poi, partendo dal secondo elemento, aggiornare mass, quando è necessario

Esempio

def massimo_sequenza(A):mass=A[0]n=len(A)for i in range(i,n):

if A[i]>mass:mass=A[i]

return mass● E' possibile definire modificare la funzione in

modo che restituisca la posizione del massimo

Mappatura

● Supponiamo di voler creare una nuova sequenza i cui elementi sono generati a partire da quelli di un'altra sequenza

● Ad esempio data una sequenza A di numeri reali, vogliamo creare una sequenza B che contiene il quadrato di ogni elemento di A

Prima versione con append

def quadrato(A):n=len(A)B=[ ]for i in range(0,n):

B.append(A[i]**2)return B

● L'uso continuo della funzione append può essere pesante dal punto di vista computazionale (la sequenza viene ridimensionata ad ogni passo)

sequenza vuota

Seconda versione

def quadrato(A):n=len(A)B=[ None ] * nfor i in range(0,n): B[i]=A[i]**2return B

● L'istruzione B=[ None ] * n crea una sequenza di n celle, ognuna delle quali è vuota

● Così si può usare B[i] senza che B sia ridimensionato ad ogni passo

Filtro

● Per selezionare una parte di una sequenza A, prendendo solo gli elementi che soddisfano una data proprietà P si può ● creare una sequenza inizialmente vuota● scorrere gli elementi di A● aggiungere con append gli elementi che verificano

P

● Ad esempio ottenere gli elementi pari di una sequenza di numeri interi

Esempio

def trova_pari(A):pari=[ ]n=len(A)for i in range(0,n):

if A[i]%2==0:pari.append(A[i])

return pari● Bisogna usare append quando non si sa quanti

sono gli elementi da selezionare

Stringhe

● Le stringhe sono particolari sequenze di caratteri che però sono immutabili (non possono essere cambiati gli elementi)

● Le costanti si indicano tra virgolette o tra apici● >>> nome=”Marco”

>>> len(nome)5>>> nome[0]M>>> nome[3]c

Stringhe

● Se si tenta di alterare la stringa si ottiene una situazione di errore

● >>> nome[1]='u'Traceback (most recent call last): File "<stdin>", line 1, in <module>TypeError: 'str' object does not support item assignment

● E' ovviamente possibile cambiare l'intero contenuto di nome

● >>> nome=”Luca”

Stringhe

● Operazioni di concatenazione e replicazione

>>> s=”ab”>>> t=”bc”>>> s+t>>> 'abbc'>>> t+s>>> 'bcab'>>> s*3>>> 'ababab'

Stringhe

● Operazione di sottostringa

>>> s=”Marco”>>> s[2:4]>>> “rc” >>> s[2:]>>> “rco”>>> s[:3]>>> “Mar”

dal carattere num. 2 al carattere num. 4 escluso

Strutture e riferimenti

Strutture

● In molti linguaggi di programmazione è presente un modo alternativo agli array di aggregare i dati

● Si chiamano strutture (o record) le aggregazioni di dati eterogenei

● Gli elementi di una struttura si chiamano campi● In Python non esiste un costrutto simile,

useremo le classi al suo posto

Esempio

● Vogliamo creare una struttura che abbia come campi i dati di una persona● cognome● nome● età● sesso

● Per fare ciò definiamo una classe con un opportuno inizializzatore

classe Persona

class Persona:def __init__(self):

self.cognome=Noneself.nome=Noneself.eta=Noneself.sesso=None

● In pratica la “funzione” init serve a indicare quali campi formano la classe Persona (cognome, nome, eta e sesso) attribuendo il valore speciale None ad ognuno di essi

Uso di Persona

Creiamo una variabile p di tipo Persona (oggetto della classe Persona) e riempiamone i campi

>>> p=Persona()>>> p.cognome=”Rossi”>>> p.nome=”Mario”>>> p.eta=40>>> p.sesso='M'

Uso di persona

● E' possibile creare tante persone...● Ad esempio eccone un'altra

>>> q=Persona()>>> q.cognome=”Verdi”>>> q.nome=”Luisa”>>> q.eta=35>>> q.sesso='F'

Strutture annidate

● E' possibile inserire un campo di tipo struttura all'interno di una struttura più grande

● Ad esempio una data composta da giorno, mese ed anno

class Data:def __init__(self):

self.giorno=Noneself.mese=Noneself.anno=None

Strutture annidate

● Poi in Persona usare la data di nascita anziché l'età

class Persona:def __init__(self):

self.nome=Noneself.cognome=Noneself.data_nascita=Noneself.sesso=None

Strutture annidate

● Prima creiamo la data di nascita

>>> dn=Data( )>>> dn.giorno=4>>> dn.mese=6>>> dn.anno=1965

● Poi la inseriamo come campo nella persona

>>> p=Persona( )>>> p.cognome=”Rossi”>>> p.nome=”Mario”>>> p.data_nascita=dn>>> p.sesso=”M”

Sequenze annidate

● Per ottenere quindi il giorno di nascita di Mario Rossi si dovrà scrivere

>>> p.data_nascita.giorno4

● Mentre per modificare l'anno

>>> p.data_nascita.anno=1966

Inizializzatore con parametri

● E' talvolta scomodo dover creare una struttura con i campi vuoti e poi con degli assegnamenti attribuire dei valori ai campi

● Si può definire per tale scopo un inizializzatore parametrico che ha come parametri i valori dei campi da inizializzare

● I valori debbono essere passati al momento in cui si crea una nuova struttura

Esempio

● Modifichiamo la classe Data

class Data:def __init__(self,gg,mm,aa): self.giorno=gg self.mese=mm self.anno=aa

● E' ora possibile scrivere

>>> dn=Data(4,6,1965)● oppure

>>> p.data_nascita=Data(4,6,1965)

self è un parametro implicito, non deve essere considerato un parametro normale

Riferimenti

● Il comportamento di Python nei confronti delle strutture (oggetti) è diverso da quello che ha nei confronti dei tipi elementari

● Confrontate>>> a=10>>> b=a>>> b10>>> a=11>>> b10

>>> p=Persona()>>> p.cognome=”Rossi”>>> q=p>>> q.cognome'Rossi'>>> p.cognome=”Verdi”>>> q.cognome'Verdi'

Confronto

● Quando Python opera con dati elementari (nell'esempio numerici), l'assegnamento crea una copia del valore: ● a e b contengono lo stesso numero● però modificando a, b rimane inalterato

● Invece con le strutture, Python usa i riferimenti:● p e q si riferiscono alla stessa struttura in memoria● cambiando il cognome della struttura di p, cambia

anche quello (che poi è lo stesso) di q

Riferimenti

● Quello che accade è che sia p che q si riferiscono alla stessa persona

p

q

cognome Rossinomeetasesso

Riferimenti● Per rendersene conto è sufficiente vedere che

hanno lo stesso valore di id (indirizzo in RAM del valore contenuto nella variabile)

● >>> id(p)● 3078679564● >>> id(q)● 3078679564

Riferimenti e sequenze● Lo stesso comportamento si ha con le sequenze● >>> a=[1,3,5,7,9]● >>> b=a● >>> b[0]● 1● >>> b[0]=4● >>> b● [4,3,5,7,9]● >>> a● [4,3,5,7,9]

ora b si riferisce alla stessa sequenza di a

Copia di una sequenza● Molte volte è necessario ottenere una copia di

una sequenza, ovvero una nuova sequenza b identica ad a, una sequenza già esistente

● Si può usare il trucco di assegnare a b la concatenazione di a con la sequenza vuota (crea comunque una nuova sequenza)

● >>> a=[1,2,4,5]● >>> b=a+[ ]● >>> a[0]=9● >>> b● [1,2,4,5]

Riferimenti e gestione della memoria

● In Python una variabile non contiene mai una sequenza o una struttura, ma contiene l'indirizzo RAM in cui la sequenza o la struttura sono realmente memorizzate

● L'assegnamento tra una variabile ed un'altra non crea mai una nuova sequenza o struttura● per creare una nuova sequenza bisogna indicare gli

elementi (ad esempio [1,2,3]) o usare qualche operazione tra sequenze (ad esempio il +)

● per creare una nuova struttura bisogna usare l'inizializzatore della classe (ad esempio Persona())

Sequenze di strutture

● E' possibile creare una sequenza i cui elementi sono strutture

● Ad esempio leggiamo da tastiera i dati di n persone e mettiamoli in una sequenza a

● La notazione a[3].cognome

indicherà ovviamente il cognome della quarta persona della struttura

Esempio

def leggi_dati(n):a=[ None ] * nfor i in range(0,n):

p=Persona( )p.cognome=raw_input('inserisci il cognome ')p.nome=raw_input('inserisci il nome ')…a[i]=p

return a

Sequenze di strutture

● Una sequenza di strutture è una struttura dati importante perché consente di avere un contenitore dati assimilabile, con i dovuti limiti, ad una tabella di un database

● Un modo migliore sarà quello di usare le liste, come vedremo in seguito

Funzioni e parametri

Aspetti teorici sulle funzioni

● Studiamo ora dal punto di vista teorico cosa accade quando si usano le funzioni

● Una funzione è definita mediante il costrutto def, in cui si stabilisce il nome, i parametri e il corpo (ovvero le istruzioni della funzione)

● Una funzione è richiamata mediante il costrutto di chiamata a funzione in cui si indica il nome e gli argomenti

Funzioni e parametri● Supponiamo di avere le seguenti funzioni

def funzione1(n):x=3y=7+nz=8r=funzione2(x-1,y+1)return r+z

def funzione2(a,b):x=a+b-1z=b-2return z*x

Semantica della chiamata

● Nell'esempio funzione1 chiama funzione2● Supponiamo che funzione1 è in esecuzione

con n=5● Cosa accade esattamente quando funzione1

chiama funzione2 ?● Nella chiamata funzione2(x-1,y+1), x-1 e y+1

sono gli argomenti (detti anche parametri attuali)

● Nella definizione funzione2(a,b), a e b sono i parametri (detti anche parametri formali)

Semantica della chiamata

1) l'esecuzione di funzione1 è momentaneamente sospesa

2) gli argomenti della chiamata a funzione2 sono valutati e i valori (nell'esempio 2 e 13) sono usati per inizializzare i corrispondenti parametri (a e b)

3) inizia l'esecuzione di funzione2

4) funzione2 termina al primo return eseguito o all'ultima istruzione della funzione

5) funzione1 riparte, potendo utilizzare il valore restituito dalla return (nell'esempio 154)

Stack di sistema

● Python, come altri linguaggi, usa una particolare struttura dati, chiamata stack

● Per ogni funzione chiamata sono memorizzate nello stack informazioni molto importanti, che formano il record di attivazione● le variabili locali● i parametri● ”l'indirizzo” dell'istruzione da cui ripartire quando la

funzione termina

Stack di sistema

● Se una funzione f1 chiama un'altra funzione f2, il record di attivazione di f2 entra nello stack

● Quando f2 termina, Python toglie dallo stack il record di attivazione di f2 e fa ripartire f1

● Cosa succede se anche f2 chiama un'altra funzione f3 e sua volta f3 chiama una quarta funzione f4 ?

Stack di sistema

● Lo stack conterrà nell'ordine le informazioni relative a f1, f2, f3 e f4

● Possiamo rappresentarlo così

f1

f2

f3

f1

f2

f4

Stack di sistema

● Appena f4 termina, il suo record di attivazione esce dallo stack e sarà fatta ripartire la funzione che si trova adesso nella “cima” dello stack, cioè f3

● Lo stack diventerà perciò

f1

f2

f3

Stack di sistema

● La gestione dello stack adotta quindi una politica LIFO (Last In First Out): la prima funzione che esce dallo stack è l'ultima che vi è entrata

● Vedremo successivamente come si può implementare uno stack (chiamato in italiano anche “pila”)

Passaggio per valore

● Il passaggio usato in Python è per valore: il valore di ogni argomento serve solo per inizializzare il corrispondente parametro

valore

argomento parametro● Non c'è nessun passaggio nel verso opposto:

ogni modifica fatta su un parametro non ha effetto sul corrispondente argomento

Esempiodef scambia(x,y):

temp=xx=yy=tempprint x,y

>>> a=1>>> b=2>>> scambia(a,b)2 1>>> a1>>> b2

x e y sono stati effettivamente scambiati

ma a e b in realtà non sono stati scambiati

Commento

● L'esempio precedente non scambia i due argomenti, nonostante che la funzione abbia scambiato i due parametri

● In realtà in Python non c'è modo di scambiare due variabili tramite una funzione

● Infatti servirebbe il passaggio per riferimento, che è presente in qualche linguaggio (Pascal, ADA, C++, C#, ...)

Passaggio per riferimento

● Ad esempio in Pascal

procedure scambia(var x,y:integer);var temp:integer;begin

temp:=x;x:=y;y:=temp;

end;

Passaggio dei parametri non elementari

● Quando l'argomento di una funzione è di tipo sequenza o struttura, il parametro è un riferimento a tale sequenza o struttura e non una copia

● Il passaggio consiste nel copiare il riferimento (indirizzo) dell'argomento nel parametro corrispondente

● Perciò la funzione può modificare il contenuto dell'argomento

Esempio con le sequenze

def raddoppia_sequenza(a):n=len(a)for i in range(0,n):

a[i]=2*a[i]

>>> b=[1,2,3,4]>>> raddoppia_sequenza(b)>>> b[2,4,6,8]

a si riferisce alla stessa sequenza di b

[ 1 | 2 | 3 | 4 ]

Esempio con le strutture

class punto:def __init__(self):

self.x=Noneself.y=None

def trasla(p):p.x=p.x+1p.y=p.y+1

p deve essere un punto, la funzionetrasla il punto di un'unità in tutte e duele dimensioni

Esempio con le strutture

>>> P=punto()>>> P.x=19>>> P.y=8>>> trasla(P)>>> P.x20>>> P.y9

le coordinate di P sono state cambiate dalla funzione trasla

Precisazione

● Una funzione può cambiare il contenuto di uno o più elementi di una sequenza o di uno o più campi di una struttura (vedi esempi precedenti)

● Una funzione però non può far sì che l'argomento si riferisca ad un oggetto diverso

● Ovvero l'oggetto a cui si riferisce l'argomento può essere alterato solo in alcune delle sue componenti, ma non può cambiare indirizzo

Precisazione● Ad esempio

def svuota(A):A=[]

non funziona● Infatti

>>> B=[1,2,3,4]>>> svuota(B)>>> B[1,2,3,4]

● Per svuotare una sequenza bisogna cancellare (con “del”) tutti i suoi elementi

Riepilogo dei passaggi

● Se l'argomento è di tipo elementare (interi, reali, booleani, stringhe), il parametro è una copia dell'argomento:● modificando il parametro l'argomento non cambia

● Se l'argomento è di tipo strutturato (sequenze, record, oggetti) il parametro contiene lo stesso indirizzo (riferimento) dell'argomento● la funzione modificando il contenuto del parametro

altera anche quello dell'argomento

Parametri errati

● Se il numero di argomenti non è uguale al numero dei parametri, si ha un errore immediato del tipoTypeError: F( ) takes exactly M argument (N given)

● Ad esempio si ottiene questo errore chiamando funzione2 con 1 o 3 argomenti

Parametri errati● In alcune situazioni l'errore potrebbe consistere

nell'utilizzare argomenti di tipo diverso da quello atteso

● Ad esempio in >>> raddoppia_sequenza(5)5 non è un argomento corretto perché il parametro 'a' deve essere una sequenza

● Questo tipo di errore non è rilevato da Python al momento della chiamata, ma solo quando si tenta di usare l'indice sul parametro a

Uso delle funzioni

● Le funzioni sono utilizzate fondamentalmente per tre scopi● modularizzazione e decomposizione● fattorizzazione● riutilizzabilità

Scomposizione di un problema

● Anziché risolvere un problema tutto insieme spesso conviene scomporre un problema in sottoproblemi

● Ogni sottoproblema può essere risolto tramite una o più funzioni

● Serve poi una funzione “complessiva” che funge da raccordo e chiama le funzioni associate ai sottoproblemi

Modularizzazione

● In generale è una ottima tecnica di programmazione quella di lavorare con le funzioni

● Infatti ogni funzione, in maniera indipendente dalle altre, può essere ● progettata ● implementata ● verificata se ha un corretto funzionamento● eventualmente modificata per correggere errori o

aggiornarla per nuove esigenze

Fattorizzazione

● In alcune situazioni le stesse operazioni devono essere svolte in più punti all'interno dello stesso programma

● Mettere tali istruzioni in una funzione, che poi e richiamata tutte le volte che serve, è molto conveniente e si hanno notevoli vantaggi● il programma è più leggibile● il programma è più facilmente modificabile

Riutilizzabilità

● Una funzione si può facilmente riutilizzare in altri programmi (un insieme arbitrario di istruzioni no)

● E' una prassi molto diffusa quella di usare funzioni scritte da altri

● E' ancora più diffusa la pratica di usare funzioni di “libreria”, cioè una raccolta di funzioni

● Molti linguaggi, incluso Python, hanno già nello loro standard svariate librerie

Visibilità delle variabili

● Una funzione non può accedere né alle variabili di altre funzioni, né alle variabili definite a linea di comando (variabili globali)

● Una funzione può accedere solo ai parametri e alle variabili “create” al suo interno

● Nota: in Python non è esattamente così, ma in prima approssimazione si può assumere tale ragionamento come corretto

● In realtà una funzione Python non può modificare una variabile globale, però può accedere al suo contenuto

Esempio

def funzione1(a,b):x=a+1y=b+2for i in range(1,5):

x=x+areturn x-y

def funzione2(c):n=0while c>0:

c=c/10 n=n+1

return n

funzione1 può usare solo le variabili x,y,a,b,i

funzione2 può usare solo le variabili c e n

Variabili omonime

● Se in due funzioni compare una variabile con lo stesso nome, in realtà si tratta di due variabili distinte

def funzione1(n):a=3…

def funzione2(x,y):a=4...

Le due variabili chiamate 'a' non hanno nessun collegamento, sono indipendenti l'una dall'altra

Variabili globali

● Una variabile globale è una variabile creata a linea di comando (attribuendole un valore)

● Una funzione può accedere e modificare una o più variabili globali solo se elenca preventivamente mediante il comando 'global' tutte le variabili globali a cui vuole accedere

● Ad esempiodef funzione(x,y):

global a,ca=a+2...

funzione può accedere e modificare le variabili globali a e c

Esempio

>>> a=10>>> b=2>>> c=3>>> funzione(0,1)>>> a12

funzione ha modificato a

Vita delle variabili

● Le variabili sono memorizzate nella RAM (alcuni linguaggi usano anche i registri del processore)

● L'allocazione è il momento in cui la variabile inizia ad esistere nella memoria, occupandone una parte

● La deallocazione è il processo inverso: la variabile non è più presente in memoria (e il valore in essa contenuto si perde)

Vita delle variabili

● Le variabili locali e i parametri di una funzione sono allocate al momento in cui inizia l'esecuzione della funzione e deallocate nel momento in cui termina

● Tale tipo di allocazione si chiama (in altri linguaggi) automatica

Ricorsione

Ricorsione

● La ricorsione è una potente tecnica di programmazione alternativa all'iterazione

● Il fondamento teorico della ricorsione è l'induzione matematica

● L'induzione serve a dimostrare la correttezza di una funzione ricorsiva

● Inoltre il ragionamento induttivo è fondamentale per poter programmare in modo ricorsivo

Esempio

● Vogliamo calcolare il fattoriale di un numero naturale n

● n! è uguale al prodotto di tutti i numeri naturali compresi tra 1 e nn!= 1∙2∙3∙ …∙(n-1)∙n

● 0! si assume per definizione uguale a 1● Vale la seguente legge ricorsiva

se n>0, n!=n∙(n-1)!● Infatti (n-1)! è il prodotto dei numeri naturali tra 1 e

n-1, se lo si moltiplica per n, si ottiene il prodotto dei numeri naturali compresi tra 1 e n

Definizione ricorsiva

● Indicando con f(n) la funzione che ad ogni numero naturale n associa il fattoriale di n si ha quindi la seguente definizione ricorsiva

f(n)=n∙f(n-1) se n>0

f(n)=1 se n=0● E' infatti indispensabile, per avere una definizione

completa, aggiungere anche almeno un caso base

● Il caso base è una legge non ricorsiva, in cui la funzione f è calcolata direttamente

Definizione ricorsiva e calcolo della funzione

● La definizione precedente può essere scritta ed usata in Python senza problemi

● Infatti una funzione definita ricorsivamente può essere calcolata direttamente dai moderni linguaggi di programmazione grazie alla gestione dello stack e dell'allocazione automatica delle variabili locali

Esempio

def fattoriale(n):if n==0:

ris=1else:

ric=fattoriale(n-1)ris=n*ric

return ris

chiamata ricorsiva:fattoriale richiama se stessa

Dimostrazione per induzione● Dimostriamo per induzione che “fattoriale” è

una funzione corretta, ovvero che per ogni n∈N, fattoriale(n) dà come risultato n!

● Il caso base è semplice. Se n=0, fattoriale(0) dà come risultato 1, che è uguale a 0! per definizione

● Sia ora n>0● Supponiamo ora per ipotesi induttiva che la

funzione fattoriale sia corretta per il valore n-1, ovvero che fattoriale(n-1) dia come risultato (n-1)!

Dimostrazione per induzione

● Sotto tale ipotesi il calcolo di fattoriale(n) procede così● ric vale (n-1)!● ris vale n∙(n-1)! ovvero n!● il risultato restituito è quindi n!

● Perciò se fattoriale(n-1) restituisce (n-1)!, allora fattoriale(n) restituisce n!

● Per il principio di induzione matematica la funzione fattoriale è corretta

Perché la ricorsione funziona in Python

● Cosa succede in Python quando si chiama fattoriale(4) ?

● L'esecuzione di fattoriale(4) crea 3 variabili● n=4● ric=?● ris=?

● Poiché n>0, la funzione richiama se stessa con argomento 3 e si sospende

per ora non hanno un valore

Ricorsione in Python

● Sono create tre nuove variabili● n=3● ric=?● ris=?

● Di nuovo, poiché n>0, la funzione richiama se stessa e si sospende

● Sono di nuovo create altre tre variabili● n=2● ric=?● ris=?

Ricorsione in Python

● E così via● La sequenza di chiamate ricorsive terminerà

quando il parametro n è 0● Nello stack si avranno 5 record di attivazione

relative alle 5 chiamate a fattoriale, ognuno con 3 variabili (n, ric e ris)

● Ogni chiamata è contraddistinta da un valore diverso di n

Stack con le chiamate di fattoriale

● Possiamo rappresentare lo stack così

n=0, ric=?, ris=?

n=1, ric=?, ris=?

n=2, ric=?, ris=?

n=3, ric=?, ris=?

n=4, ric=?, ris=?

fattoriale(0):

fattoriale(1):

fattoriale(2):

fattoriale(3):

fattoriale(4):

Raggiunto il caso base

● A questo punto n=0, per cui non si hanno chiamate ricorsive e il risultato è 1

● Il record di attivazione di fattoriale(0) esce dallo stack e viene ripristinata la chiamata di fattoriale(1)

● n vale 1● ric vale 1, perché è il risultato di fattoriale(0)● ris diventa n*ric=1∙1=1● fattoriale(1) termina e il risultato è 1

Ripristino delle chiamate precedenti

● A questo punto fattoriale(2) è fatta ripartire● ric vale 1● ris vale n*ric=2∙1=2● fattoriale(2) termina e il risultato è 2● A questo punto fattoriale(3) è fatta ripartire● ric vale 2● ris vale n*ric=3∙2=6● fattoriale(3) termina e il risultato è 6

Fine della ricorsione

● A questo punto fattoriale(4) è fatta ripartire● ric vale 6● ris vale n*ric=4∙6=24● fattoriale(4) termina e il risultato è 24

Commenti finali

● Negli esempi useremo ancora le variabili ric e ris

● ric conterrà il risultato della chiamata ricorsiva● ris invece conterrà il risultato finale della

funzione, di solito si ottiene svolgendo alcune operazioni su ric

Variabili ric e ris

● Una volta presa confidenza con la ricorsione, si possono eliminare le variabili ric e ris

● Ecco ad esempio il fattorialedef fattoriale(n):

if n==0:return 1

else:return n*fattoriale(n-1)

● Noi però continueremo ad usare ric e ris

Come si programma in modo ricorsivo

● Per risolvere un problema in modo ricorsivo occorre trovare● uno o più leggi ricorsive, in cui la risoluzione del

problema è ottenuta mediante la soluzione dello stesso problema (con input diversi)

● uno o più casi base, in cui la soluzione si ottiene direttamente (e possibilmente con poco sforzo)

Trovare le leggi ricorsive

● Un procedimento con cui ottenere delle leggi ricorsive è il seguente

● Supponiamo di voler calcolare f(x) in modo ricorsivo

● Immaginiamo di avere a disposizione un “oracolo” che ci indica il valore di f per uno o più argomenti y diversi da x (in genere minori di x), ad esempio il valore di f(x-1)

● In che modo potrebbe essere utilizzato f(y) per ottenere f(x) ?

Trovare le leggi ricorsive

● Una legge ricorsiva è quindi un modo per calcolare f(x), più o meno agevolmente, a partire dal valore noto di f(y)

● Nell'esempio del fattoriale, la legge ricorsiva lega n! al valore di (n-1)!

● Spesso uno studio preliminare del comportamento di f è utile a individuare le leggi ricorsive

Casi base

● I casi base sono invece necessari ad interrompere la catena delle chiamate ricorsive

● Se si eliminasse il caso base sul fattoriale si otterrebbe una funzione non terminantedef fattoriale(n):

ric=fattoriale(n-1)ris=n*ricreturn ris

in cui si hanno (almeno teoricamente) infinite chiamate ricorsive

Casi base

● E' necessario individuare un numero sufficiente di casi base, in modo che qualsiasi sia l'argomento x della funzione, dopo un numero finito di chiamate ricorsive, si arriva ad un caso base

● In molti problemi, i casi base consistono in situazioni facili o particolari (ad esempio il fattoriale di 0)

Esempio

● Calcolare xn mediante n moltiplicazioni successive

● Legge ricorsivaxn=x∙ xn-1 per n>0

● Caso basexn=1 per n=0

● La validità della legge ricorsiva e del caso base sono ovvie

Esempio

def potenza(x,n):if n==0:

ris=1.0else:

ric=potenza(x,n-1)ris=x*ric

return ris

Esempio

● Un metodo più veloce per calcolare xn è dato dalle seguenti leggi ricorsive

● se n è pari e >0

● se n è dispari invece

xn= x2n2

xn=x⋅ x2n−1

2

Esempio

def potenza_veloce(x,n):if n==0:

ris=1elif n%2==0:

ris=potenza_veloce(x*x,n/2)else:

ric=potenza_veloce(x*x,(n-1)/2)ris=x*ric

return ris

Confronto tra le due funzioni ricorsive per il calcolo della potenza

● potenza impiega n moltiplicazioni per calcolare xn

● potenza_veloce necessita di log2n chiamate

ricorsive, ognuna delle quali al massimo svolge 2 moltiplicazioni. In totale usa al massimo 2 log

2n moltiplicazioni.

Dimostrazione per induzione

● Lo schema ricorsivo di questo esempio è diverso da quelli precedenti: da n si passa a n/2 o a (n-1)/2

● La dimostrazione per induzione usa perciò una diversa formulazione del principio di induzione

● Il caso base è lo stesso: se n=0, potenza_veloce(x,n) dà come risultato 1, che corrisponde a x0

Dimostrazione per induzione

● Supponiamo, per ipotesi induttiva, che potenza_veloce(x,m) sia corretta per tutti i valori m<n, ovvero che dia come risultato xm

● Allora il calcolo di potenza_veloce(x,n) procede così

● Se n è pari, ric vale potenza_veloce(x*x,n/2), che per ipotesi induttiva è

● Tale numero è poi il risultato finale

x2n2=xn

Dimostrazione per induzione

● Se invece n è dispari, allora ric vale potenza(x*x,(n-1)/2), che per ipotesi induttiva corrisponde a

● Il risultato finale sarà quindi x*ric ovvero xn

x2 n−1

2 = xn−1

Numeri di Fibonacci

● I numeri di Fibonacci sono una successione di numeri interi, i cui primi elementi sono1 1 2 3 5 8 13 21 34 55 89

● Ogni elemento, tranne i primi due, è la somma dei due elementi precedenti (ad esempio 8=3+5)

● La successione è generata da un famoso problema (proposto da Fibonacci nel XIII secolo) e ha molte applicazioni sia informatiche che non

Numeri di Fibonacci in Python

def fibonacci(n):if n==1 || n==2:

ris=1else:

ric1=fibonacci(n-1)ric2=fibonacci(n-2)ris=ric1+ric2

return ris

Costo della funzione ricorsiva Fibonacci

● Calcolare i numeri di Fibonacci con questa funzione ricorsiva non è per niente efficiente

● Per rendersene conto basta pensare che per calcolare fibonacci(7) occorre calcolare fibonacci(6) e fibonacci(5)● a sua volta per fibonacci(6) occorre calcolare

fibonacci(5) e fibonacci(4)● mentre per calcolare fibonacci(5) occorrono

fibonacci(4) e fibonacci(3)● …

Costo della funzione ricorsiva Fibonacci

● Continuando lo schema precedente si nota che● fibonacci(5) è calcolato 2 volte● fibonacci(4) è calcolato 3 volte● fibonacci(3) è calcolato 4 volte● …

● Il numero di addizioni richieste cresce in maniera esponenziale

● Invece la versione iterativa necessita solo di n-2 addizioni

Contare le cifre

● Dato un numero naturale n, vogliamo contare le sue cifre decimali

● Ad esempio n=134788 ha 6 cifre● Indicando con L(n) il numero di cifre di n, vale

la seguente regola ricorsivaL(n)=1+L(n/10)

● ove per n/10 si intende il quoziente della divisione di n per 10

● La legge è ovvia: n/10=13478 ha 5 cifre● Il caso base è per n<10, in cui L(n)=1

Contare le cifre

def conta_cifre(n):if n<10:

ris=1else:

ric=conta_cifre(n/10)ris=ric+1

return ris

Conversione in binario

● Per convertire un numero in base 2 si può usare una semplice definizione ricorsiva

● Indicando con B(n) la stringa binaria corrispondente al numero n si ha la seguente legge ricorsiva, per n>=2

B(n)=B(q) concatenato con (r come stringa)

in cui q è il quoziente della divisione di n per 2 e d r è il resto

● Ad esempio B(17)=B(8) “+” 1, infatti B(17)=10001 e B(8)=1000

Conversione in binario

Il caso base è per n=0 o n=1, in cui B(n) è uguale a n (come stringa)

def binario(n):if n<2:

ris=str(n)else:

ric=binario(n/2)ris=ric+str(n%2)

return ris

Ricorsione sulle sequenze

● Una definizione ricorsiva di una funzione f che ha tra gli argomenti una sequenza si può ottenere così● il caso base è quando la sequenza è vuota o ha un

solo elemento (in genere è “piccola a sufficienza”)● le leggi ricorsive legano il valore di f sull'intera

sequenza al valore di f sulla sequenza a cui è stato tolto un elemento (ad esempio il primo o l'ultimo) o alcuni elementi

Esempio

● Vogliamo calcolare ricorsivamente la somma di una sequenza a

● Se a ha un solo elemento, quello è la somma (caso base)

● Una legge ricorsiva è la seguente● sia ric la somma di tutti gli elementi tranne il primo,

che si ottiene chiamando la funzione ricorsivamente sulla sequenza a[1:] (ovvero tutti tranne il primo)

● il risultato è quindi a[0]+ric

Esempio

def somma_ricorsiva(a):if len(a)==1:

ris=a[0]else:

ric=somma_ricorsiva(a[1:])ris=a[0]+ric

return ris

Altra direzione

● Si può ottenere una soluzione alternativa usando una legge ricorsiva “opposta”● sia ric la somma della sequenza tranne l'ultimo

elemento● il risultato è a[n-1]+ric

● Per togliere l'ultimo elemento si può scrivere a[:n-1]

● La prima soluzione opera sui suffissi di a (da un certo elemento in poi), la seconda sui prefissi (fino ad un certo elemento)

Esempio

def somma_ricorsiva(a):if len(a)==1:

ris=a[0]else:

ric=somma_ricorsiva(a[:n-1])ris=ric+a[n-1]

return ris

Maggiore efficienza

● Per avere una maggiore efficienza si può evitare di creare una nuova sequenza (togliendo elementi)

● Si può infatti indicare qual è l'ultimo elemento della sottosequenza (prefisso) o il primo (suffisso)

● Ad esempio nella ricorsione sui prefissi si può passare un secondo parametro n che indica il numero di elementi presenti nella sequenza da sommare

Esempio

def somma_ricorsiva(a,n):if n==1:

ris=a[0]else:

ric=somma_ricorsiva(a,n-1)ris=a[n-1]+ric

return ris

Esempio

● Un altro esempio è il calcolo del massimo elemento di una sequenza

● Il caso base è ovvio● La regola ricorsiva dice che se ric è il massimo

della sequenza tranne il primo elemento, il risultato è il maggiore tra ric e il primo elemento

Esempio

def massimo_ricorsivo(a,n):if n==1:

ris=a[0]else:

ric=massimo_ricorsivo(a,n-1)if ric>a[n-1]:

ris=ricelse:

ris=a[n-1]return ris

Esempio

● Un altro esempio è la ricerca di un valore x all'interno di una sequenza A di n elementi (problema della ricerca)

● Una versione iterativa è presentata nella terza parte di questi appunti

● Ci sono due casi base● x è il primo elemento (risultato True)● n=0 (risultato False)

Esempio

● La legge ricorsiva è ovvia: se x non è il primo elemento, il risultato è quello che si ha cercando x nella sequenza A[1:], ovvero ottenuta da A togliendo il primo elemento

● Detto in altri termini, se x non è il primo elemento di A, può comparire a partire dal secondo elemento

Esempio

def cerca_ric(x,A):n=len(A)if n==0:

ris=Falseelif A[0]==x:

ris=Trueelse:

ris=cerca_ric(x,A[1:])return ris

Esempio

● Una versione più efficiente evita di creare una nuova sequenza ad ogni passaggio

● Usiamo quindi un terzo parametro p che indica il primo elemento di A da considerare

● I casi base diventano● p=n (risultato False)● A[p]=x (risultato True)

Esempio

def cerca_ric(x,A,p):n=len(A)if p==n:

ris=Falseelif A[p]==x:

ris=Trueelse:

ris=cerca_ric(x,A,p+1)return ris

Esempio

● Vogliamo controllare se una sequenza A di n elementi è palindroma:● il primo elemento è uguale all'ultimo● il secondo è uguale al penultimo● ecc.

● Un primo case base è quando n=0 o n=1● In tale caso la risposta è ovviamente True● Un altro caso base è quando il primo elemento

non è uguale all'ultimo (risultato False)

Esempio

● La regola ricorsiva è quando il primo elemento è uguale all'ultimo, la sequenza A è ricorsiva se e solo se è ricorsiva la sequenza che si ottiene da A togliendo il primo e l'ultimo elemento

● Perciò da A si passa a A[1:n-1]

Esempio

def palindroma_ric(A):n=len(A)if n==0 or n==1:

ris=Trueelif A[0]!=A[n-1]:

ris=Falseelse

ris=palindroma_ric(A[1:n-1])return ris

Esempio

● Per avere una maggiore efficienza si possono usare due indici (s e d) che indica l'elemento più a sinistra e l'elemento più a destra da controllare

● I casi base sono● s>=d (cioè zero o un elemento, risultato True)● A[s]=A[d] (risultato False)

● La regola ricorsiva aumenta s e diminuisce d● All'inizio s=0 e d=n-1

Esempio

def palindroma_ric(A,s,d):if s>=d: ris=Trueelif A[s]!=A[d]: ris=Falseelse: ris=palindroma_ric(A,s+1,d-1)return ris

def palindroma(A):return palindroma_ric(A,0,len(A)-1)

Torri di Hanoi

● Il problema delle torre di Hanoi consiste nello spostare n dischi dal piolo 1 al piolo 3, usando il piolo 2 come appoggio

1 2 3

Regole delle torre di Hanoi

● Si deve spostare solo un disco per volta● Il disco da spostare non deve avere un altro

disco sopra● Il disco può essere messo sopra un disco più

grande, ma non sopra ad uno più piccolo

Soluzione delle torri di Hanoi

● Il problema può essere risolto in maniera ricorsiva usando la seguente strategia

● Per spostare n dischi dal piolo x al piolo y (chiamando z il piolo restante) si deve● spostare i primi n-1 dischi da x a z● spostare il disco rimanente da x a y● rispostare gli n-1 dischi da z a y

Torri di Hanoi in Python

def hanoi(n,x,y):if n==1:

print “sposta il primo disco di “,x, “ su “,yelse:

z=6-x-yhanoi(n-1,x,z)print “sposta il primo disco di “,x, “ su “,yhanoi(n-1,z,y)

Commenti

● L'istruzione z=6-x-y trova l'altro piolo, a partire dai due pioli x e y (provare tutte le possibilità)

● Il numero di operazioni di spostamento di dischi singoli necessari a risolvere il problema è 2n-1

● Ad esempio● per n=1, 1 operazione● per n=2, 3 operazioni● per n=3, 7 operazioni● per n=4, 15 operazioni

Confronto tra ricorsione ed iterazione

● Dal punto di vista di “possibilità di calcolo” si equivalgono:● ogni funzione ricorsiva si può calcolare in modo

iterativo (con cicli while e for)● ogni funzione iterativa si può calcolare tramite una

funzione ricorsiva

● Però non si equivalgono né dal lato “espressivo” né dal lato “computazionale”

Espressività

● Per molti programmatori, l'iterazione è più naturale ed intuitiva rispetto alla ricorsione: la ricorsione impone un modo di ragionare induttivo che all'inizio è oggettivamente difficile da utilizzare

● In moltissime situazioni le soluzioni iterative sono più semplici e dirette, mentre quelle ricorsive non sono altro che una traduzione delle versioni iterative

Espressività

● D'altro canto, in alcuni problemi la ricorsione offre soluzioni più semplici o più efficienti

● Ad esempio la visita di un albero binario si scrive in poche righe di codice ricorsivo, invece una soluzione iterativa sarebbe decisamente più complicata e lunga

● Si noti che tra i migliori algoritmi di ordinamento vi sono quelli ricorsivi (Quicksort, Mergesort)

Espressività

● In conclusione possiamo dire che la maggior parte dei problemi sono “iterativi”, cioè si risolvono in modo più intuitivo con funzioni non ricorsive

● Esistono però dei problemi “inerentemente ricorsivi”, le cui soluzioni più semplici sono ricorsive

● Esistono inoltre linguaggi puramente ricorsivi (Prolog, Lisp, OCaML, ecc.), in cui è obbligatorio usare la ricorsione

Costo della ricorsione

● Per concludere il confronto tra iterazione e ricorsione bisogna sottolineare il fatto che la ricorsione ha un suo costo “di utilizzo” dovuto alle operazioni aggiuntive di gestione delle chiamate ricorsive

● Infatti ad ogni chiamata ricorsiva deve essere creato un nuovo record di attivazione sullo stack

● Tale record sarà poi eliminato alla fine della chiamata

Costo della ricorsione

● Poiché nell'iterazione non accade niente del genere, su molti algoritmi una versione ricorsiva è un po' più lenta di una versione iterativa

● Inoltre i record di attivazione occupano memoria, adducendo anche costi in termini di memoria utilizzata

● Esistono tecniche implementative della ricorsione (ricorsione in coda) che evitano, quando è possibile, tali costi aggiuntivi