Calculating Catalan Numbers [closed]

Question

I am trying to use this code to calculate the Catalan Number in Python, but it just does not work. How can I fix it?

Here is the code I have:

def catalan_rec(n):
    if n == 0:
        return 1
    else:
        b = 0
        for i in range (n):
            b += sum((catalan_rec(i))*(catalan_rec(n-1-i)))
    return b

Answer 1

The problem is that you are summing, you should actually multiply. From Wikipedia the definition is:

You can better use a for loop instead of recursion:

def catnumber(n):
  ans = 1.0
  for k in range(2,n+1):
     ans = ans *(n+k)/k
  return ans

Edit 2

I thought the formula was incorrect, but the problem was in fact that it was using integer division and therefore rounded sub results. The solution is to use a float variable, I do this by initializing with ans=1.0.

Answer 2

Change the line:

b += sum((catalan_rec(i))*(catalan_rec(n-1-i)))

For:

b += (catalan_rec(i))*(catalan_rec(n-1-i))

You are passing an integer as argument to the function sum(), which only accepts an iterable.

Answer 3

This seems to work for me(from your code)

def catalan_rec(n):
    b = 0
    if n == 0:
        return 1
    else:
        for i in range (n):
            b += (catalan_rec(i))*(catalan_rec(n-1-i))
    return b

print catalan_rec(5)

Out:

42