Using Memoization Instead of Recursion

BustACode 0 Tallied Votes 1K Views Share

When recursion won't do, then memoizaton will.

# 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()
rubberman 1,355 Nearly a Posting Virtuoso Featured Poster

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 Master Poster

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,
to get advice about style and other way to solve it.

The author of lru_cache Raymond Hettinger,
had a whole talk about PEP-8 in this year PyCon.
Raymond Hettinger - Beyond PEP 8 -- Best practices for beautiful intelligible code -

Gribouillis commented: great +14
vegaseat 1,735 DaniWeb's Hypocrite Team Colleague
vegaseat 1,735 DaniWeb's Hypocrite Team Colleague

You still do recursion, it's just more efficient in some cases.

BustACode commented: The idea is to use recursion, but when it won't work properly, to use memoization, as in the demo provided. +0
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.