recursion gotcha?

[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'

[rs387]

On Sep 14, 9:01*am, cnb <circularf...@y ahoo.sewrote:

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

[Marco Bizzarri]

On Sun, Sep 14, 2008 at 10:01 AM, cnb <ci**********@y ahoo.sewrote:

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
--
Marco Bizzarri
http://notenotturne.blogspot.com/
http://iliveinpisa.blogspot.com/

[Marco Bizzarri]

On Sun, Sep 14, 2008 at 10:08 AM, Marco Bizzarri
<ma************ @gmail.comwrote :

On Sun, Sep 14, 2008 at 10:01 AM, cnb <ci**********@y ahoo.sewrote:

>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
--
Marco Bizzarri
http://notenotturne.blogspot.com/
http://iliveinpisa.blogspot.com/

[Arnaud Delobelle]

On Sep 14, 9:44*am, "Marco Bizzarri" <marco.bizza... @gmail.comwrote :

On Sun, Sep 14, 2008 at 10:08 AM, Marco Bizzarri

<marco.bizza... @gmail.comwrote :

On Sun, Sep 14, 2008 at 10:01 AM, cnb <circularf...@y ahoo.sewrote:

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

--
Arnaud

[Boris Borcic]

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(10 1))

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