```
# 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()
```

Recommended Articles