Recursion

Factorial, recursively: $5! \rightarrow 5\times(4!) \rightarrow 5\times 4 \times (3!) \rightarrow 5\times 4 \times 3 \times (2!) \rightarrow 5\times 4 \times 3 \times 2 \times (1!) \rightarrow 5\times 4 \times 3 \times 2 \times 1 \times (0!) \rightarrow 5\times 4 \times 3 \times 2 \times 1 \times 1$

Summing up numbers

Iterative Version

In [3]:
def list_sum(num_list):
    the_sum = 0
    for i in num_list:
        the_sum += i
        
    return the_sum
In [4]:
list_sum([1,3,5,7,9])
Out[4]:
25

Importing rcviz

In [ ]:
from rcviz import viz, CallGraph

Recursive Version

In [13]:
cg = CallGraph()
In [14]:
@viz(cg)
def list_sum_rec(num_list):
    if len(num_list) == 1:
        # base case
        return num_list[0]
    else:
        # recursive statement
        # Two or more numbers in our num_list
        return num_list[0] + list_sum_rec(num_list[1:])
In [15]:
list_sum_rec([1,3,5,7,9])
Out[15]:
25
In [16]:
cg
callviz: Rendering in inline in Jupyter Notebook
Out[16]:
nodes=5 140719445289728 list_sum_rec([1, 3, 5, 7, 9]) ret: 25 140719448736416 list_sum_rec([3, 5, 7, 9]) ret: 24 140719445289728->140719448736416 1 (⇑4) 140719448739184 list_sum_rec([5, 7, 9]) ret: 21 140719448736416->140719448739184 2 (⇑3) 140719445290256 list_sum_rec([7, 9]) ret: 16 140719448739184->140719445290256 3 (⇑2) 140719407529168 list_sum_rec([9]) ret: 9 140719445290256->140719407529168 4 (⇑1)

Recursive Version (Better)

In [6]:
cg = CallGraph()
In [7]:
@viz(cg)
def list_sum_rec2(the_sum, num_list):
    if len(num_list) == 0:
        return the_sum
    
    return list_sum_rec2(the_sum + num_list[0], num_list[1:])
In [8]:
list_sum_rec2(0, [1,3,5,7,9])
Out[8]:
25
In [9]:
cg
callviz: Rendering in inline in Jupyter Notebook
Out[9]:
nodes=6 140719407522240 list_sum_rec2(0,[1, 3, 5, 7, 9]) ret: 25 140719450789712 list_sum_rec2(1,[3, 5, 7, 9]) ret: 25 140719407522240->140719450789712 1 (⇑5) 140719445277600 list_sum_rec2(4,[5, 7, 9]) ret: 25 140719450789712->140719445277600 2 (⇑4) 140719448733728 list_sum_rec2(9,[7, 9]) ret: 25 140719445277600->140719448733728 3 (⇑3) 140719445278528 list_sum_rec2(16,[9]) ret: 25 140719448733728->140719445278528 4 (⇑2) 140719407519024 list_sum_rec2(25,[]) ret: 25 140719445278528->140719407519024 5 (⇑1)

Recursive Version (Slighty better over the last one)

In [25]:
# `rcviz` has bugs, it won't work if you have indirect recursion
In [22]:
def helper(the_sum, num_list):
    if len(num_list) == 0:
        return the_sum
    
    return helper(the_sum + num_list[0], num_list[1:])
In [23]:
def list_sum_rec3(num_list):
    return helper(0, num_list)
In [24]:
list_sum_rec3([1,3,5,7,9])
Out[24]:
25