Recursive Function in Python

A recursive function is powerful as it allows calling itself multiple times until a termination condition is fulfilled.

To illustrate, we can use a factorial calculation as an example:

4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1

so the function can be writen

def factorial(n):
print(“factorial has been called with n = ” + str(n))
if n == 1:
return 1
res = n * factorial(n-1)
print(“intermediate result for “, n, ” * factorial(” ,n-1, “): “,res)
return res

Now we apply the same principle to the index weight capping rule – “that individual security weight is capped at a threshold% and no more than two securities are at that cap. The excess weight of any capped security is redistributed proportionally among remaining securities whose weights are less than threshold%. If this redistribution leads to additional security weights exceeding threshold%, the aforementioned redistribution process is repeated iteratively until no security weight exceeds threshold%.”

file = final[ == 20170602]
sum = file[‘adj_market_cap_($Mil_USD)’].sum()
file = file.sort_values(by=’adj_market_cap_($Mil_USD)’, ascending=False)
file[‘weight’] = file[‘adj_market_cap_($Mil_USD)’]/sum

def Capping(df, threshold):
    while (df.weight > threshold).any():
        print('Greater than %s? Cap it  ') %(threshold)
        largest = float(df.weight.nlargest(1))        
        df['weight_1'] = 0
        df['weight_1'][df.weight == threshold] = threshold
        num = len(df[df.weight == largest])  
        df['weight_1'][df.weight == largest] = threshold
        dist = (largest - threshold)*num
        total = df.weight[(df.weight_1 == 0)].sum()
        df['weight_1'][df.weight_1 == 0] = df.weight + dist*(df.weight/total)
        del df['weight']
        df.rename(columns={'weight_1': 'weight'}, inplace=True) 
        return Capping(df, threshold) 

Note the key to grasp “recursive” is to differentiate it from “iterative”. For instance, the following two snippets illustrate two ways – iterative and recursive ways.

# Iterative length calculation: O(n)
def iterative_str_len(input_str):
    input_str_len = 0
    for i in range(len(input_str)):
        input_str_len += 1
    return input_str_len

# Recursive length calculation: O(n)
def recursive_str_len(input_str):
    if input_str == '':
        return 0
    return 1 + recursive_str_len(input_str[1:])

#find upper case using recursive method
input_str_1 = 'fsnc eRognesr'
def find_uppercase_iterative(input_str):
    for i in range(len(input_str)):
        if input_str[i].isupper():
            return input_str[i]
    return "no uppercase found"
def find_uppercase_recursive(input_str, idx=0):
    if input_str[idx].isupper():
        return input_str[idx]
    if idx == len(input_str) - 1:
        return "No uppercase character found"
    return find_uppercase_recursive(input_str, idx+1)        

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.