CODEWITHSUNDEEP
pythonpython-2.7recursion
viethaihp291
viethaihp291

Reputation: 607

'int' object has no attribute '__getitem__' (again)

I am trying to find the sum of a list recursively as follow (I know there are a simple sum() function and tons of other ways):

def rsum(x):

    if not (x):
        return 0
    else:
        sum = x[0] + rsum(x.pop(0))
        return sum

However, Python keeps telling me that x is an int and cannot have operator []. How do I fix this?

For those who think I am too lazy for asking this question here: I have looked everywhere but still have no idea how to make Python understand that x is not supposed to be an int.

Upvotes: 2

Views: 481

Answers (3)

Alexander R.
Alexander R.

Reputation: 1756

Very simple example:

def rec_sum(x, n):
    if not n:
        return x[0]
    return x[n] + rec_sum(x, n-1)

print rec_sum(x, len(x)-1)

This version more efficient then all examples posted by thefourtheye, because in Python every x[1:] generates new list. Why to do this when you can use original list? Also, there is no reason to do manipulations like .pop

Upvotes: 1

thefourtheye
thefourtheye

Reputation: 239653

x.pop(0) will remove the first item and return it. And you are passing that to rsum, which is trying to do x[0], but x is now a number. That is why it is failing.

Instead, use pop first, and the pass x to rsum like this

def rsum(x):
    if not x:
        return 0
    else:
        return x.pop() + rsum(x)

print rsum([1, 2, 3])
# 6

If you want to avoid mutating the original object, then use slicing to create new list without the first element, like this

def rsum(x):
    if not x:
        return 0
    else:
        return x[0] + rsum(x[1:])

print rsum([1, 2, 3])
# 6

Since you are learning recursion, I would like you to consider Tail Call optimization as well. You can change your function a little bit like this

def rsum(x, total):
    if not x:
        return total
    else:
        return rsum(x[1:], total + x[0])

print rsum([1, 2, 3], 0)
# 6

In earlier cases, till you hit your base condition (if not x:) the current function cannot be taken out of the memory (because x[0] or x.pop() is in the current stack and they have to added with the result of the recursive call to actually return from the current function). So, when you run this function on a very large list, it will run out of stack space. But, in the TCO version, you are returning the result of another function call. So, the current function need not have to be in memory.

Note: That said, Python doesn't support Tail Call Optimization. Read what the BDFL (Guido) has to say about this here.

Upvotes: 5

lvc
lvc

Reputation: 35089

When you have an error that doesn't seem to make sense for the value you expect an object to have, try printing it to see what value it does have:

def rsum(x):
    print(x)
    if not (x):
        return 0
    else:
        sum = x[0] + rsum(x.pop(0))
        return sum


rsum([1,2,3])

Gives this output:

[1, 2, 3]
1

So, the first time you call rsum it has a list as expected; the second time it has a number. You can play around in the interactive interpreter to figure out why:

>>> x = [1,2,3]
>>> x.pop(0)
1
>>> x
[2, 3]

So, pop modifies the list but the result of the call is the item that was removed. You can use this fact to come up with something like this:

sum = x.pop(0) + rsum(x)

Upvotes: 2

Related Questions