Recursion vs iteration

A recent tutorial for the students was about the differece between recursion and iteration.
The most effective way to explain it was the following:

  • iteration requires a set of values, and you perform the same operations on each of them until you are done
  • recursion implies an operation on an input, that has a result depending on the same operation on smaller inputs up to a very simple one (like zero or one) with an easy answer

The classic example for recursion is the computation of a factorial. The factorial of a number n, denoted by n!,  is the product of all the numbers up to n. So 3! = 1 x 2 x 3, 5! = 1 x 2 x 3 x 4 x 5.

It is easy to implement recursively in Python as:

def fact(n):
    if n==1:
       return 1
    else:
       return n*fact(n-1)

As you can see, we have the simple input when n equals to 1, otherwise the value depends on a smaller input (n-1).

If you can write a recursive function for a task, you can also write an iterative version of the same task.

def fact(n):
    result = 1
    for i in range(1,n+1):
        result = result * i
    return result

The iterative version requires a variable to store intermediate results.

A more complex example is the binary search. The input for binary search is a sorted list of elements, for example numbers. It is faster to find the presence of a value in the list using the following approach:

  1. look at the middle element
  2. if it is equal to the one we are looking for, we are done
  3. if it is greater, then our number should be in the lower half of the list
  4. if it is lesser, then our number should be in the upper half of the list
  5. repeat from step 1 for the appropriate half

In this case, the recursive version is straghtforward too:

def binary_search(l,n):
    #l is the list, n is the element to be found
    if len(l)>0:
       mid = len(l)/2
       if l[mid]==n:
          return True
       elif l[mid]>n:
          return binary_search(l[:mid],n)
       elif l[mid]<n:
          return binary_search(l[mid+1:],n)
    else: #empty list
       return False

However, if we also want the position of the element, we need few more parameters:

def binary_search(l,n,low,high):
    if high<low:
       return None
    else:
       mid = (high-low)/2+low
       if l[mid]==n:
          return mid
       elif l[mid]>n:
          return binary_search(l,n,low,mid-1)
       elif l[mid]<n:
          return binary_search(l,n,mid+1,high)

To create an iterative version of this, a while loop is required:

def binary_search(l,n,low,high):
    while low<=high:
        mid = (high-low)/2+low
        if l[mid]==n:
          return mid
        elif l[mid]>n:
          high = mid-1
        elif l[mid]<n:
          low = mid+1
    return None

In this last case, there is not a clear list of inputs, like in the factorial example, but we have an exit condition similar to the one used by recursion.

Di umani, regole e inutilità delle stesse

Leggo acidi commenti ad articoli su giornali e post di assessori al trasporto. Il ciclista si lamenta del poco spazio, il pedone si lamenta del ciclista sotto il portico, la zdaura in generale dice che i ciclisti fanno quello che vogliono e nessuno gli dice niente.

Io ho preso la patente a 30 anni, per poter essere d’aiuto in caso di emergenza e non per necessità. Ho vissuto 12 anni benissimo senza guidare e sto molto meglio quando non sono in macchina. Non che quando prendo la bicicletta per fare il percorso casa-lavoro e viceversa le cose vadano meglio.

Questo perché il numero di persone che ignora, è con la testa fra le nuvole o se ne frega delle regole del codice della strada è immane. Se sono a piedi, trovo il ciclista sotto il portico (ha un pista ciclabile a mezzo metro di distanza); se sono in bici trovo il pedone sulla ciclabile (larga un metro, quando lui avrebbe 4 metri di portico entro cui poter anche ballare) oppure il tipico SUV parcheggiato per metà nel parcheggio motorini e per metà sulla ciclabile rialzata. Lasciamo stare quando sono in macchina: no, se devo dare la precedenza a una fila di 20 auto, non posso svoltare nella corsia preferenziale solo perché lei, cara signora con la 500L o la mini cooper ha fretta. No, caro tassista, se il giovane cinese è sulle strisce e sta attraversando con un carrello pieno di mercanzia, io mi fermo e lo lascio passare.

Perché sei poco sveglio, non sei abbastanza aggressivo, sei un vecchio col cappello, diranno i miei piccoli lettori. No, perché il codice della strada prevede questo. Se devo dare la precedenza, do la precedenza, che sia 1 automobile o 20 bus di turisti portoghesi. Se la pista ciclabile è per le biciclette, non mi fermo lì in mezzo mentre aspetto che scatti il verde pedonale. Voi aspettate che scatti il verde stando fermi in mezzo alla strada? Se quella strada dice “divieto d’accesso”, non ci entro con la bicicletta, perché chi la percorre non si aspetta un matto che gli sbuchi davanti all’improvviso. Se la pista ciclabile è fatta per permettermi di percorrere in senso inverso un senso unico, tu caro collega ciclista ti piazzi su strada, visto che segui il flusso delle auto, e non prendi la ciclabile in una direzione opposta a quella indicata da frecce e disegnini vari.

