3
\$\begingroup\$
def T(n):
  if n <= 0:
    return 1
  else:
    return T(n-1) + (n-1) * T(n-2)
    
print T(4)

I need an effective way to print out the output of the function T(n) generated using the recurrence relation above. Is there any way to make the above code more efficient?

Sample output:

10
\$\endgroup\$
8
\$\begingroup\$

If you cannot use functools.cache or functools.lru_cache and if you don't understand or want to use a decorator, as shown in another answer, here a low-tech approach to memoization. Please note that the functools approach is easier, more robust, etc. But if you are not worried about all of that and just want simple code that is radically faster than your current approach, this will work.

def T(n):
    if n not in T.cache:
        if n <= 0:
            T.cache[n] = 1
        else:
            T.cache[n] = T(n-1) + (n-1) * T(n-2)
    return T.cache[n]

# Initialize the cache.
T.cache = {}
\$\endgroup\$
14
  • 3
    \$\begingroup\$ If you change T.cache = {0: 1} you can get rid of the if :) \$\endgroup\$ – Peilonrayz Feb 20 at 19:14
  • 3
    \$\begingroup\$ @Peilonrayz Hah, good idea, although I think at least {0: 1, -1: 1} is needed. And I don't know whether the function should gracefully handle negative integers, so I'll leave those optimizations to the OP. \$\endgroup\$ – FMc Feb 20 at 19:19
  • 1
    \$\begingroup\$ @Justin Probably, but not specifically. Most things in Python, including functions, are objects. Objects can have attributes. We are just giving the T function an attribute called cache, and it's a dict that we intend to use for memoization. Regarding timing/profiling, there are many ways to do that, including using Python profiling libraries. But if you want simple, you can just do it "manually" with the time library: t0 = time.time() ; DO SOMETHING ; t1 = time.time() ; print(t1 - t0) \$\endgroup\$ – FMc Feb 20 at 19:43
  • 1
    \$\begingroup\$ @Justin Need more specifics to make those times meaningful: what did you measure? For example, your function will indeed be faster for low values of n, because it does not incur any caching costs. The big differences emerge for larger values of n; that's when the caching approach yields big benefits because the code doesn't have to repeatedly compute a result for an input it has already seen before. \$\endgroup\$ – FMc Feb 25 at 22:20
  • 1
    \$\begingroup\$ @Justin Yes, if I understand you correctly. If you aren't worried about the function handling negative numbers gracefully, you can just initialize the cache as {0: 1, -1: 1} and then drop the if-else structure entirely, as noted in the comments above. \$\endgroup\$ – FMc Feb 27 at 15:59
10
\$\begingroup\$

One more option is to not recurse at all, but to instead compute the sequence until we get the desired term. This not only avoids the original algorithm's exponential complexity; it also avoids the at least linear (in terms of counting values) memory complexity of memoization. (Recursion/memoization can also run into implementation-specific issues such as recursion depth errors or memory errors, which are not a concern with the code below.)

def T(n):
    if n<=0: return 1
    # Set a, b to T(-1), T(0)
    a, b = 1, 1
    for i in range(n):
        # Change a, b from T(i-1), T(i) to T(i), T(i+1)
        a, b = b, b+i*a
    # i=n-1 set b to T(n)
    return b
\$\endgroup\$
0
6
\$\begingroup\$

You should use an if "__name__" == __main__: guard.

From Python 3.2 you can use functools.lru_cache and from Python 3.9 you can use functools.cache to memoize the function calls, to only call T \$O(n)\$ times. Which is a fancy name for caching the input and output of the function. The way this works is by wrapping a function. Each time the decorated function is called we compare the arguments to the keys in a cache:

  • if there is a match we return the value, and
  • if there is no match we call the function to get the return value. Store the returned value in the cache and return the returned value to the caller.

Since you're using Python 2, we can make this function ourselves. We can use a closure to build a decorator function to hold the cache.

def cache(fn):
    def inner(*args):
        try:
            return CACHE[args]
        except KeyError:
            pass
        CACHE[args] = value = fn(*args)
        return value
    CACHE = {}
    return inner
@cache
def T(n):
  if n <= 0:
    return 1
  else:
    return T(n-1) + (n-1) * T(n-2)
\$\endgroup\$
8
  • \$\begingroup\$ Thanks for the answer! But I was wondering if you had something for Python 2.7... I wanted the solution to make use of only one recursive invocation of the function T. (The current one invokes the function T twice.) I'm looking for something simple and easy to understand... \$\endgroup\$ – Justin Feb 20 at 17:30
  • 1
    \$\begingroup\$ @Justin My answer above does have something for Python 2.7. Please read the part that says "Since you're using Python 2". Asking to change code from calling a function twice to only once is not part of what Code Review is about. \$\endgroup\$ – Peilonrayz Feb 20 at 17:32
  • \$\begingroup\$ Ah yes, the rest of the answer just loaded for me. I guess this works, but I would like the code to be shorter. I do not understand some of the complicated functions that Python has to offer and I was hoping for something simple and efficient. \$\endgroup\$ – Justin Feb 20 at 17:35
  • \$\begingroup\$ Also, isn't changing code from calling a function twice to only once making the code more efficient? I didn't know how to do that, so I asked it here. Is there anywhere else I could ask? \$\endgroup\$ – Justin Feb 20 at 17:36
  • 1
    \$\begingroup\$ By short, I meant concise... sorry! \$\endgroup\$ – Justin Feb 20 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.