code
share
In the previous posts we discussed elementary function operations, in particular function composition. In this post we explore the result of repeatedly applying function composition, which results in the creation of so-called recursive functions. These sorts of functions arise throughout machine learning, from the computation of higher order derivatives to the construction of neural networks.
# imports from custom library
import sys
sys.path.append('../../')
import autograd.numpy as np
import matplotlib.pyplot as plt
from mlrefined_libraries import basics_library as baslib
%load_ext autoreload
%autoreload 2
In this Section we describe recursion, a common method of computation in which a large calculation is broken down into a nested sequences of smaller versions of the same calculation. In other words, a recursion is a function that is defined in terms of itself. This principle arises throughtout the sciences - from calculus and dynamical systems to computer science and machine learning / deep learning.
The factorial function $f$ which takes in an positive integer $n$ and returns
$$ f(n) = n! = n \times (n-1) \times (n-2) \times (n-3) \times \cdots 2 \times 1 $$is a common recursion. The first few values are
\begin{array} \ f(1) = 1 \\ f(2) = 2 \times 1 = 2 \\ f(3) = 3 \times 2 \times 1 = 6 \\ f(4) = 4 \times 3 \times 2 \times 1 = 24\\ \end{array}One can code up this function - like many recursions - as a for loop as in the next Python cell
def factorial(n):
a = 1
for i in range(n):
a = (n-i)*a
return (a)
This works just fine. We can test it out for the first few values in the next Python cell
# print out the first few values of factorial using the for-loop definition
f1 = factorial(1)
f2 = factorial(2)
f3 = factorial(3)
f4 = factorial(4)
print (f1,f2,f3,f4)
One can also define factorial recursively, i.e., in terms of a function that calls itself, as shown in the next Python cell
# define the factorial function recursively
def factorial(n):
if n > 1:
return n*factorial(n-1)
else:
return 1
Here the 'if n > 1' branch of the factorial definition defines the recursion, calling the function itself. To see why this defines the factorial follow this branch for several steps with a given input value for $n$, say $n = 4$.
Given the stated logic the definition returns a call to itself 4*factorial(3). In other words
factorial(4) = 4*factorial(3)Now in the next call to factorial here factorial(3) the input $3$ being greater than $1$ will also trigger the 'n > 1' branch, and will return 3*factorial(2). In other words
factorial(3) = 3*factorial(2)Continuing the call to factorial[2] returns 2*factorial[1] or
factorial(2) = 2*factorial(1)And finally the call to factorial[1] finally activates the other branch 'n <=1' and returns 1. Reverse substituting back up to factorial[3] we then can write
factorial[4] = 4*3*2*1which is correct. And this process holds more generally as well.
In the next Python cell we test this recursive form of the factorial function.
# print out the first few values of factorial using the recursive definition
f1 = factorial(1)
f2 = factorial(2)
f3 = factorial(3)
f4 = factorial(4)
print (f1,f2,f3,f4)
and all of these are indeed correct.
QuickSort is a popular recursive algorithm used for sorting a list or array of numbers. Like any other sorting algorithm, QuickSort takes in an unsorted list, e.g.,
$$a = [18,25,10,33,16,75,50,14]$$and returns its sorted version
$$a_{\text{ sorted}} = [10, 14, 16, 18, 25, 33, 50, 75]$$To see how QuickSort works, imagine for a moment that you have coded a sub-routine that takes in any list and returns as output, a shuffled version of it wherein the first element of the input list is now placed in its correct position. For example, with the list $a$ given above as input your sub-routine should return a list that has the first element of $a$ - that is $18$ - in its fourth position
$$[?, ?, ?, 18, ?, ?, ?, ?]$$At this point it is not important where other elements of the list end up! We only need to make sure that $18$ ends up in its correct post-sort position.
Two questions: (1) how difficult is it to code such a sub-routine? and (2) Having coded one, how will it help us sort the enire list?
Let's answer the first question first: notice all our sub-routine needs to do is place all elements of $a$ that are smaller (or equal to) $a[0]$ before $a[0]$, and those greater than $a[0]$ after it, as in the following list
$$\left[\begin{array}{ccc} \text{elements of }a\textbf{ smaller } \text{than or equal to }a\left[0\right], & a\left[0\right], & \text{elements of }a \textbf{ greater } \text{than }a\left[0\right]\end{array}\right]$$Take a moment to verify that the simple sub-routine below does exactly that.
def my_sub_routine (a):
return [i for i in a[1:] if i <= a[0]] + [a[0]] + [i for i in a[1:] if i > a[0]]
a = [18,25,10,33,16,75,50,14]
my_sub_routine(a)
Now to the second question: how does this help sort the entire list? Well, we know that $a[0]$ is already in its correct position. So we can focus on the sub-lists to the left and right of $a[0]$ - let's call them $b$ and $c$
$$\left[\begin{array}{ccc} b, & a\left[0\right], & c\end{array}\right]$$Applying our simple sub-routine again, this time to both $b$ and $c$, will result in a list that looks like
$$\left[\begin{array}{ccccccc} \text{all }b\left[i\right]\leq b\left[0\right], & b\left[0\right], & \text{all }b\left[i\right]>b\left[0\right], & a\left[0\right], & \text{all }c\left[i\right]\leq c\left[0\right], & c\left[0\right], & \text{all }c\left[i\right]>c\left[0\right]\end{array}\right]$$where, in addition to $a[0]$, we now have both $b[0]$ and $c[0]$ in their correct positions as well.
It should be clear by now what to do next: we recurisively apply our sub-routine to the sub-lists created on the left and right of the first element. This algorithm, like any other recursion, has to stop at some point. In this case we stop when a sub-list contains only one element in which case no further sorting is required and we can simply return that element. In the Python cell below we show the full QuickSort algorithm where we have added this stopping condition.
def QuickSort(a):
if len(a) <= 1:
return a
else:
return QuickSort([i for i in a[1:] if i <= a[0]]) + [a[0]] + QuickSort([i for i in a[1:] if i > a[0]])
QuickSort(a)
Notice how QuickSort is called recursively on the sub-lists to the left and right of $a[0]$.
A classic recursion from the study of chaos theory and dynamical systems is called the logistic sequence (this is very much related to logistic regression in machine learning). The logistic sequence is generated by repeatedly plugging the output of the equation
$$ f(x) = wx - wx^2 $$where $w$ is some value, back into itself. Writing the logistic function itself as
# logistic function
def logistic(x,w):
return w*x - w*x**2
We can define a sequence based on this function using a for loop - where we have set $w=3$ - as
# create a logistic sequence via for loop
num_elements = 70 # number of points to generate
sequence = [] # container for generated points
x = 0.0001 # our initial point
for i in range(num_elements):
x = logistic(x,w=3)
sequence.append(x)
and plot this sequence
# plot the result
plt.scatter(np.arange(len(sequence)),sequence)
plt.plot(sequence,alpha = 0.5) # plot lines connecting consecutive points for visualization purposes
plt.show()
The logistic sequence is a 'chaotic system' because slight changes to the value of $w$ and the initial point $x$ can create enormous changes in the sequence's behavior. For example, if we change the value $w$ from $3$ to $4$ and keep same initial point we generate a sequence that is almost completely random [1].
# create a logistic sequence via for loop that is almost completely random
num_elements = 70 # number of points to generate
sequence = [] # container for generated points
x = 0.0001 # our initial point
for i in range(num_elements):
x = logistic(x,w=4)
sequence.append(x)
# plot the result
plt.scatter(np.arange(len(sequence)),sequence)
plt.plot(sequence,alpha = 0.5) # plot lines connecting consecutive points for visualization purposes
plt.show()
The logistic $n^{th}$ element of the logistic sequence can also be written recurively, as shown in the next Python cell.
# define f, and compositions of f, recursively
def f(x,w,n,seq): # x = input point, n = desired number of compositions
seq.append(x)
if n > 1:
return f(w*x - w*x**2,w,n-1,seq)
else:
seq.append(w*x - w*x**2)
return seq
With the recursive definition of the logistic sequence defined we can quickly apply it using the same settings as above to get the same results.
# create the same sequences using our recursive definition of the logistic sequence
sequence1 = f(0.0001,3,70,[]); sequence2 = f(0.0001,4,70,[]);
# plot the sequences
fig = plt.figure(figsize = (15,4))
ax1 = fig.add_subplot(121); ax2 = fig.add_subplot(122);
ax1.scatter(np.arange(len(sequence1)),sequence1); ax2.scatter(np.arange(len(sequence2)),sequence2);
ax1.plot(sequence1,alpha = 0.5); ax2.plot(sequence2,alpha = 0.5); # plot lines connecting consecutive points for visualization purposes
plt.show()
In addition to the examples given here fractal geometry is another common and fun type of object defined by recursion.
In this Section we go through a number of examples of repeated function compositions, which are themselves recursive functions. We also describe repeating composition of various functions also constitutes a recursion.
Take the simple linear function
$$ f(x) = x + 1 $$and notice what happens when we repeatedly compose it iwth itself.
\begin{array} \ f(x) = x + 1 \\ f(f(x)) = f(x + 1) = (x+1) + 1 = x + 2 \\ f(f(f(x))) = f(f(x + 1)) = f((x+1) + 1) = f(x + 2) = x + 3 \\ \vdots \\ \end{array}This trend continues, with the composition of $n$ of these functionsn taking the form
$$ f(f(\cdots f(x) \cdots )) = x + n $$Because writing out the left hand side above is somewhat cumbersome, one often uses the following shorthand notation instead
$$ n\,\, \text{ compositions of } f \text{:} \,\,\, f(f(\cdots f(x) \cdots )) \iff f^{(n)}(x) $$Notice the parenthesis in the exponent here, this is here to distinguish composition from multiplication. i.e., $f^{(n)}(x)$ says to compose $f$ with itself $n$ times, not multiply $f$ by itself $n$ times.
\begin{array} \ f^{(n)}(x) = x + n \,\,\,\,\,\,\,\,\,\, \text{(composition)}\\ f^n(x) = (x + 1)^n \,\,\,\,\, \text{(multiplication)}\\ \end{array}How do we express this function and its compositions in code? There are several ways. The first is to write out the function directly as in the next Python cell.
# produce next number in sequence
def f(x):
return x + 1
In Python we can write a composition of this function fairly naturally if $n$ is small. For example, for one composition we can write $n$ times with itself we can define a for loop and sequentially compose the function with itself, as done in the next Python cell.
# one composition of the function with itself
x = 1
print (f(f(x)))
To create deeper compositions we need a for loop, for example in the next Python cell we produce the output of $n=10$ compositions of the function, evaluated at the same point.
# evaluate deeper composition of f at an input point
x = 1; n = 10;
for i in range(n):
x = f(x)
print (x)
Another common way of expressing deeper compositions is by defining the function itself recursively. A function defined recursively calls itself at some point in its definition. For example, to define $f$ so that we can control the number of compositions
# define f, and compositions of f, recursively
def f(x,n): # x = input point, n = desired number of compositions
if n > 1:
return (f(x+1,n-1))
else:
return (x + 1)
Using this recursively defined version of the function and its compositions, we can test the same settings as previous.
### test out the recursively defined composition of f
# one composition of f
x = 1; n = 2
print (f(x,n))
# 10 compositions of f
x = 1; n = 10
print (f(x,n))
Using this recursive definition of the function composition we can plot out the first 10 compositions, as in the next Python cell.
# use basic plotting device to plot recursive function
baslib.basics_plotter.recursive_plotter(f=f,n = 10)
Starting with the function
$$ f(x) = \text{sin}(x) $$we can create the recursive function $f^{(n)}(x)$ by composing this with itself $n$ times. This function we can define as in the next Python cell.
# define f(x) = sin(x) and create recursive function by composing it with itself n times
def f(x,n): # x = input point, n = desired number of compositions
if n > 1:
return (f(np.sin(x),n-1))
else:
return (np.sin(x))
We can plot the first 10 compositions via the Python function below.
# use basic plotting device to plot recursive function
x = np.linspace(-10,10,500)
baslib.basics_plotter.recursive_plotter(f=f,n = 10,x=x,legend = 'on',plot_all = True)
With the Python plotting function above we can see what happens as the number of compositions gets very large too. In the next Python cell we print out only the $1000^{th}$ composition.
# use basic plotting device to plot recursive function
x = np.linspace(-10,10,500)
baslib.basics_plotter.recursive_plotter(f=f,n = 1000,x=x,legend = 'on',plot_all = False)
Examine the vertical axis here - the scale here is incredibly small - and this function is essentially constant and eequal to zero.
For kicks we animate the transition from one composition to one hundred in the Python cell below.
# use basic plotting device to plot recursive function
x = np.linspace(-5,5,500)
baslib.basics_animators.recursive_animator(f=f,n = 100,x=x)
A composition of multiple functions is also a recursive function. For example, take the two functions
\begin{array} \ g(x) = \text{sin}(x) \\ h(x) = x^2 \\ \end{array}We can construct a recursive function by alternatingly composing these two functions toegether.
$$ f_n(x) = g(h(g(h(\cdots (x) \cdots )) $$We can recursively define the general altnerating composition of these two functions as in the next cell.
# compose two funtions to create recursive function
def f(x,n): # x = input point, n = desired number of compositions
if n > 1:
if np.mod(n,2) == 1:
return (f(x**2,n-1))
if np.mod(n,2) == 0:
return (f(np.sin(x),n-1))
else:
return (np.sin(x))
In the next Python cell we animate the first 15 alternating compositions of these two functions. In other words, we animate $f$ for $n=1...15$.
# use basic plotting device to plot recursive function
x = np.linspace(-5,5,500)
baslib.basics_animators.recursive_animator(f=f,n = 15,x=x,notation = 'subscript')
The content of this notebook is supplementary material for the textbook Machine Learning Refined (Cambridge University Press, 2016). Visit http://mlrefined.com for free chapter downloads and tutorials, and our Amazon site for details regarding a hard copy of the text.
[1] For more information on the logistic sequence and chaos theory / complex systems in general see
Feldman, David P. Chaos and fractals: an elementary introduction. Oxford University Press, 2012. APA
and David's course online which you can find here.