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

Answer 1

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 

Answer 2

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)

Answer 3

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:

1
1
2
5
14
42
132
429
1430
4862