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, Feb 09 '15 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](https://www.python.org/dev/peps/pep-0008/) - things like odd spacing and using odd capitilisation for variable names makes code hard to read. — Gareth Latty, Feb 09 '15 at 13:55
Looks like you might have an issue with infinite recursion, too. — Joel Cornett, Feb 09 '15 at 13:55
Also, you might want to look at [a generator](http://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python) for doing this kind of thing - more efficient and easier to write than building up a list like this. — Gareth Latty, Feb 09 '15 at 13:57

Kevin · Accepted Answer · 2015-02-09T13:55:56.777

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:

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. — Gareth Latty, Feb 09 '15 at 13:50
Wow, you guys are fast -- my post was corrected and answered before I could fix my post myself (or even think). Haha — Paul Eugenio, Feb 09 '15 at 13:54
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. — Paul Eugenio, Feb 09 '15 at 13:56

score 0 · Answer 2 · answered Feb 09 '15 at 13:58

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)

score 0 · Answer 3 · edited Mar 20 '15 at 20:12

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 '15 at 20:12

Artjom B.

61,146
24
125
222

answered Feb 09 '15 at 14:29

Paul Eugenio

143
7

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 – Antti Haapala -- Слава Україні Mar 20 '15 at 21:56

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

3 Answers3

Linked