CODEWITHSUNDEEP
python-3.xcatalan
user4411105
user4411105

Reputation:

Generating sequence of numbers with recursion python

The goal is to generate catalan numbers ! my code works up to n = 30 (i tried the same algorithm in JAVA and it's totally correct,but, then something strange happens with python , it gives wrong numbers back after n=30. I'm totally sure that there is an issue about rounding or maybe formats, but can't figure it out by myself!

def catalan(n):
if n < 0:
    return -1
else:
    if n == 0:
        return 1
    else:
        c_n = (4*n-2)/(n+1)*catalan(n-1)
    return int(c_n)

Upvotes: 1

Views: 1274

Answers (1)

trincot
trincot

Reputation: 350770

By using /(n+1) you produce a floating point number, which by its nature has a limited precision. This precision is not accurate enough for the larger numbers that appear with n > 30.

So instead, use a formula that sticks with integer numbers: first multiply and only then perform the division, an integer division:

 c_n = (4*n-2)*catalan(n-1)//(n+1)

The cast to int is then also unnecessary, and you can just do:

 return c_n

Side note: you don't need else when you return in the if part of the statement. So you can write:

def catalan(n):
    if n < 0:
        return -1
    if n == 0:
        return 1
    return (4*n-2)*catalan(n-1)//(n+1)

Upvotes: 3

Related Questions