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]

Re: recursion gotcha?

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]

Re: recursion gotcha?

On Sun, Sep 14, 2008 at 10:01 AM, cnb <circularfunc@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]

Re: recursion gotcha?

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

On Sun, Sep 14, 2008 at 10:01 AM, cnb <circularfunc@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]

Re: recursion gotcha?

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]

Re: recursion gotcha?

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