# recursion gotcha?

C

#### cnb

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.

def summa(xs):
if not xs:
0
else:
xs[0]+summa(xs[1:])

Traceback (most recent call last):
File "<pyshell#6>", line 1, in <module>
summa([1,2,3,4,5])
File "<pyshell#5>", line 5, in summa
xs[0]+summa(xs[1:])
File "<pyshell#5>", line 5, in summa
xs[0]+summa(xs[1:])
File "<pyshell#5>", line 5, in summa
xs[0]+summa(xs[1:])
File "<pyshell#5>", line 5, in summa
xs[0]+summa(xs[1:])
File "<pyshell#5>", line 5, in summa
xs[0]+summa(xs[1:])
TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

R

#### rs387

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

it returns none.

Yep, that's because there is no "return" statement anywhere. Python
doesn't return expressions "by default", like functional languages do,
so where you say "suma(xs[1:], acc+xs[0])" this just calls itself and
returns nothing.

Try this:

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

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

(prints 15)

Roman

M

#### Marco Bizzarri

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])

You're just missing the "return" statements?

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

Regards
Marco

M

#### Marco Bizzarri

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])

You're just missing the "return" statements?

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

Besides: you can avoid the "acc" parameter:

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

Regards
Marco

A

#### Arnaud Delobelle

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])
You're just missing the "return" statements?
def suma(xs, acc=0):
if len(xs) == 0:
return acc
else:
return suma(xs[1:], acc+xs[0])

Besides: you can avoid the "acc" parameter:

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

I think the OP tried to make it tail-recursive, which of course has no
benefit in Python. In fact it looks like a Scheme implementation of
sum translated literally to Python.

In Python this algorithm is expressed naturally as:

def suma(xs):
acc = 0
for x in xs:
acc += x
return acc

B

#### Boris Borcic

cnb said:
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