Using Memoization Instead of Recursion

# Purpose:     Compares the use of traditional recusrsion vs using glopal memoization to compute Fib numbers.
# Notes:       Recursion touches each layer mulptiple times and uses more resources. Memoization method touches each layer once and uses fewer reources.
# References:   Sec. 5.8, p.156; Data Structures and Algorithms with Python, By Kent D. Lee, Steve Hubbard
#               https://books.google.com.mx/books?id=jnEoBgAAQBAJ&pg=PA157&lpg=PA157&dq=The+complexity+of+the+fib+function+is+O%282n%29.&source=bl&ots=5VdnNdvd8r&sig=_RYXMa6kRqNApO6FSXIBiYsRjSw&hl=en&sa=X&ei=uv07VZrnF8HWsAWytYCADw&ved=0CDEQ6AEwAw#v=onepage&q=The complexity of the fib function is O%282n%29.&f=false

    # Imports #
from __future__ import print_function
import sys
    # Main #
def main():
        # Main Code
# Default DEBUG Print Option
    global v_Debug
    v_Debug = 1

    global v_Count
    v_Count = 0

    try:
        v_Num = int(raw_input("Enter a number to computer, or ENTER for default 30\nTradditonal Fib. will default to 30 on vals over 30") or 30) ##
    except KeyboardInterrupt:
        print("Cancelled".format())
        sys.exit()

    v_Num2 = v_Num ## Creates a copy of v_Num for use in  O(2n) Fib(n) function
    if v_Num > 30: v_Num2 = 30 ## Keeps this function low to prevent crash.
    print("With Recursion")
    print("Fib({}): {}".format(v_Num2, f_Commify(f_Fib(v_Num2)))) ## Computes the nth. Fibonacci number with recursion
    if v_Debug == 1: print("DEBUG - Call Count for Fib({}) is: {}".format(v_Num2, f_Commify(v_Count))) # DEBUG
    print()

    global memo
    memo = {}
    v_Count = 0
    print("With Memorization")
    print("FibM({}): {}".format(v_Num, f_Commify(f_FibM(v_Num)))) ## Computes the nth. Fibonacci number with memoization
    if v_Debug == 1: print("DEBUG - Call Count for FibM({}) is: {}".format(v_Num, f_Commify(v_Count))) # DEBUG

#-----------Basement------------

    # Functions #
        # Normal Functions
def f_Fib(n):
    """Computer Fibonacci numbers using recursion
    The weakness is that each layer requires the computation of the layer before
    it multiple times, growin exponentially as the target number grows in size.
    The complexity of the fib function is O(2n). A function with exponential complexity
    is worthless except for very small values of n."""
    global v_Count # DEBUG - Tracks call counts for testing/comparison
    v_Count = v_Count + 1 # DEBUG - Tracks call counts for testing/comparison

    if n == 0:
        return 0
    if n == 1:
        return 1
    return f_Fib(n - 1) + f_Fib(n -2)

def f_FibM(n):
    """Computer Fibonacci numbers using recursion and stores values internally to a "memo" variable
    The memoized fib function in Sect. 5.8.1 records any value returned by the function
    in its memo. The memo variable is accessed from the enclosing scope. The memo
    is not created locally because we want it to persist from one call of fib to the next.
    Each time fib is called with a new value of n the answer is recorded in the memo.
    The result: the memoized fib function now has O(n) complexity and it can compute fib(100) almost instantly.
    Without memoization, it would take 1,146,295,688,027,634,168,201 calls to the fib function to compute fib(100). With memoization it is 199."""
    global v_Count # DEBUG - Tracks call counts for testing/comparison
    v_Count = v_Count + 1 # DEBUG - Tracks call counts for testing/comparison

    if n in memo:
        return memo[n]
    if n == 0:
        memo[0] = 0
        return 0
    if n == 1:
        memo[1] = 1
        return 1
    val = f_FibM(n - 1) + f_FibM(n - 2)
    memo[n] = val
    return val

def f_Commify(v_Num):
    """Desc.: Add commas to an integer `v_Num`. >>> f_Commify(1) '1', >>> f_Commify(123) 123', >>> f_Commify(1234) '1,234'
        >>> f_Commify(1234567890) '1,234,567,890', >>> f_Commify(123.0) '123.0', >>> f_Commify(1234.5) '1,234.5'
        >>> f_Commify(1234.56789) '1,234.56789', >>> f_Commify('%.2f' % 1234.5) '1,234.50', >>> f_Commify(None) >>>
        Syntax: int or float(v_Num); Returns: str(v_Out)
        Test: print f_Commify(1000000.00)
    """
    if v_Num is None: return None
    v_Num = str(v_Num)
    if '.' in v_Num:
        v_Dollars, v_Cents = v_Num.split('.')
    else:
        v_Dollars, v_Cents = v_Num, None

    v_Holder = []
    for i, c in enumerate(str(v_Dollars)[::-1]):
        if i and (not (i % 3)):
            v_Holder.insert(0, ',')
        v_Holder.insert(0, c)
    v_Out = ''.join(v_Holder)
    if v_Cents:
        v_Out += '.' + v_Cents
    return v_Out
    # Main Loop #
if __name__ == '__main__':
    main()