Seconda parte degli appunti delle lezioni del corso di Programmazione I con laboratorio (A.A. 2011/12)

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 è

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

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

Istruzione print

● Scrive uno o più dati sullo schermo

print 1+1 print a*b

print 'Ciao, mondo !' print a+1,' ',b

print 4,

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*altezza

Chiamata di funzione

E' possibile richiamare la funzione >>> area_rettangolo() inserisci la base 5 inserisci l'altezza 4 L'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**2 return math.sqrt(somma_quad)

● L'istruzione return indica quant'è il risultato

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 a

m 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

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

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

● Sintassi if C: S1 else: 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,

Semantica

● E' equivalente all'istruzione “Se” del nostro

pseudo-codice

Esempio

● per calcolare il massimo tra due numeri

def massimo(a,b): if a>b: m=a else: m=b return 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=a else: 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 b m=massimo(m1,c)

return m

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:

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 a

if C:

S

else:

pass

Semantica

Esempio

● Vediamo un diverso modo di calcolare il

massimo tra 3 numeri def massimo3(a,b,c):

m=a if b>m:

m=b

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

m=c return m

Esempio

● Analogamente per 4 numeri

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

Esempio

● Risolviamo un'equazione di II grado discutendo il

delta def eq2grado(a,b,c): delta=b**2-4*a*c if 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<0

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

Sintassi di If-elif-else

● La sintassi è if C1: S1 elif C2: S2 elif C3: S3 … elif Cn: Sn else: S0 C1,C2,...,Cn condizioni S1,S2,...,Sn,S0 sequenze di istruzioni nota: unica if

una o più elif

unica 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

Esempio

● La soluzione dell'equazione di II grado diventa def eq2grado(a,b,c): delta=b**2-4*a*c if 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

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=30 elif m==28: ngiorni=28 else: ngiorni=31 return 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)

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)

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

● …

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)

Semantica

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=0 for i in range(1,n+1): somma=somma+i return 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)

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=0 for i in range(1,n+1): somma=somma+i**2 return 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=0 for 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

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

Esempio

def massimo_numeri(n): dato=input('inserisci un numero') mass=dato for i in range(1,n): dato=input('inserisci un numero') if dato>mass: mass=dato return mass

● range(1,n) perché si devono leggere n-1 dati (il

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=1

for i in range(1,n+1): prodotto=prodotto*i return 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



n k



=

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=1 for h in range(n-k+1,n+1): prodotto=prodotto*h cb=prodotto/fattoriale(k) return cb



n k



= ∏ h=n− k1 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

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

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

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

Istruzione while

● Sintassi

while 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

Semantica del while

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

Versione migliorata

def euclide_veloce(a,b): while b!=0: resto=a%b a=b b=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

Esempio

def somma_numeri(): somma=0

msg='inserisci un numero (0 per terminare)' dato=input(msg)

while dato!=0:

somma=somma+dato dato=input(msg)

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

1

2



r 

a r



Esempio

def radice_approx(a): r=a r_old=0 while abs(r-r_old)>=0.0001: r_old=r r=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

Esempio

def primo(n):

trovato=False d=2

while d<n and not trovato: if n%d==0:

trovato=True else:

d=d+1

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

Esempio

def somma_cifre(n): somma=0 while n!=0: resto=n%10 somma=somma+resto n=n/10 return somma

for e while

● Il ciclo for I in range(A,B): S corrisponde a I=A while I<B: S I=I+1

● In generale l'iterazione limitata è un caso

particolare di quella non limitata

● Non vale il viceversa: esistono casi in cui il

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

Esempio

def primo(n): trovato=False for d in range(2,n): if n%d==0: trovato=True break

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

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

Esempio

def somma_sequenza(A): n=len(A) somma=0 for 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,

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

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)

Seconda versione

def quadrato(A): n=len(A) B=[ None ] * n for i in range(0,n): B[i]=A[i]**2 return 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

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

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

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

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

● 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,

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

classe Persona

class Persona: def __init__(self): self.cognome=None self.nome=None self.eta=None self.sesso=None

● In pratica la “funzione” init serve a indicare quali

campi formano la classe Persona (cognome, nome, eta e sesso) attribuendo il valore

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

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=None self.mese=None self.anno=None

Strutture annidate

● Poi in Persona usare la data di nascita anziché

l'età class Persona: def __init__(self): self.nome=None self.cognome=None self.data_nascita=None self.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.giorno 4

● Mentre per modificare l'anno

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

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 >>> b 10 >>> a=11 >>> b 10 >>> 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

Riferimenti

● Quello che accade è che sia p che q si

riferiscono alla stessa persona

p q cognome Rossi nome eta sesso

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)

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

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

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

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 ] * n for 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,

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=3 y=7+n z=8 r=funzione2(x-1,y+1) return r+z def funzione2(a,b): x=a+b-1 z=b-2

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

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

Esempio

def scambia(x,y): temp=x x=y y=temp print x,y >>> a=1 >>> b=2 >>> scambia(a,b) 2 1 >>> a 1 >>> b 2

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

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=None self.y=None def trasla(p): p.x=p.x+1 p.y=p.y+1

p deve essere un punto, la funzione trasla il punto di un'unità in tutte e due le dimensioni

Esempio con le strutture

>>> P=punto() >>> P.x=19 >>> P.y=8 >>> trasla(P) >>> P.x 20 >>> P.y 9

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

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 tipo

TypeError: F( ) takes exactly M argument (N given)

● Ad esempio si ottiene questo errore chiamando

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

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

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

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

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

Esempio

def funzione1(a,b): x=a+1 y=b+2 for i in range(1,5): x=x+a return x-y def funzione2(c): n=0 while 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 esempio def funzione(x,y): global a,c a=a+2 ... funzione può accedere e modificare le variabili globali a e c

Esempio

>>> a=10 >>> b=2 >>> c=3 >>> funzione(0,1) >>> a 12 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

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

Esempio

● Vogliamo calcolare il fattoriale di un numero

naturale n

● n! è uguale al prodotto di tutti i numeri naturali

compresi tra 1 e n n!= 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

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=1 else: 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 fattoriale1) 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

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

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=?

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

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

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

Fine della ricorsione

● A questo punto fattoriale(4) è fatta ripartire ● ric vale 6

● ris vale n*ric=4∙6=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 fattoriale

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

return 1 else:

return n*fattoriale(n-1)

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

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 terminante def fattoriale(n):

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

return 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 ricorsiva

xn_{=x∙ x}n-1 _{per n>0}

● Caso base

xn_{=1 per n=0}

● La validità della legge ricorsiva e del caso base

Esempio

def potenza(x,n): if n==0: ris=1.0 else: 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= x2 n 2 xn=x⋅ x2 n−1 2

Esempio

def potenza_veloce(x,n): if n==0: ris=1 elif 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 log

2n chiamate

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

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

x2

n

2

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