Find the Factorial of a number by tabulation using decorators
def factorial(n):
if n<1:
return 1
else:
f=[0]*(n+1) #creation of the array/list#
f[0]=1 #initialization#
for i in range(1,n+1):#the loop#
f[i]=i*f[i-1] #the recursion + adding in the list#
return f[n]
Now How do i use a decorator to make this work? Following is my attempt ''' #tabulation (down to up) with decorator
import time
def tabulation(func):
def inner(*args,**kwargs):
n=str(args)+str(kwargs)
n=int(n[1])
m=[0]*(n+1)
if n not in m:
m[n]=func(*args,**kwargs)
print(m)
return(m[n])
return inner
@tabulation
def fact(n):
if n<=1:
return n
else:
return n*fact(n-1)
start=time.time()
f=fact(5)
end=time.time()
start=time.time()
g=fact(10)
end=time.time()
print(f," ",end-start)
print(g," ",end-start)
print(m)
'''
The table should be defined ouside the inner function so that it can be shared across calls. However, with the table defined outside the inner function, it can't be initialized with any items since n is not known until the inner function is called. Instead, grow the table dynamically with the list.extend method as needed:
def tabulation(func):
def inner(n):
table.extend(map(func, range(len(table), n + 1)))
return table[n]
table = []
return inner
@tabulation
def fact(n):
if n < 1:
return 1
return n * fact(n - 1)
so that:
import time
start = time.perf_counter()
f = fact(5)
end = time.perf_counter()
print(f, " ", end - start)
start = time.perf_counter()
g = fact(10)
end = time.perf_counter()
print(g, " ", end - start)
outputs:
120 8.546994649805129e-06
3628800 3.326000296510756e-06
Demo: Try it online!