Python Coding challenge - Day 520| What is the output of the following Python Code?

 

Code Explanation:

Function Definition

def catalan(n):

This defines a recursive function named catalan that computes the nth Catalan number.

Base Case: Return 1 for n = 0 or n = 1

\    if n <= 1:

        return 1

This handles the base cases of the recursion.

By definition, Catalan(0) = 1 and Catalan(1) = 1.

If n is 0 or 1, the function immediately returns 1 without further recursion.

Initialize Result

    res = 0

Initializes a variable res to accumulate the total sum.

This variable will store the result of the recursive sum for Catalan(n).

Recursive Loop Over All Possible Partitions

    for i in range(n):

This loop runs from i = 0 to i = n-1.

Recursive Calls for Subproblems

        res += catalan(i) * catalan(n - i - 1)

This is the heart of the recursion.

For each i, the function recursively calculates:

catalan(i) – representing the number of structures in the left subtree.

catalan(n - i - 1) – representing the number of structures in the right subtree.

The product of the two is added to res.

Return Final Computed Result

    return res

After the loop finishes, the total value of res contains Catalan(n).

This value is returned.

Function Call and Output

print(catalan(4))

This line calls the function with n = 4.

It prints the result of catalan(4).

Final Output

14

As calculated, Catalan(4) = 14.