Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It only takes a minute to sign up.
Sign up to join this community
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
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 = {}
T.cache = {0: 1} you can get rid of the if :)
\$\endgroup\$
{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\$
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\$
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\$
{0: 1, -1: 1} and then drop the if-else structure entirely, as noted in the comments above.
\$\endgroup\$
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
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:
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)
