A recursive function to find nth catalan number - Python

[ A recursive function to find nth catalan number ]

A recursive function to find nth catalan number

def catalan(n): 
    # Base Case 
    if n <= 1: 
        return 1

    # Catalan(n) is the sum  
    # of catalan(i)*catalan(n-i-1) 
    res = 0
    for i in range(n): 
        res += catalan(i) * catalan(n-i-1) 

    return res 

# Driver Code 
for i in range(10): 
    print (catalan(i))

Disassembler

import dis
def hello1_func():
    s = 'Hello'
    return s
dis.dis(hello1_func)

example to demonstrate usage of docstring

def greet(name):
    """
    This function greets to
    the person passed in as
    a parameter
    """
    print("Hello, " + name + ". Good morning!")

Absolute function

def absolute_value(num):
    """This function returns the absolute
    value of the entered number"""

    if num >= 0:
        return num
    else:
        return -num
print(absolute_value(2))
print(absolute_value(-4))

usage of dictionary

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}
print "dict['Name']: ", dict['Name']
print "dict['Age']: ", dict['Age']

accept user input

str = input("Enter your input: ")
print ("Received input is : ", str)

A naive recursive Python implementation

def binomialCoeff(n , k): 

    if k > n : 
       return 0
    if k==0 or k ==n : 
        return 1

    # Recursive Call 
    return binomialCoeff(n-1 , k-1) + binomialCoeff(n-1 , k) 

# Driver Program to test ht above function 
n = 5
k = 2
print ("Value of C(%d,%d) is (%d)" %(n , k , binomialCoeff(n , k)) )

A naive Python implementation of LIS problem

""" To make use of recursive calls, this function must return 
 two things: 
 1) Length of LIS ending with element arr[n-1]. We use 
 max_ending_here for this purpose 
 2) Overall maximum as the LIS may end with an element 
 before arr[n-1] max_ref is used this purpose. 
 The value of LIS of full array of size n is stored in 
 *max_ref which is our final result """

# global variable to store the maximum 
global maximum 

def _lis(arr , n ): 

    # to allow the access of global variable 
    global maximum 

    # Base Case 
    if n == 1 : 
        return 1

    # maxEndingHere is the length of LIS ending with arr[n-1] 
    maxEndingHere = 1

    """Recursively get all LIS ending with arr[0], arr[1]..arr[n-2] 
       IF arr[n-1] is maller than arr[n-1], and max ending with 
       arr[n-1] needs to be updated, then update it"""
    for i in range(1, n): 
        res = _lis(arr , i) 
        if arr[i-1] < arr[n-1] and res+1 > maxEndingHere: 
            maxEndingHere = res +1

    # Compare maxEndingHere with overall maximum. And 
    # update the overall maximum if needed 
    maximum = max(maximum , maxEndingHere) 

    return maxEndingHere 

def lis(arr): 

    # to allow the access of global variable 
    global maximum 

    # lenght of arr 
    n = len(arr) 

    # maximum variable holds the result 
    maximum = 1

    # The function _lis() stores its result in maximum 
    _lis(arr , n) 

    return maximum 

# Driver program to test the above function 
arr = [10 , 22 , 9 , 33 , 21 , 50 , 41 , 60] 
n = len(arr) 
print ("Length of lis is ", lis(arr) )

Function for nth Fibonacci number

def Fibonacci(n): 
    if n<0: 
        print("Incorrect input") 
    # First Fibonacci number is 0 
    elif n==0: 
        return 0
    # Second Fibonacci number is 1 
    elif n==1: 
        return 1
    else: 
        return Fibonacci(n-1)+Fibonacci(n-2) 

# Driver Program 

print(Fibonacci(9))