Algorithms and Functions

Exercise 4.1. Two processes that you can use to multiply two nonnegative integers $a,b$ together are listed below:

Algorithm 4.1.

1. Define a new number $prod$ , and initialize it (i.e. set it equal) to 0.
2. If $\mathbf{a} = 0$ , stop, and return the number $prod$ .
3. Otherwise, add $b$ to prod, and subtract 1 from $a$ . Then go to 2.

Algorithm 4.2.

1. Define a new number $prod$ , and initialize it (i.e. set it equal) to 0.
2. If $\mathbf{a} = 0$ , stop, and return the number $prod$ .
3. Otherwise, if $a$ is odd subtract $1$ from $a$ and set $prod = prod +b$ .
4. Divide $a$ by 2, and multiply $b$ by 2.
5. Go to step 2.

In general, which of these is the faster way to multiply two numbers? Why?

Functions in General

In your high-school mathematics classes, you’ve likely seen functions described as things like ”$f(x) = 2x+3$ ” or ”$g(x) = \max(x,y)$ .” When we’re writing code, however, we don’t do this! That is: in most programming languages, you can’t just type in expressions like the ones before and trust that the computer will understand what you mean. Instead, you’ll often write something like the following:

/* function returning the max between two numbers */
int max(int num1, int num2) 
{
    /* local variable declaration */
    int result;
 
    if (num1 > num2)
        result = num1;
    else
        result = num2;
 
    return result; 
}

Notice how in this example we didn’t just get to define the rules for our function: we also had to specify the kind of inputs the function should expect, and also the type of outputs the function will generate! On one hand, this creates more work for us at the start: we can’t just tell people our rules, and we’ll often find ourselves having to go back and edit our functions as we learn what sorts of inputs we actually want to generate.

On the other hand, though, this lets us describe a much broader class of functions than what we could do before! Under our old high-school definition for a function, we just assumed that functions took in numbers and returned numbers. With the above idea, though, we can have functions take in and output anything: multiple numbers, arrays, text files, whatever!

On the third(?) hand, enforcing certain restrictions on the types of inputs and outputs to a function is also a much more secure way to think about functions in computer science. If you’re writing code in a real-life situation, you should always expect malicious or just clueless users to try to input the worst possible data to your functions. As a result, you can’t just have a function defined by the rule $f(x) = \frac{1}{x}$ and trust that your users out of the goodness of their hearts will never input 0 just to see what happens! They’ll do it immediately (as well as lots of other horrifying inputs, like 🐥, $\frac{1}{0}$ , $1-0.\overline{9}, \ldots$ ) just to see what happens.

