# 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]:

### 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]:

### 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