playing with recursive, linear and simple factorial runtimes

factorial_runtimes.py

 # -*- coding: utf-8 -*-

import functools
import time


def fact(n):
    if n < 2: return 1
    # this will still produce stack returns to return back.
    return n * fact(n-1)

def fact_rec(n, finale=1):
    if n < 2: return finale
    # you don't need to cache this but it still does return from deep stacks.
    return fact_rec(n-2, n*(n-1)*finale)

def fact_dp_iterative(n):
    # there are no stacks involved and it builds bottom to top linearly.
    return functools.reduce(lambda x, y: x*y, range(1,n+1))

def fact_dp_iterative_simple(n):
    # there are no stacks involved and it builds bottom to top linearly.
    prod = 1
    for i in range(1, n+1):
        prod *= i
    return prod

for fn in (fact, fact_rec, fact_dp_iterative, fact_dp_iterative_simple):
    start = time.time()
    print(fn(16))
    print(f"runtime {fn.__name__}: {round((time.time() - start) * 10**5, 2)}\n")