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

Advertisements

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
 
Ad

Advertisements

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
 
Ad

Advertisements


Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top