When recursion won't do, then memoizaton will.

923 Views

Science and Math Researcher (For Fun)

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

# 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()``````
rubberman 1,355

So, do you have a problem, or are just showing off? :-) Sorry, couldn't help myself!

For some problems, recursion is simple and elegant. There are classes of problem where recursion is the only reasonable approach. Once upon a time, I found that a compiler (mainstream commercial C++ compiler for realtime as well as other systems) wasn't handling exceptions properly. I wrote a fibonacci routine (recursive) using exceptions to illustrate the problem. Properly compliant compilers handled it correctly, but the compiler in question didn't. I submitted the code to the vendor, and they had it fixed within a couple of days.

FWIW, recursive fibonacci don't dig that deep into the stack, and perform perfectly adequately. Using non-recursive algorithms for this is fine, but probably more trouble than it's worth. Using non-recursive algorithms for extracting the prime factors for really big numbers is a situation where recursion is, in my experience, the only viable approach. I won't get into that algorithm right now except to say that you use a Sieve of Aristhostenes to build an array of primes of say 10K elements. Using recursion allowed me on an old 8086/8087 PC with only 512K of RAM to factorize any number up to that expressible by a double precision floating point number. I would have extended it for arbitrary length numbers, but didn't have the time. It was part of my personal research into public key encryption and Goedel numbers. FWIW, extracting the prime factors for these big numbers took less than 1 second. The code was written in C as C++ didn't yet exist.

snippsat 661

You have been told before to before to watch your coding style.
Stop using `global`.

There is a also build module that solve this in Python 3.

``````from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
``````

Test all computation are instantly.

``````>>> fib(100)
354224848179261915075
>>> fib(500)    139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
>>> fib(700)    87470814955752846203978413017571327342367240967697381074230432592527501911290377655628227150878427331693193369109193672330777527943718169105124275
``````

Maybe post it as question first before making a Code snippets,

The author of `lru_cache` Raymond Hettinger,