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

Question

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.

You don't need to "make Python understand that `x` is not supposed to be an int", you need to fix the error in your code that causes `x` to be an int. The computer isn't misunderstanding you and it isn't making problems up. — hobbs, Mar 27 '15 at 05:34

score 5 · Accepted Answer · edited May 23 '17 at 12:12

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.

score 2 · Answer 2 · answered Mar 27 '15 at 05:42

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)

score 1 · Answer 3 · answered Mar 27 '15 at 05:50

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

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

3 Answers3

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