CODEWITHSUNDEEP
pythonlistfunctionrecursion
user3425706
user3425706

Reputation:

Writing recursive solutions to a list

I am trying to write a function that will return a list of the first n catalan numbers. This is what I have come up with so far.

def catalan_numbers(n):
    if n == 0:
        return 1
    else:
        n -= 1
        return int((((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan_numbers(n))

So far this provide me with a correct solution for a single index. So if I were to call catalan_numbers(4), 14 would be returned which is correct but exactly what I am seeking. I tried to fix this issue doing the following:

def catalan_numbers(n):
    catalan = [1]
    for x in range(0, n):
        catalan.append(int((((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan_numbers(n))
    return catalan

But this returns: 

RuntimeError: maximum recursion depth exceeded in comparison

Upvotes: 1

Views: 66

Answers (2)

orlp
orlp

Reputation: 117681

I would suggest iteration over recursion:

def catalan_numbers(N):
    C = [1]
    for n in range(1, N):
        C.append((4*n - 2) * C[-1] // (n + 1))
    return C

Upvotes: 0

m7mdbadawy
m7mdbadawy

Reputation: 920

the error is because you don't have a base case also check the following code instead of returning a one number it returns a list and concatenate the current n catalan number with the list for n-1

def catalan_numbers(n):
    if n == 0:
        return [1]
    else:
        n -= 1
        t = catalan_numbers(n)
        return t + [int((((2*n+2) * (2*n+1))/((n+1)*(n+2))) * t[-1])]

Upvotes: 1

Related Questions