Factorial

Iterative Version

In [21]:
def fact(n):
    result = 1
    
    for i in range(2, n+1):
        result *= i
        
    return result
In [22]:
fact(6)
Out[22]:
720

Recursive Version

In [23]:
from rcviz import viz, CallGraph
In [24]:
cg = CallGraph()
In [25]:
@viz(cg)
def fact_rec(n):
    if n == 0:
        return 1
    else:
        return n*fact_rec(n-1)
In [26]:
fact_rec(6)
Out[26]:
720
In [27]:
cg
callviz: Rendering in inline in Jupyter Notebook
Out[27]:
nodes=7 140459856799088 fact_rec(6) ret: 720 140459880006016 fact_rec(5) ret: 120 140459856799088->140459880006016 1 (⇑6) 140459855622080 fact_rec(4) ret: 24 140459880006016->140459855622080 2 (⇑5) 140459856783824 fact_rec(3) ret: 6 140459855622080->140459856783824 3 (⇑4) 140459880009968 fact_rec(2) ret: 2 140459856783824->140459880009968 4 (⇑3) 140459876703616 fact_rec(1) ret: 1 140459880009968->140459876703616 5 (⇑2) 140459855681840 fact_rec(0) ret: 1 140459876703616->140459855681840 6 (⇑1)
In [29]:
# Iterative version, it's fast!
fact(100)
Out[29]:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
In [31]:
# Recursive version, quite slow
fact_rec(100)
Out[31]:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
In [32]:
# Recursive version, depth limits!
fact_rec(500)
Out[32]:
1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000