recursion gotcha?

Boris Borcic bborcic at gmail.com
Sun Sep 14 11:41:17 CEST 2008


cnb wrote:
> this recursive definition of sum thrumped me, is this some sort of
> gotcha or am I just braindead today?
> and yes i know this is easy a a for x in xs acc += x or just using the
> builtin.
> 
> def suma(xs, acc=0):
> 	if len(xs) == 0:
> 		acc
> 	else:
> 		suma(xs[1:], acc+xs[0])
> 
> it returns none.

Without return statement, the only recursive solution is a lambda expr :

 >>> suma = lambda xs : xs[0]+suma(xs[1:]) if xs else 0

 >>> suma(range(101))
5050

Note that suma(xs[1:]) implies copying the remainder of xs, what in turn makes 
the time grow quadratically with the length of xs. So instead of passing a 
superfluous acc second variable, you could pass an index into the list, eg

def suma(xs,pos=0) :
     if pos>=len(xs) :
        return 0
     else :
        return xs[pos]+suma(xs,pos+1)

Cheers, BB




More information about the Python-list mailing list