E no, non leghi la bici al palo lasciandola di traverso in mezzo alla ciclabile, come il caro NCC non dovrebbe parcheggiare nel mezzo della ciclabile di fronte alla stazione perché il parcheggio a lui dedicato “è pieno”.

La lamentazione tipica della zdaura sul corriere o sulla pagina facebook dell’assessore è che nessuno multa il ciclista. Io non vedo multare nessuno, né pedone, né ciclista né automobilista. Gente al cellulare mentre guida, mentre pedala e mentre attraversa guardandosi i piedi non viene multata. Automobili parcheggiare in divieto di sosta tutti i giorni tutto il giorno, lasciate lì invece di essere portate via per sanare il bilancio del comune.

Ora, a cosa servono le leggi e il codice della strada? Ad avere una convivenza civile, con regole condivise, in cui l’utente della strada sa cosa aspettarsi dagli altri: se loro hanno rosso stanno fermi, se sto camminando sul marciapiede l’audi non mi mette sotto, se pedalo non mi tagliano la strada sorpassandomi per svoltare a destra.

Chi lo fa? Se le regole non sono seguite, ci sono sanzioni? Le sanzioni sono adeguate? Sono efficaci nello scoraggiare comportamenti impropri?

Altrimenti, chiedetevi perché non vedete gente che cammina a piedi in mezzo all’autostrada. Lì la sanzione c’è, e scoraggia: entro 10 secondi sei morto, o è morto quello che ti ha schivato. Forse montando dei rostri alla Ben Hur sulle biciclette le piste ciclabili sarebbero libere da pedoni e automobili; lanciando bastoni nei raggi delle biciclette sotto i portici si limiterebbe il numero di pedoni investiti; e il tamarro blindato del sindaco di Vilnius sarebbe un ottimo deterrente contro gli automobilisti indisciplinati.

Dipende cosa preferite, se avere regole che vi tengono al sicuro, ma che dovete seguire, o avere la prepotenza, e lì dipende quanto siete grossi e veloci. Non potete fare i prepotenti e i furbi a cui le regole non si applicano, e poi invocare quelle stesse regole come scudo.

 

Switching dictionary keys and values in Python

Yesterday a student asked how could he may swap a dictionary so that keys become values and values keys.

One naive solution may be something like that:

new_dict = dict([(value,key) for key,value in old_dict.items()])

However, this solution has a major drawback: keys are guaranteed to be unique, while values may not. Given the fact that old_dict.items() returns a list of dictionary (key,value) elements in an arbitrary order, the last key having a specific value will be the final value in the new_dict. Example:

>>> old_dict = {12:1,76:3,23:1,3:3}
>>> old_dict.items()
dict_items([(76, 3), (3, 3), (12, 1), (23, 1)])
>>> new_dict = dict([(value,key) for key,value in old_dict.items()])
>>> new_dict
{1: 23, 3: 3}

Notice that (3,3) and (23,1) are the (key,value) pairs used to build he new dictionary.

Maybe the intended result is to have a (value,[key1,key2,..]) element for each value. This can be achieved using a for loop like:

for key,value in old_dict.items():
   if value in new_dict:
       new_dict[value].append(key)
   else:
       new_dict[value]=[key]

or by using a comprehension like:

new_dict = dict([(value, [key for key,v in old_dict.items() if v==value]) for value in set(old_dict.values())])

which gives {1: [12, 23], 3: [76, 3]} as result.

The latter example loops through the dictionary N times, where N is the number of distinct values, while the former performs just one loop.

Retrieving Python dictionary values in order

Complex data in Python may be represented by lists or dictionaries, and sometimes it may be helpful to sort it.

While sorting a list is quite straightforward using

l.sort()

or, if you have a list of lists/tuples and you prefer to sort on a specific value of them:

# sorts using the second value in the element
# example list with name,age,city
l=[['Alice',34,'Berlin'],
   ['Bob',29,'London'],
   ['Carol',30,'Rome']]
l.sort(key=lambda x: x[1])
# l is now sorted by age

Dicationaries are a different thing. Suppose that you have a dictionary mapping students to their grades, like:

grades = { 'Bruce': 100,
           'Diana': 98,
           'Barbara': 78,
           'Clark': 23}

If you print the content of the dictionary it may not appear in sorted order or even using the order in which you specified the keys:

for name in grades:
	print(name,grades[name])

on my machine I get:

Bruce 100
Clark 23
Diana 98
Barbara 78

If you want to get the list sorted by names, you should first sort the keys:

names = list(grades.keys())
names.sort()
for name in names:
	print(name,grades[name])

But what about sorting by values? (I.e. sorting by grades instead of names)

By using the previously shown key parameter of the sort method, you can convert the dictionary to a list of tuples, sort it using the second element of the tuple and then you get the result:

#convert dictionary into list
l = [(x,y) for (x,y) in grades.iteritems()]
l.sort(key=lambda x: x[1])

