Расчет каталонских чисел

Question

Я пытаюсь использовать этот код для вычисления каталонского числа в Python, но он просто не работает. Как я могу это исправить?

Вот код, который у меня есть:

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

Проблема в том, что вы суммируете, вы должны умножать. Из Википедии определение таково:

Вы можете лучше использовать цикл for вместо рекурсии:

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

Редактировать 2

Я думал, что формула была неправильной, но проблема была в том, что в ней использовалось целочисленное деление и, следовательно, округленные промежуточные результаты. Решение состоит в том, чтобы использовать переменную с плавающей точкой, я делаю это путем инициализации с ans=1.0,

Answer 2

Измените строку:

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

За:

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

Вы передаете целое число в качестве аргумента функции sum(), который принимает только итеративный.

Answer 3

Кажется, это работает для меня (из вашего кода)

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)

Из:

42