# Functions & Recursion

'''
FUNCTIONS

A function takes some input and produces an output.
The output is called the return value.

Functions may do other things additionally, like printing.
...Or they may not return a value.

If we define our own functions we can use them to simplify repeated tasks.

"Method" and "procedure" can be considered synonymous with "function" for most purposes.
'''

# Calculates nth Fibonacci number explicitly using Binet's formula
# (Nevermind the specifics)
def closedFib(n):
    phi = (1 + 5**0.5) / 2
    return int(round((phi**n - (1-phi)**n) / 5**0.5))

'''
RECURSION

Recursive functions call themselves.
They work by breaking a large problem into one or more smaller problems.
Eventually a small problem with an easy answer is reached--the base case.
'''
               
# Calculates all Sanskrit meters of a given length (in morae)
# Recursive (and wasteful besides), so not good for large morae counts
def meters(morae):
    # Base cases: monomoraic and bimoraic meters
    if morae == 1:
        return ['S']
    elif morae == 2:
        return ['SS', 'L']

    # Recursive case:
    else:
        # Either add on a short syllable to a meter one morae shorter...
        shorts = ['S' + meter for meter in meters(morae - 1)]

        # ...Or add on a long syllable to a meter two morae shorter
        longs = ['L' + meter for meter in meters(morae - 2)]

        '''
        The above creates a list by doing something to every item of another list.
        It is the same as:
        
        longs = []
        for meter in meters(morae - 2)
            longs = longs + ['L' + meter]
        '''

        return shorts + longs

# Calculates Fibonacci numbers by calculating Sanskrit meters
# Therefore, not good for large values of n
def metricalFib(n):
    # Fibonacci is offset, so fill in some values
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return len(meters(n-1))

'''
MEMOIZATION (advanced)

Recursive algorithms often recalculate the same value over and over again.
To avoid this waste, we can store previously calculated values.
'''
               
# Memoized version of recursion for Fibonacci numbers
# Store previous values, avoid recalculation
# Much better than basic recursion which is then better than the metrical version
memo = {0:0, 1:1}
def memoFib(n):
    if not n in memo:
        memo[n] = memoFib(n-1) + memoFib(n-2)
    return memo[n]