(from https://xkcd.com/327/)

This is why many programming languages enforce type systems: i.e. rules around their functions that specifically force you to declare the kinds of inputs and outputs ahead of time, like we’ve done above! Doing this is an important part of writing bug-free and secure code.

As this is a computer science class, we should have a definition of function that matches this concept. We provide this here:

In other words, we never have a value $a$ in $A$ for which $f(a)$ is undefined,as that would cause our programs to crash! As well, we also do not allow for a value $a \in A$ to generate “multiple” outputs; i.e. we want to be able to rely on $f(a)$ not changing on us without warning, if we keep $a$ the same.

Example 4.1. Typically, to define a function we’ll write something like “Consider the function $f: \mathbb{Z} \to \mathbb{Q}$ , defined by the rule $f(n) = \frac{1}{n^2+1}$ . This definition tells you three things: what the domain is (the set the arrow starts from, which is the integers in this case), what the codomain is (the set the arrow points to, which is the rational numbers in this case), and the rule used to define $f$ .

Example 4.2. $f: \mathbb{Z} \to \mathbb{Z}$ defined by the rule ”$f(x) = y$ if and only if $x = y^2$ ” is not a function. There are many reasons for this:

• There are values in the domain that do not get mapped to any values in the codomain by our rule. For instance, consider $x = -1 \in \mathbb{Z}$ . There is no value $y \in \mathbb{R}$ such that $-1 = y^2$ , because no integer when squared is negative! Therefore, $x$ is not mapped to any value $y$ in the codomain, and so we do not regard $f$ as a function.

• There are also values in the domain that get mapped to multiple values in the codomain by our rule. For instance, consider $x=1 \in \mathbb{Z}$ . Because $1 = y^2$ has the two solutions $y=\pm1$ , this rule maps $x=1$ to the two values $y = \pm 1$ . This is another reason why $f$ is not a function!

Example 4.3. Let $A$ be the set of all students at the University of Auckland, and $B$ be the set of all integers. We can define a function $f: A\to B$ by defining $f(a)$ to be equal to that student’s current ID number. This is a function, because each student has a unique ID number!

However, if we tried to define a function $g: B \to A$ by the rule $g(b) =$ the student whose ID number is $b$ , we would fail! This is because there are many integers that are not ID numbers: for example, no student has ID number $-1$ , or $10^{100}$ .

While the objects above have had relatively “nice” rules, not all functions can be described quite so cleanly! Consider the following example:

Let $A$ be the collection {🇨🇦, 🐈, 🐥, 🇳🇿, 🕸️} of the Canada, cat, bird, New Zealand and web emojis, and let $B$ be the collection {🐙, ☢️, 🐝, 👨🏾} of the octopus, radiation, bee, and man emojis. Consider $f: A \to B,$ defined by the rules:

This is a function, because we have given an output for every possible input, and also never sends an input to multiple different outputs. It’s not a function with a simple algebraic rule like ”$x^2+2x-1$ ”, but that’s OK!

A useful way to visualize functions defined in this piece-by-piece fashion is with a diagram: draw the domain at left, the codomain at right, and draw an arrow from each $x$ in the domain to its corresponding element $f(x)$ in the codomain.

Alongside the domain/codomain ideas above, another useful idea here is the concept of range:

Note that the range is usually different to the codomain! In the examples we studied earlier, we saw the following:

• $f: \mathbb{Z} \to \mathbb{Q}$ defined by the rule $f(n) = \dfrac{1}{n^2+1}$ does not output every rational number! Amongst other values, it will never output any number greater than 1 (as $\dfrac{1}{n^2+1} \leq \dfrac{1}{0^2+1} = 1$ for every integer $n$ .) As such, its codomain ($\mathbb{Q}$ ) is not equal to its range.
• The function $f:A \to B$ from Example 4.3, that takes in any student at the University of Auckland and outputs their student ID, does not output every integer: amongst other values, it will never output a negative integer! As such, its codomain ($B$ ) is not equal to its range.
• The emoji function in Example 4.4 never outputs ☢️, even though it’s in the codomain.

Intuitively: we think of the codomain as letting us know what type of outputs we should expect. That is: in both mathematics or computer science, often just knowing that the output is “an integer” or “a binary string of length at most 20” or “a Unicode character” is enough for our compiler to work. As such, it’s often much faster to just describe the type of possible outputs, instead of laboriously finding out exactly what outputs are possible!

However, in some cases we will want to know precisely what values we get as outputs, and in that situation we will want to find the actual outputs: i.e. the range. To illustrate this, let’s consider a few examples:

Example 4.5. Consider the function $f: \mathbb{Z} \to \mathbb{Z}$ given by the rule $f(x) = 2|x| + 2$ . This function has range equal to all even numbers that are at least 2.

To see why, simply notice that for any integer $x$ , $|x|$ is the “absolute value” of $x$ : i.e. it’s $x$ if we remove its sign so that it’s always nonnegative. As a result, $2|x|$ is always a nonnegative even number, and this $2|x| + 2$ must be a nonnegative even number that’s at least 2.

That tells us that the only possible outputs are even numbers that are at least 2! However, we still don’t know that all of those outputs are ones that we actually can get as outputs.

To see why this is true: take any even number that is at least 2. By definition, we can write this as $2k$ , for some $k \geq 1$ . Rewrite this as $2(k-1) + 2$ ; if we do so, then we can see that $f(k-1) = 2|k-1| + 2 = 2(k-1) + 2$ (because if $k \geq 1,$ then $k-1 \geq 0$ and so $|k-1| = k-1$ .) As a result, we’ve shown that $f(k-1) = 2k$ for any $k \geq 1$ , and thus that we can actually get any even number that’s at least 2 as an output.

Example 4.7. Let $A$ be the collection of all pairs of words in the English language, and $B$ be the two values $\{$ true, false$\}$ . Define the function $f: A \to B$ by saying that $f(w_1, w_2) =$ true if the words $w_1, w_2$ rhyme, and false otherwise. For example, $f($ cat, bat$) =$ true, while $f($ cat, cataclysm$)=$ is false.

The range of this function is $\{$ true, false$\}$ , i.e. the same as its codomain! It is possible for the range and codomain to agree. (If this happens, we call such a function a surjective function. We’re not going to focus on these functions here, but you’ll see more about them in courses like Compsci 225 and Maths 120/130!)

Example 4.8. Let $\mathbb{R}$ denote the set of all real numbers (i.e. all numbers regardless of whether they’re rational or irrational; alternately, anything you can describe with a decimal expansion.) Define the function $f: \mathbb{R} \to \mathbb{R}$ by the rule $f(x) = 2^x$ . This function has range equal to the set of all positive numbers! This takes more math to see than we currently have: again, take things like Maths 130 to see the “why” behind this. However, if you draw a graph of $2^x$ you’ll see that the outputs (i.e. $y$ -values) range over all of the possible positive numbers, as claimed.

To close this section, we give a useful bit of notation for talking about functions defined in terms of other functions: function composition.

Fact 4.2. Given any two functions $f: B \to C, g: A \to B$ , we can combine these functions via function composition: that is, we can define the function $f \circ g: A\to C$ , defined by the rule $f \circ g (x) = f(g(x))$ . We pronounce the small open circle symbol $\circ$ as “composed with.”

Example 4.9.

• If $f, g: \mathbb{R}\to \mathbb{R}$ are defined by the rules $f(x) = x+1$ and $g(x) = x^2-1,$ then we would have $g \circ f(x) = g(f(x)) = g(x+1) = (x+1)^2 - 1 = x^2 + 2x$ .

• Notice that this is different to $f \circ g (x) = f(g(x)) = f(x^2-1) = (x^2-1)+1 = x^2$ !

  In general, $f \circ g$ and $g \circ f$ are usually different functions: make sure to be careful with the order in which you compose functions.

• If $f, g: \mathbb{R}\to \mathbb{R}$ are defined by the rules $f(x) = 3x-1$ and $g(x) = \frac{x+1}{3}$ , then $f \circ g (x) = f(g(x)) = f\left( \frac{x+1}{3}\right) = 3\frac{x+1}{3} - 1 = (x+1)-1 = x$ .

• If $f: \mathbb{R}^+\to \mathbb{R}^+$ and $g: \mathbb{R}^+ \to \mathbb{R}$ are defined by the rules $f(x) = 2^{x^2+1}$ and $g(x) = \log_2(x) - 1$ , then $g \circ f (x) = g(f(x)) = g\left(2^{x^2+1}\right) = \log_2\left(2^{x^2+1}\right)-1 = (x^2+1) - 1 = x^2$ .

  (Here, $\mathbb{R}^+$ denotes the set of all positive real numbers.)

Handy!

Notice that in the definition above, we required that the domain of $f$ was the codomain of $g$ . That is: if we wanted to study $f \circ g (x) = f(g(x))$ , we needed to ensure that every output of $g$ is a valid input to $f$ .

This makes sense! If you tried to compose functions whose domains and codomains did not match up in this fashion, you’d get nonsense / crashes when the inner function $g$ returns an output at which the outer function is undefined. For example:

Example 4.10.

• If $f: \mathbb{R} \setminus \{0\} \to \mathbb{R}$ is defined by the rule $f(x) = \frac{1}{x}$ and $g: \mathbb{R} \to \mathbb{R}$ is defined by the rule $g(x) = x^2-1$ , then you might think that $f \circ g (x) = f(g(x)) = \frac{1}{x^2-1}$ .

  However, this is not a function! When $x=\pm 1$ , for example, we have $f(g(\pm 1)) = \frac{1}{(\pm 1)^2 - 1} = \frac{1}{0}$ , which is undefined. This is why we insist that the codomain of $g$ is the domain of $f$ ; we need all of $g$ ’s outputs to be valid inputs to $f$ .

• Let $A$ be the set of all people in your tutorial room, $B$ be the set of all ID numbers of UoA students, and $C$ be the set of all ID numbers of Compsci 120 students. Then $f: C \to \mathbb{R}$ defined by taking any Compsci 120 student’s ID and outputting their grade on the mid-sem test is a function; as well, $g: A \to B$ , defined by mapping each person in your tutorial room to their ID number is a function.

  However, $f \circ g$ , the function that tries to take each person in your tutorial room and output their mid-sem test score, is undefined! In particular, your tutor is someone in your tutorial room, who even though they do have an ID number, will not have a score on the mid-sem test. Another reason to insist that the codomain of $g$ is the domain of $f$ !

Algorithms

In the previous section, we came up with a “general” concept for function that we claimed would be better for our needs in computer science, as it would let us think of things like

/* function returning the max between two numbers */
int max(int num1, int num2) 
{
    /* local variable declaration */
    int result;
 
    if (num1 > num2)
        result = num1;
    else
        result = num2;
 
    return result; 
}

as a function. However, most of the examples we studied in this chapter didn’t feel too much like the code above: they were either fairly mathematical in nature (i.e. $f(n) = \frac{1}{n^2+1}$ ) or word-problem-oriented (i.e. the function that sent UoA students to their ID numbers.)

To fix this issue, this section will focus on the idea of an algorithm: that is, a way of describing in general a step-by-step problem-solving process that we can easily turn into code.

We start by describing what an algorithm is:

Typically, people think of algorithms as a set of instructions for solving some problem; when they do so, they typically have some restrictions in mind for the kinds of instructions they consider to be valid. For example, consider the following algorithm for proving the Riemann hypothesis:

1. Prove the Riemann hypothesis.
2. Rejoice!

On one hand, this is a fairly precise and unambiguous set of instructions: step 1 has us come up with a proof of the Riemann hypothesis, and step 2 tells us to rejoice.

On the other hand: this is not a terribly useful algorithm. In particular, its steps are in some sense “too big” to be of any use: they reduce the problem of proving the Riemann hypothesis to … proving the Riemann hypothesis. Typically, we’ll want to limit the steps in our algorithms to simple, mechanically-reproducible steps: i.e. operations that a computer could easily perform, or operations that a person could do with relatively minimal training.

In practice, the definition of “simple” depends on the context in which you are creating your algorithm. Consider the algorithm for making delicious pancakes, given at below.

This algorithm’s notion of “simple” is someone who is (1) able to measure out quantities of various foods, and (2) knows the meaning of various culinary operations like “whisk” and “flip.” If we wanted, we could make an algorithm that includes additional steps that define “whisking” and “flipping”. That is: at each step where we told someone to whisk the flour, we could instead have given them the following set of instructions:

(a). Grab a whisk. If you do not know what a whisk is, go to this Wikipedia article and grab the closest thing to a whisk that you can find. A fork will work if it is all that you can find. (b). Insert the whisk into the object you are whisking. (c). Move the whisk around through the object you are whisking in counterclockwise circles of varying diameter, in such a fashion to mix together the contents of the whisked object.

In this sense, we can extend our earlier algorithm to reflect a different notion of “simple,” where we no longer assume that our person knows how to whisk things. It still describes the same sets of steps, and in this sense is still the “same” algorithm — it just has more detail now!

This concept of “adding” or “removing” detail from an algorithm isn’t something that will always work; some algorithms will simply demand steps that cannot be implemented on some systems. For example, no matter how many times you type “sudo apt-get 2 cups of flour,” your laptop isn’t going to be able to implement our above pancake algorithm. As well, there may be times where a step that was previously considered “simple” becomes hideously complex on the system you’re trying to implement it on!

We’re not going to worry too much about the precise definition of “simple” in this class, because we’re not writing any code here (and so our notion of “simple” isn’t one we can precisely nail down) --- these are the details we’ll leave for your more coding-intensive courses.

Instead, let’s just look at a few examples of algorithms! We’ve already seen one in this class, when we defined the $\%$ operation:

Algorithm 4.3. This algorithm takes in any two integers $a, n$ , where $n > 0$ . It then calculates $a \% n$ as follows:

• If $a \geq n$ , we repeatedly subtract $n$ from $a$ until $a < n$ , and return the end result.
• If $a < 0$ , repeatedly add $n$ to $a$ until $a > 0$ , and return the end result.
• If neither of these cases apply, then we just return $a$ .

Second, we can turn Claim 1.6 into an algorithm for how to tell if a number is prime:

Algorithm 4.4. This is an algorithm that takes in a positive integer $n$ , and determines whether or not $n$ is prime. It proceeds as follows:

• If $n=1$ , stop: $n$ is not prime.
• Otherwise, if $n > 1$ , find all of the numbers $2,3,4,\ldots \lfloor \sqrt{n} \rfloor$ . Take each of these numbers, and test whether they divide $n$ .
• If one of them does, then $n$ is not prime!
• Otherwise, if none of them divide $n$ , then by Claim 1.6, $n$ is prime.

This is a step-by-step process that tells us if a number is a prime or not! Notice that the algorithm itself didn’t need to contain a proof of Claim 1.6; it just has to give us instructions for how to complete a task, and not justify why those instructions will work. It is good form to provide such a justification where possible, as it will help others understand your code! However, it is worth noting that such a justification is separate from the algorithm itself: it is quite possible (and indeed, all too easy) to write something that works even though you don’t necessarily understand why.

For a third example, let’s consider an algorithm to sort a list:

Algorithm 4.5. The following algorithm, $\texttt{SelectionSort}(L)$ , takes in a list $L =(l_1, l_2, \ldots l_n)$ of $n$ numbers and orders it from least to greatest. For example, $\texttt{SelectionSort}(1,7,1,0)$ is $(0,1,1,7)$ . It does this by using the following algorithm:

1. If $L$ contains at most one number, $L$ is trivially sorted! In this situation, stop.
2. Otherwise, $L$ contains at least two numbers. Let $L = (l_1, l_2, \ldots l_n)$ , where $n \geq 2$ . Define a pair of values $\texttt{val}_\texttt{min}$ , $\texttt{loc}_\texttt{min}$ , and set them equal to the value and location of the first element in our list.
3. One by one, starting with the second entry in our list and working our way through our entire list $L$ , compare the value stored in $\texttt{val}_\texttt{min}$ to the current value $l_k$ that we’re examining.

• If $\texttt{val}_\texttt{min} > l_k$ , update $\texttt{val}_\texttt{min}$ to be equal to $l_k$ , and update $\texttt{loc}_\texttt{min}$ to be equal to k.

• Otherwise, just go on to the next value.

4. At the end of this process, $\texttt{val}_\texttt{min}$ and $\texttt{loc}_\texttt{min}$ describes the value and the location of the smallest element in our list. Swap the first value in our list with $l_{\texttt{loc}_\texttt{min}}$ in our list: this makes the first value in our list the smallest element in our list.
5. To finish, set the first element of our list aside and run $\texttt{SelectionSort}$ on the rest of our list.

Back in our first chapter, to understand our two previous algorithms 4.3 and 4.4 we started by running these algorithms on a few example inputs! In general, this is a good tactic to use when studying algorithms; actually plugging in some concrete inputs can make othewise-obscure instructions much simpler to understand.

To do so here, let’s run our algorithm on the list $(1,7,1,0)$ , following each step as written:

Here, we use the $\boxed{7,1,1}$ , $\boxed{7,1}$ and $\boxed{7}$ boxes to visualize the “rest of our list” part of step 5 in our algorithm.

This worked! Moreover, doing this by hand can help us see an argument for why this algorithm works:

Proof. In general, there are three things we need to check to show that a given algorithm works:

• The algorithm doesn’t have any bugs: i.e. every step of the process is defined, you don’t have any division by zero things or undefined cases, or stuff like that.

  This is true here! The only steps we perform in this algorithm are comparisons and swaps, and the only case we encounter is ”$\texttt{val}_\texttt{min} > l_k$ is true” or ”$\texttt{val}_\texttt{min} > l_k$ is false,” which clearly covers all possible situations. As such, there are no undefined cases or undefined operations.

• The algorithm doesn’t run forever: i.e. given a finite input, the algorithm will eventually stop and not enter an infinite loop.

  This is also true here! To see why, let’s track the number of comparisons and write operations performed by this process, given a list of length $n$ as input:

  • Step 1: one comparisons (we checked the size of the list.)

  • Step 2: two write operations (we defined $\texttt{val}_\texttt{min}$ , $\texttt{loc}_\texttt{min}$ .)

  • Step 3: $(n-1)$ comparisons and possibly $2(n-1)$ write operations.

    To see why: note that for all of the $n-1$ entries in our list from $l_2$ onwards, we looked up the value in $l_k$ and compared it to the value we have in $\texttt{val}_\texttt{min}$ , which gives us $n-1$ comparisons. If it was smaller, we rewrote the values in $\texttt{val}_\texttt{min}$ and $\texttt{loc}_\texttt{min}$ in 3(a).

  • Step 4: 2 write operations (to swap these values.)

  • Step 5: 1 write operation (to resize the list to set the first element aside), and however many operations we need to sort a list of $n-1$ numbers with $\texttt{SelectionSort}$ .

  In total, then, we have the following formula: if $\texttt{SelectionSortSteps}(n)$ denotes the maximum number of operations in total needed to sort a list with our algorithm, then

  $\texttt{SelectionSortSteps}(n) = 1+2+(n-1)+2(n-1) + 2 + 1+ \texttt{SelectionSortSteps}(n-1)$
  $= 3n+3 + \texttt{SelectionSortSteps}(n-1).$
  $= 3(n+1) + \texttt{SelectionSortSteps}(n-1).$

  At first, this looks scary: our function is defined in terms of itself! In practice, though, this is fine. We know that $\texttt{SelectionSortSteps}(1) =1$ , because step 1 immediately ends our program if the list has size 1.

  Therefore, our formula above tells us that if we set $n=2$ , we have

  $\texttt{SelectionSortSteps}(2) = (3\cdot (2+1)) + \texttt{SelectionSortSteps}(2-1) = 9+1= \boxed{10},$

  by using our previously-determined value for $\texttt{SelectionSortSteps}(1)$ . Still finite!

  We can do this again for $n=3$ , and get

  $\texttt{SelectionSortSteps}(3) = (3\cdot (3+1)) + \texttt{SelectionSortSteps}(3-1) = 12 +10 = \boxed{22},$

  by using our previously-determined value for $\texttt{SelectionSortSteps}(2)$ . Again, still finite!

  In general, if this process can sort a list of size $n-1$ in finitely many steps, then it only takes us $3n+3$ more steps to sort a list of size $n$ . In particular, there is no point at which our algorithm jumps to needing “infinitely many” steps to sort a list!

• The algorithm produces the desired output: in this case, it produces a list ordered from least to greatest.

  This happens! To see why, notice that in step 4, we always make the first element of the list we’re currently sorting the smallest element in our list. Therefore, on our first application of step 4, we have ensured that $l_1$ is the smallest element of our list.

  On the second application of step 4, we were sorting the list starting from its second element: doing so ensures that $l_2$ is smaller than all of the remaining elements.

  On the third application of step 4, we had set the first two elements aside and were sorting the list starting from its third element: doing so ensures that $l_3$ is smaller than all of the remaining elements.

  In general, on the $k$ -th application of step 4, we had set the first $k-1$ elements aside and were sorting the list starting from its $k$ -th element! Again, doing so ensures that $l_k$ is smaller than all of the remaining elements.

So, in total, what does this mean? Well: by the above, we know that $l_1 \leq l_2 \leq l_3 \leq \ldots \leq l_n$ , as by definition each element is smaller than all of the ones that come afterwards. In other words, this list is sorted! $\square$

Recursion, Composition, and Algorithms

Algorithm 4.5 had an interesting element to its structure: in its fifth step, it contained a reference to itself! This sort of thing might feel like circular reasoning: how can you define an object in terms of itself?

However, if you think about it for a bit, this sort of thing is entirely natural: many tasks and processes in life consist of “self-referential” that are defined by self-reference! We call such definitions recursive definitions, and give a few examples here:

Example 4.11. Fractals, and the many plants and living things that have fractal-like patterns built into theirselves, are examples of recursively-defined objects! For example, consider the following recursive process:

1. Start by drawing any shape $S_0$ . For example, here’s a very stylized drawing of a cluster of fern spores:

2. Now, given any shape $S$ , we define $T(S)$ as the shape made by making four copies of $S$ and manipulating them as follows: if $S$ is a shape contained within the gray rectangle at left, we make four copies of $S$ appropriately scaled/stretched/etc to match the four rectangles at right. (It can be hard to see the black rectangle, because it’s so squished: it’s the stem-looking bit at the bottom-middle.)

   

   For example, $T(S_0)$ , i.e. $T$ applied to our fern spore shape, is the following:

   

3. Using our “seed” shape $S_0$ and our function $T$ , we then recursively define $S_n$ as $T(S_{n-1})$ for every positive integer $n$ . That is: $S_1 = T(S_0), S_2 = T(S_1)$ , etc. This is a recursive definition because we’re defining our shapes in terms of previous shapes! Using the language of function composition, we can express this all at once by writing $S_n = \underbrace{T \circ T \circ \ldots \circ T}_{n \textrm{ times}}(S_0)$ .

4. Now, notice what these shapes look like as we draw several of them in a row:

   

   Our seed grows into a fern!

This is not a biology class, and there are many open questions about precisely how plants use DNA to grow from a seed. However, the idea that many plants can be formed by taking a simple instruction (given one copy of a thing, split it into appropriately stretched/placed copies of that thing) and repeatedly applying it is one that should seem reasonable, given the number of places you see it in the world!

Example 4.12. On the less beautiful but more practical side, recursion is baked into many fundamental mathematical operations! For example, think about how you’d calculate $11 \cdot 13$ . By definition, because multiplication is just repeated addition, you could calculate this as follows:

Now, however, suppose that someone asked you to calculate $12 \cdot 13$ . While you could use the process above to find this product, you could also shortcut this process by noting that

This sort of trick is essentially recursion! That is: if you want, you could define the product $n \cdot k$ recursively for any nonnegative integer $n$ by the following two-step process:

• $0 \cdot k = 0$ , for every $k$ .
• For any $n \geq 1$ , $n \cdot k = k + (n-1)\cdot k$ .

The second bullet point is a recursive definition, because we defined multiplication in terms of itself! In other words, when we say that $12 \cdot 13 = 13 + 11 \cdot 13$ , we’re really thinking of multiplication recursively: we’re not trying to calculate the whole thing out all at once, but instead are trying to just relate our problem to a previously-worked example.

Exponentiation does a similar thing! Because exponentiation is just repeated multiplication, we know that

Similarly, though, we can define exponentiation recursively by saying that for any nonnegative integer $n$ and nonzero number $a$ , that

• $a^0 = 1$ , and
• For any $n \geq 1$ , $a^n = a \cdot a^{n-1}$ .

In other words, with this idea, we can just say that

instead of calculating the entire thing from scratch!

These ideas can be useful if you’re working with code where you’re calculating a bunch of fairly similar products/exponents/etc. With recursion, you can store some precalculated values and just do a few extra steps of working rather than doing the whole thing out by scratch each time. Efficiency!

Recursion also comes up in essentially every dynamical system that models the world around us! For instance, consider the following population modelling problem:

Example 4.13. Suppose that we have a petri dish in which we’re growing a population of amoebae, each of which can be in two possible states (small and large).

Amoebas grow as follows: if an amoeba is small at some time $t$ , then at time $t+1$ it becomes large, by eating food around it. If an amoeba is large at some time $t$ , then at time $t+1$ it splits into one large amoeba and one small amoeba.

Suppose our petri dish starts out with one small amoeba at time $t=1$ . How many amoebae in total will be in this dish at time $t=n$ , for any natural number $n$ ?

Answer. To help find an answer, let’s make a chart of our amoeba populations over the first six time steps:

This chart lets us make the following observations:

1. The number of large amoebae at time $n$ is precisely the total number of amoebae at time $n-1$ . This is because every amoeba at time $n-1$ either grows into a large amoeba, or already was a large amoeba!
2. The number of small amoebae at time $n$ is the number of large amoebae at time $n-1$ . This is because the only source of small amoebae are the large amoebae from the earlier step when they split!
3. By combining 1 and 2 together, we can observe that the number of small amoebae at time $n$ is the total number of amoebae at time $n-2$ !
4. Consequently, because we can count the total number of amoebae by adding the large amoebae to the small amoebae, we can conclude that the total number of amoebae at time $n$ is the total number of amoebae at time $n-1$ , plus the total number of amoebae at time $n-2$ . In symbols,

We call relations like the one above recurrence relations, and will study them in greater depth when we get to induction as a proof method.

For now, though, notice that they are remarkably useful objects! By generalizing the model above (i.e. subtracting $a_{n-3}$ to allow for old age killing off amoebas, or having a $-ca_n^2$ term to denote that as the population grows too large, predation or starvation will cause the population to die off, etc.) one can basically model an arbitrarily-complicated population over the long term.

It bears noting that the amoeba recurrence relation is not the first recurrence relation you’ve seen! If you go back to Algorithm 4.5, we proved that

This is another recurrence relation: it describes the maximum number of operations needed to sort a list of size $n$ in terms of the maximum number of operations needed to sort a list of size $n-1$ .

While recurrence relations are nice, they can be a little annoying to work with directly. For example, suppose that someone asked us what $\texttt{SelectionSortSteps}(12)$ is. Because we don’t have a non-recursive formula, the only thing we could do here is just keep recursively applying our formula, to get

This is … kinda tedious. It would be nice if we had a direct formula for this: something like $\texttt{SelectionSortSteps}(n) =2^n$ or $n^2-4n + 17$ that we could just plug $n$ into and get an answer.

At this point in time, we don’t have enough mathematics to directly find such a “closed” form. However, we can still sometimes find an answer by just guessing. To be a bit more specific: if we use our definition, we can calculate the following values for $\texttt{SelectionSortSteps}(n)$ :

If you plug this into the Online Encyclopedia of Integer Sequences, it will give you the following guess by comparing it to all of the sequences it knows:

This turns out to be correct!

We don’t have the techniques to prove this just yet. If you would like to see a proof, though, skip ahead to the induction section of our proofs chapter! We’ll tackle this problem there (along with another recurrence relation), in Section 7.8.

Runtime and Algorithms

In the above few sections, we studied $\texttt{SelectionSortSteps}(n)$ and analyzed the maximum number of operations it needs to sort a list of length $n$ . In general, this sort of run-time analysis of an algorithm - i.e. the number of elementary operations needed for that algorithm to run - is a very useful thing to be able to do!

To give a brief example of why this is useful, consider another, less well-known algorithm that we can use to sort a list:

Algorithm 4.6. The following algorithm, BogoSort $(L)$ , takes in a list $L =(l_1, l_2, \ldots l_n)$ of $n$ numbers and orders it from least to greatest. It does this by using the following algorithm:

1. One by one, starting with the first entry in our list and working our way through our list, compare the values stored in consecutive elements in our list.

   If these elements never decrease - i.e. if when we perform these comparisons, we see that $l_1 \leq l_2 \leq \ldots \leq l_n$ - then our list is already sorted! Stop.

2. Otherwise, our list is not already sorted. In this case, randomly shuffle the elements of our list around, and loop back to step 1.

Here’s a sample run of this algorithm on the list $(1,7,1,0)$ , where I’ve used Random.org to shuffle our list when needed by step 3:

This … is not great. If you used BogoSort to sort a deck of cards, your process would look like the following:

• One-by-one, go through your deck of cards and see if they’re ordered.
• If during this process you spot any cards that are out of order, throw the whole deck in the air, collect the cards together, and start again.

By studying the running time of this algorithm, we can make “not great” into something rigorous:

Proof. If $L$ is a list containing $n$ different elements, there are $n!$ many different ways to order $L$ ’s elements (this is ordered choice without repetition, where we think of ordering our list as “choosing” elements one-by-one to put in order.) If all of these elements are different, then there is exactly one way for us to put these elements in order.

Therefore, on each iteration BogoSort has a $\frac{1}{n!}$ chance of successfully sorting our list, and therefore has a $\frac{n!-1}{n!}$ chance of failing to sort our list. For any $n >1$ , $n! -1$ is nonzero, and so the chance that our algorithm fails on any given iteration is nonzero.

Therefore, in the worst-case scenario, it is possible for our algorithm to just fail on each iteration, and thereby this algorithm could have infinite run-time.

In terms of running time, then, we’ve shown that BogoSort has a strictly worse runtime than $\texttt{SelectionSortSteps}$ , as $\infty > \dfrac{3n^2+9n^{2^2}-10}{2}$ . Success!

This sort of comparison was particularly easy to perform, as one of the two things we were comparing was $\infty$ . However, this comparison process can get trickier if we examine more interesting algorithms. Let’s consider a third sorting algorithm:

Algorithm 4.7. The following algorithm, MergeSort$(L)$ , takes in a list $L =(l_1, l_2, \ldots, l_n)$ of $n$ numbers and orders it from least to greatest. It does this by using the following algorithm:

1. If $L$ contains at most one number, $L$ is trivially sorted! In this situation, stop.

2. Otherwise, $L$ contains at least two numbers. In this case,

   (a) Split $L$ in half into two lists $L_1, L_2$ .

   (b) Apply MergeSort to each of $L_1, L_2$ to sort them.

3. Now, we “merge” these two sorted lists:

   (a) Create a big list with $n$ entries in it, all of which are initially blank.

   (b)Compare the first element in $L_1$ to the first element in $L_2$ . If $L_1, L_2$ are both sorted, these first elements are the smallest elements in $L_1, L_2$ .

   (c) Therefore, the smaller of those two first elements is the smallest element in our entire list. Take it, remove it from the list it came from, and put it in the first blank location in our big list.

   (d) Repeat (b)+(c) until our big list is full!

As before, to better understand this algorithm, let’s run it on an example list like $(1,7,1,0,2)$ :