Python:: "IndexError: list index out of range"

Question

I'm experimenting with a few python programming elements and trying to produce an array of Catalan Numbers in the process.

I keep getting the aforementioned error, but I can't seem to reason out why or find any enlightening sources of info.

The function calculates the next element of list C using the current element, starting with C[0]=0.

I've reduced my code to make things simpler yet still preserve the error.

from math import *

C = []
C += [0]
def ppC(n,C):  # increment list C
    print( C[n] ) # list index out of range
    C += [ C[n]*(4*n+2)/(n+2) ]
    n += 1
    ppC(n+1,C) # recursive

ppC(0,C)        # RUN

You added 1 to n twice, but only one element was added to C. — Martijn Pieters
– Martijn Pieters, Commented Feb 9, 2015 at 13:54
It's worth noting list.append(element) exists when you want to add a single element to a list, rather than doing `list += [element] (which creates an extra list). You might also want to look at the python style guide - things like odd spacing and using odd capitilisation for variable names makes code hard to read. — Gareth Latty
– Gareth Latty, Commented Feb 9, 2015 at 13:55
Looks like you might have an issue with infinite recursion, too. — Joel Cornett
– Joel Cornett, Commented Feb 9, 2015 at 13:55
Also, you might want to look at a generator for doing this kind of thing - more efficient and easier to write than building up a list like this. — Gareth Latty
– Gareth Latty, Commented Feb 9, 2015 at 13:57

Kevin · Accepted Answer · 2015-02-09 13:55:56Z

1

n += 1
ppC(n+1,C) # recursive

With these two lines, your second call to ppC will have an n value of two, which is one past the end of the array. Try only incrementing n once.

from math import *

C = []
C += [0]
def ppC(n,C):  # increment list C
    print( C[n] ) # list index out of range
    C += [ C[n]*(4*n+2)/(n+2) ]
    ppC(n+1,C) # recursive

ppC(0,C)        # RUN

You should probably also have some kind of check to determine when you should stop generating numbers, or else the function will run forever. (or rather, it will run one thousand times and crash with a "maximum recursion depth exceeded" error.) For example:

from math import *

C = []
C += [1]
def ppC(n,C):  # increment list C
    print( C[n] ) # list index out of range
    C += [ C[n]*(4*n+2)/(n+2) ]
    if len(C) > 100: 
        return
    ppC(n+1,C) # recursive

ppC(0,C)        # RUN

One more thing. Isn't the first Catalan number one and not zero?

from math import *

C = []
C += [1]
def ppC(n,C):  # increment list C
    print( C[n] ) # list index out of range
    C += [ C[n]*(4*n+2)/(n+2) ]
    if len(C) > 10: 
        return
    ppC(n+1,C) # recursive

ppC(0,C)        # RUN

Result:

edited Feb 9, 2015 at 13:55

answered Feb 9, 2015 at 13:50

Kevin

76.5k13 gold badges141 silver badges168 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Gareth Latty Over a year ago

I'm pretty sure it isn't quite that simple - he extends C with a new item before making the n+1 call, so the list is expanding.

Paul Eugenio Over a year ago

Wow, you guys are fast -- my post was corrected and answered before I could fix my post myself (or even think). Haha

Paul Eugenio Over a year ago

Thanks a bunch! That makes sense. I do have more code that prompts the user every 10 iterations, but I left it out for simplicity.

Antti Haapala · Accepted Answer · 2015-02-09 13:58:10Z

0

Catalan numbers can be produced completely iteratively, thus you could make your function into a generator:

def catalans():
    C = 1
    n = 0
    while True:
        yield C
        C = 2 * (2 * n + 1) * C // (n + 2)
        n += 1

# then to get 100 first numbers in a list, you can do
from itertools import islice
print(list(islice(catalans(), 100)))

# or print forever:
for i in catalans():
    print(i)

answered Feb 9, 2015 at 13:58

Antti Haapala

135k23 gold badges297 silver badges349 bronze badges

Comments

Artjom B. · Accepted Answer · 2015-03-20 20:12:26Z

0

Ok, it looks like what Kevin said is true -- it is hitting the recursion and incrementing a second time before the array is expanded to account for it. Also, Catalan number C[0]=1.

Here is my full (and now fully functional) code:

from math import *

C = []
C += [1]
def ppC(n,C):
    print( C[n] )
    C += [ C[n]*(4.*n+2)/(n+2) ]
    if prompt(n) == 1:
        ppC(n+1,C)

def prompt(n):
    if n%10 == 0:   
        print("continue?")
        m = raw_input("(y/n)")
        if m != "y":
            return 0
        else:
            return 1
    else:
        return 1

ppC(0,C)        # RUN

edited Mar 20, 2015 at 20:12

Artjom B.

62k26 gold badges137 silver badges236 bronze badges

answered Feb 9, 2015 at 14:29

Paul Eugenio

1458 bronze badges

1 Comment

Antti Haapala Over a year ago

Please do not make a new answer for this, just use comments and accept the best answer; this is just @Kevin's answer with a prompt functionality added in

Collectives™ on Stack Overflow

Python:: "IndexError: list index out of range"

3 Answers 3

3 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related