CODEWITHSUNDEEP
pythonmultiplicationcatalan
Brenda So
Brenda So

Reputation: 201

Python does not follow order of PEMDAS?

I am programming a catalan number generator for homework, and I am doing a recursive program in pytohon.

The program:

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

print catalan(10)

returns 5832, which is the wrong answer, but

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

print catalan(10)

gives me 16796, which is the correct answer.

So does python not follow PEMDAS?

Upvotes: 1

Views: 1477

Answers (1)

alexgolec
alexgolec

Reputation: 28252

Just like PEMDAS, python evaluates expressions from left to right. It evaluates (4*n-2)/(n+1), stores it (call the result X), and then computes X/catalan(n-1).

The problem is, what is the value of X? (4*n-2)/(n+1) is not an integer for all values of n, but if you're passing in a value of n that is a python int you're performing integer division. The result is that the fractional part of the computation is discarded, and your computation goes off the rails.

The second iteration works because of a property of the catalan function is that the (4*n-2)*catalan(n-1) expression will be a multiple of n-1. This way, you leave the (potentially destructive) division to the end of the expression, and the mathematical properties of you computation save you.

Upvotes: 2

Related Questions