Then iterating through the list you should get:

Clark 23
Barbara 78
Diana 98
Bruce 100

Reading a FASTA file with Python

Since one of my tutoring duties is related to basic programming tasks for bioinformatics, I’m starting from there.

A good starting point is the exercise “Build a dictionary containing sequences from a FASTA file”.

The FASTA file format is a text based representation of a biological sequences. A FASTA file contains one or multiple entries: each entry consists of an header like, starting with the character > (greater than), and a set of lines (each up to 60 characters long) containing the sequence.

Of course you can use one of the already made libraries for the task: Bio.SeqIO.to_dict() or a loop using other methods from BioPython may be faster. However, this exercise is perfect in teaching how to think like a computer scientist.

First, the problem must be solved without using code: if you don’t know how to solve a problem, you can’t write a program that performs the solution.

In general, the FASTA file contains multiple entries, so we need a way to track the current entry name. We must distinguish the header from the sequence content.

Building from the inside-out:

#distinguish header from sequence
if line[0]=='>': #or line.startswith('>')
    #it is the header
else:
    #it is sequence

In the first case, we need to store the new sequence name and create its entry in the dictionary:

#distinguish header from sequence
if line[0]=='>': #or line.startswith('>')
    #it is the header
    name = line[1:] #discarding the initial >
    seqs[name] = ''
else:
    #it is sequence

We wrap everything inside a for loop, i.e. we are reading one line at the time:

for line in f:
    #let's discard the newline (if any)
    line = line.rstrip()
    #distinguish header from sequence
    if line[0]=='>': #or line.startswith('>')
        #it is the header
        name = line[1:] #discarding the initial >
        seqs[name] = ''
    else:
        #it is sequence

Now we have different ways to manage the sequence:

  1. build a string and update the dictionary when a new header or the end of file is found
  2. update the dictionary entry belonging to the current name

In the first case:

name = None
s = ''
for line in f:
    #let's discard the newline at the end (if any)
    line = line.rstrip()
    #distinguish header from sequence
    if line[0]=='>': #or line.startswith('>')
        #it is the header
        #if this is not the first sequence (i.e. we already read one)
        if name:
            seqs[name]=s
        name = line[1:] #discarding the initial >
        seqs[name] = ''
        s = ''
    else:
        #it is sequence
        s = s + line
#we must keep in mind the last entry: it was not saved
#since we didn't find a new header
if name: #just checking against an empty file
   seqs[name]=s

In the second approach:

name = None
for line in f:
    #let's discard the newline at the end (if any)
    line = line.rstrip()
    #distinguish header from sequence
    if line[0]=='>': #or line.startswith('>')
        #it is the header
        name = line[1:] #discarding the initial >
        seqs[name] = ''
    else:
        #it is sequence
        seqs[name] = seqs[name] + line

F can be a file object from open() or a list of lines from readlines() (I discourage the second one).

Back in business

I’m going to try to revamp this blog a bit, mostly on its core business: programming and technical stuff.

Since I’m tutoring in a couple of programming classes, I think that starting with some simple examples may be useful. Then, we will see.

Also, I’m planning to implement some algorithms that are dangling on my drive since last summer, I’ll keep you posted.

Le compagnie telefoniche e l’inutilità della privacy

Un anno e mezzo fa ho sottoscritto un contratto telefonico+ADSL con la compagnia telefonica X: la linea era nuova e nessuno aveva quel numero. Contestualmente al contratto, ho inviato un modulo (fornito da X), in cui indicavo come non volessi essere inserito nell’elenco telefonico pubblico.

Dopo 2 giorni la compagnia telefonica Y ha iniziato a chiamare offrendo varie promozioni. Ho contattato la compagnia X e il garante della privacy: entrambi mi suggerivano di iscrivermi al registro delle opposizioni.

Peccato che il registro delle opposizioni funzioni solo per le numerazioni presenti in elenco, e quindi non sia stato possibile completare la registrazione.

Apparentemente (ma devo ritrovare l’origine dell’informazione), esiste un elenco accessibile alle sole compagnie telefoniche al fine di garantire la concorrenza.

Vista la quantità abnorme di telefonate ricevute, ho riprovato a inserire il numero nel registro delle opposizioni (è passato ormai un anno dall’ultima volta). Nonostante alcuni problemi di browser, la cosa ha funzionato. Sono passati 17 giorni dall’iscrizione, il garante per la privacy dice di dare 15 giorni ai vari personaggi per recepire la cosa.

Ovviamente oggi ha chiamato la compagnia Z per offrire questo e quello.

Visto che la legge difende solo i rompicoglioni, e visto che le poste offrono un comodo sistema di invio di raccomandate tramite il sito, da oggi il rompicoglioni sono io.

Di certo, Rodotà, i suoi “discendenti” come garanti e i vari parlamentari hanno fatto un ottimo lavoro, nel passare dal selvaggio west, all’opt-in all’opt-out.